[proofplan] We prove both directions by converting between complete PA theories and binary diagonal avoidance. From a complete consistent extension $T$ of PA, we let $T$ decide a uniformly computable sentence saying that the corresponding diagonal computation does not halt with value $1$; PA-verifiable correctness of computations forces the opposite binary value whenever $\varphi_e(e)$ converges. Conversely, from a binary diagonally noncomputable function $f$, we build a path through the co-c.e. tree of finite consistent decisions of arithmetic sentences. The key point is that the dead-child search at each node is a partial computable binary function, so $f$ cannot choose a dead branch. [/proofplan] [step:Use a complete PA extension to define a binary diagonal avoider] Assume $a$ is a PA degree. Let $A \in a$ compute a complete consistent extension $T$ of PA, regarded as a set of Gödel codes of arithmetic sentences. Fix a standard primitive recursive computation predicate $C(e,x,b,t)$ with the meaning that the computation of $\varphi_e(x)$ halts by stage $t$ with value $b \in \{0,1\}$. We use the standard formalisation for which PA proves uniqueness of computation values: for all $e,x,t,s \in \mathbb{N}$, PA proves that $C(e,x,0,t)$ and $C(e,x,1,s)$ cannot both hold. For each $e \in \mathbb{N}$, let $\alpha_e$ be the arithmetic sentence \begin{align*} \neg \exists t \, C(e,e,1,t). \end{align*} The map $e \mapsto \ulcorner \alpha_e \urcorner$ is computable. Define \begin{align*} f: \mathbb{N} &\to \{0,1\} \\ e &\mapsto \begin{cases} 1, & \text{if } \ulcorner \alpha_e \urcorner \in T,\\ 0, & \text{if } \ulcorner \neg \alpha_e \urcorner \in T. \end{cases} \end{align*} Since $T$ is complete and consistent, exactly one of $\alpha_e$ and $\neg \alpha_e$ belongs to $T$, so $f$ is a total $\{0,1\}$-valued function. Since $A$ computes $T$ and $e \mapsto \ulcorner \alpha_e \urcorner$ is computable, $A$ computes $f$. It remains to verify diagonal disagreement. Let $e \in \mathbb{N}$. If $\varphi_e(e)=1$, then for some $t \in \mathbb{N}$ the true primitive recursive fact $C(e,e,1,t)$ holds. PA proves each true instance of a primitive recursive computation fact, so PA proves $\exists t\, C(e,e,1,t)$, hence PA proves $\neg \alpha_e$. Since $T$ extends PA and is consistent, $\alpha_e \notin T$, so $f(e)=0 \neq 1$. If $\varphi_e(e)=0$, then for some $t \in \mathbb{N}$ the true primitive recursive fact $C(e,e,0,t)$ holds. By PA-verifiable uniqueness of computation values, PA proves \begin{align*} C(e,e,0,t) \implies \neg \exists s\, C(e,e,1,s). \end{align*} Thus PA proves $\alpha_e$. Since $T$ extends PA, $\alpha_e \in T$, and therefore $f(e)=1 \neq 0$. Thus $f$ is diagonally noncomputable relative to $(\varphi_e)_{e \in \mathbb{N}}$. [/step] [step:Represent complete PA extensions as paths through a co-c.e. binary tree] Fix a computable one-to-one enumeration $(\theta_n)_{n \in \mathbb{N}}$ of all arithmetic sentences, with computable inverse on sentence codes. For a finite binary string $\sigma \in 2^{<\mathbb{N}}$, define the finite set of sentence decisions \begin{align*} D_\sigma := \{\theta_i : i < |\sigma| \text{ and } \sigma(i)=1\} \cup \{\neg \theta_i : i < |\sigma| \text{ and } \sigma(i)=0\}. \end{align*} Define the tree \begin{align*} S := \{\sigma \in 2^{<\mathbb{N}} : \mathrm{PA} \cup D_\sigma \text{ is syntactically consistent}\}. \end{align*} The complement of $S$ is computably enumerable: enumerate proofs from PA together with the finitely many extra assumptions in $D_\sigma$, and enumerate $\sigma$ out of $S$ when a contradiction is found. Hence $S$ is a co-c.e. subtree of $2^{<\mathbb{N}}$. The tree $S$ is infinite. Indeed, the empty string belongs to $S$ because PA is consistent. If $\sigma \in S$ and both $\sigma^\frown 0$ and $\sigma^\frown 1$ were outside $S$, then $\mathrm{PA} \cup D_\sigma \cup \{\neg\theta_{|\sigma|}\}$ and $\mathrm{PA} \cup D_\sigma \cup \{\theta_{|\sigma|}\}$ would both be inconsistent. Since $D_\sigma$ is finite, the [deduction theorem](/theorems/1452) applies to these finite extra assumptions. The first inconsistency gives a derivation in $\mathrm{PA} \cup D_\sigma$ of $\neg\neg\theta_{|\sigma|}$, hence of $\theta_{|\sigma|}$ by classical propositional logic. The second inconsistency gives a derivation in $\mathrm{PA} \cup D_\sigma$ of $\neg\theta_{|\sigma|}$. Thus $\mathrm{PA} \cup D_\sigma$ proves both $\theta_{|\sigma|}$ and $\neg\theta_{|\sigma|}$, contradicting $\sigma \in S$. Hence every node in $S$ has at least one child in $S$, and induction gives nodes of every length. [/step] [step:Use the DNC function to avoid dead branches] Assume now that $A \in a$ computes a total function $f: \mathbb{N} \to \{0,1\}$ satisfying $f(e) \neq \varphi_e(e)$ whenever $\varphi_e(e)$ is defined. We construct an infinite path $P \in 2^{\mathbb{N}}$ through $S$ using oracle access to $f$. For each finite binary string $\sigma$, define a partial computable function $\psi_\sigma: \mathbb{N} \rightharpoonup \{0,1\}$ as follows. On any input, $\psi_\sigma$ searches for a bit $b \in \{0,1\}$ and a number $m \in \mathbb{N}$ such that every string $\tau \in 2^{<\mathbb{N}}$ extending $\sigma^\frown b$ with $|\tau|=|\sigma|+1+m$ has been enumerated into the complement of $S$. If such a pair $(b,m)$ is found, $\psi_\sigma$ outputs $b$ and halts. By acceptability of $(\varphi_e)_{e \in \mathbb{N}}$, there is a computable index function \begin{align*} h: 2^{<\mathbb{N}} \to \mathbb{N} \end{align*} such that $\varphi_{h(\sigma)}=\psi_\sigma$ for every $\sigma \in 2^{<\mathbb{N}}$. Define finite strings $(\sigma_n)_{n \in \mathbb{N}}$ recursively by \begin{align*} \sigma_0 &:= \varnothing,\\ \sigma_{n+1} &:= \sigma_n^\frown f(h(\sigma_n)). \end{align*} We prove by induction that each $\sigma_n$ has an infinite extension through $S$. This is true for $\sigma_0$ because $S$ is infinite. Suppose $\sigma_n$ has an infinite extension through $S$. If the chosen child $\sigma_n^\frown f(h(\sigma_n))$ had no infinite extension through $S$, then, since $S$ is finitely branching and co-c.e., there would be some level at which all extensions of that child had been enumerated into the complement of $S$. Therefore $\psi_{\sigma_n}(h(\sigma_n))$ would halt with value $f(h(\sigma_n))$, meaning \begin{align*} \varphi_{h(\sigma_n)}(h(\sigma_n)) = f(h(\sigma_n)). \end{align*} This contradicts the DNC property of $f$. Hence the chosen child has an infinite extension through $S$. [guided] The construction is designed to let $f$ choose the next bit, but only after we have arranged that a wrong choice would be visible as a diagonal computation. At a node $\sigma$, the dangerous situation is that one child, say $\sigma^\frown b$, is dead: it has no infinite extension through the consistency tree $S$. Because $S$ is co-c.e. and finitely branching, deadness is semidecidable. If $\sigma^\frown b$ is dead, then there is a finite level $|\sigma|+1+m$ at which every extension of $\sigma^\frown b$ has already been removed from $S$ by a finite inconsistency proof. This is why we define $\psi_\sigma$ to search for such a dead child and output its bit. Formally, \begin{align*} \psi_\sigma: \mathbb{N} \rightharpoonup \{0,1\} \end{align*} is the partial computable function which ignores its input and searches for $b \in \{0,1\}$ and $m \in \mathbb{N}$ such that every length $|\sigma|+1+m$ extension of $\sigma^\frown b$ has been enumerated into $2^{<\mathbb{N}} \setminus S$. If it finds such data, it outputs $b$. The acceptable enumeration gives a computable index $h(\sigma)$ with $\varphi_{h(\sigma)}=\psi_\sigma$. We now let the DNC function choose the next bit: \begin{align*} \sigma_{n+1} := \sigma_n^\frown f(h(\sigma_n)). \end{align*} Suppose $\sigma_n$ still has an infinite extension through $S$. At most one child of $\sigma_n$ can be dead, because if both children were dead then $\sigma_n$ itself would have no infinite extension. If the child selected by $f$ were dead, then $\psi_{\sigma_n}$ would eventually discover this and halt with exactly that selected bit: \begin{align*} \varphi_{h(\sigma_n)}(h(\sigma_n)) = \psi_{\sigma_n}(h(\sigma_n)) = f(h(\sigma_n)). \end{align*} This is forbidden by the DNC property. Therefore the selected child is not dead, so it has an infinite extension through $S$. This completes the induction. [/guided] [/step] [step:Read the path as a complete consistent extension of PA] Let \begin{align*} P := \bigcup_{n \in \mathbb{N}} \sigma_n \in 2^{\mathbb{N}}. \end{align*} The previous step shows that every finite initial segment of $P$ lies in $S$. Since the sequence $(\sigma_n)_{n \in \mathbb{N}}$ is computable from $f$, and $f$ is computable from $A$, the path $P$ is computable from $A$. Define the set of arithmetic sentences \begin{align*} T_P := \{\theta_n : P(n)=1\} \cup \{\neg\theta_n : P(n)=0\}. \end{align*} Because the enumeration $(\theta_n)_{n \in \mathbb{N}}$ is computable with computable inverse on sentence codes, $T_P$ is computable from $P$, hence computable from $A$: given a sentence code, compute its index if it is some $\theta_n$, and otherwise compute the index of the sentence whose negation it is. The theory $T_P$ is complete: for each sentence $\theta_n$, the bit $P(n)$ places exactly one of $\theta_n$ and $\neg\theta_n$ in $T_P$. It is consistent because every finite subset of $T_P$ is contained in $\mathrm{PA} \cup D_{\sigma_m}$ for some $m \in \mathbb{N}$, and $\sigma_m \in S$. It remains to check that $T_P$ extends PA and is deductively closed. If $\theta_n$ is an axiom of PA and $P(n)=0$, then some finite initial segment of $P$ would contain the decision $\neg\theta_n$, making $\mathrm{PA} \cup D_{\sigma_m}$ inconsistent for all sufficiently large $m$, contrary to $\sigma_m \in S$. Thus every PA axiom belongs to $T_P$. If $T_P$ proves a sentence $\theta_n$ but $P(n)=0$, then a finite subset of $T_P$ proves $\theta_n$, while $T_P$ also contains $\neg\theta_n$. These finitely many decisions occur inside $D_{\sigma_m}$ for some $m$, so $\mathrm{PA} \cup D_{\sigma_m}$ is inconsistent, contradicting $\sigma_m \in S$. Therefore every theorem of $T_P$ belongs to $T_P$, and $T_P$ is a complete consistent extension of PA computable from $A$. Hence $a$ is a PA degree. Combining this with the first direction proves the equivalence. [/step]