[proofplan] We prove both directions by reading the second-order axioms of $\mathsf{RCA}_0$ as closure conditions on the available sets. In an $\omega$-model, recursive comprehension forms every set computable from the parameters already present, which gives downward closure under Turing reducibility and closure under Turing joins. Conversely, if $\mathcal S$ is a Turing ideal, then every set whose membership relation is recursively decidable from finitely many parameters in $\mathcal S$ is itself in $\mathcal S$, so recursive comprehension holds. The remaining first-order and induction axioms hold because the first-order part is the standard $\mathbb N$. [/proofplan] [step:Derive downward closure from recursive comprehension] Assume $(\mathbb N,\mathcal S) \models \mathsf{RCA}_0$. Let $A \in \mathcal S$ and let $B \subseteq \mathbb N$ satisfy $B \le_T A$. By definition of [Turing reducibility](/page/Turing%20Reducibility), there is an oracle Turing machine index $e \in \mathbb N$ such that, for every $n \in \mathbb N$, the computation $\Phi_e^A(n)$ halts and \begin{align*} \Phi_e^A(n)=1 \iff n \in B, \qquad \Phi_e^A(n)=0 \iff n \notin B. \end{align*} Here $\Phi_e^A$ denotes the partial function computed by the $e$th oracle Turing machine with oracle set $A$; the displayed totality and $0$-$1$ output condition are exactly the information supplied by $B \le_T A$. Define two arithmetical predicates with parameter $A$: \begin{align*} \theta_1(n) &:\iff \text{there exists a finite accepting computation of }\Phi_e^A(n)\text{ with output }1,\\ \theta_0(n) &:\iff \text{there exists a finite accepting computation of }\Phi_e^A(n)\text{ with output }0. \end{align*} Both predicates are $\Sigma^0_1$ relative to $A$, because a finite computation transcript is a natural number code and its correctness is primitive recursive relative to the oracle answers from $A$. Since $\Phi_e^A(n)$ halts with exactly one of the two outputs $0$ and $1$, the standard first-order part satisfies \begin{align*} \forall n \in \mathbb N \, \bigl(\theta_1(n) \leftrightarrow \neg \theta_0(n)\bigr). \end{align*} Thus $\theta_1$ is $\Delta^0_1$ relative to the parameter $A$. By the $\Delta^0_1$ comprehension scheme of $\mathsf{RCA}_0$, applied inside $(\mathbb N,\mathcal S)$, there is a set $C \in \mathcal S$ such that \begin{align*} \forall n \in \mathbb N \, \bigl(n \in C \leftrightarrow \theta_1(n)\bigr). \end{align*} By the definition of $\theta_1$, this set is exactly $B$. Hence $B \in \mathcal S$. [/step] [step:Derive closure under Turing join from recursive comprehension] Let $A,B \in \mathcal S$. Define the [Turing join](/page/Turing%20Join) $A \oplus B \subseteq \mathbb N$ by \begin{align*} 2n \in A \oplus B &\iff n \in A,\\ 2n+1 \in A \oplus B &\iff n \in B. \end{align*} The membership relation for $A \oplus B$ is decidable by a bounded arithmetical formula with parameters $A$ and $B$: \begin{align*} m \in A \oplus B \iff \bigl(\exists n \le m \, (m = 2n \wedge n \in A)\bigr) \vee \bigl(\exists n \le m \, (m = 2n+1 \wedge n \in B)\bigr). \end{align*} This is in particular $\Delta^0_1$ relative to $A$ and $B$. By $\Delta^0_1$ comprehension in $(\mathbb N,\mathcal S)$, the set $A \oplus B$ belongs to $\mathcal S$. Therefore $\mathcal S$ is closed under Turing join. Since $\mathsf{RCA}_0$ also proves the existence of at least one set, for instance the empty set defined by $n \ne n$, the second-order part $\mathcal S$ is nonempty. Combining nonemptiness, downward closure, and join closure shows that $\mathcal S$ is a Turing ideal. [/step] [step:Use a Turing ideal to satisfy recursive comprehension] Conversely, assume that $\mathcal S$ is a Turing ideal. We verify the second-order comprehension axiom of $\mathsf{RCA}_0$. Let $A_1,\dots,A_k \in \mathcal S$ be finitely many set parameters. Because a Turing ideal is nonempty, choose a set $A_0 \in \mathcal S$. The empty set is computable from $A_0$, so $\varnothing \le_T A_0$; by downward closure, $\varnothing \in \mathcal S$. If $k=0$, let $P := \varnothing$. If $k \ge 1$, define the finite join $P \subseteq \mathbb N$ recursively by \begin{align*} P := A_1 \oplus A_2 \oplus \cdots \oplus A_k, \end{align*} where any fixed primitive recursive coding of finite joins is used. In the case $k=0$ the preceding paragraph gives $P \in \mathcal S$; in the case $k \ge 1$, closure under binary joins and induction on $k$ give $P \in \mathcal S$. Now suppose the premise of the $\Delta^0_1$ comprehension scheme is satisfied for the given parameters. That is, let $\alpha(n)$ and $\beta(n)$ be $\Sigma^0_1$ formulas, with parameters among $A_1,\dots,A_k$, such that the standard natural numbers satisfy \begin{align*} \forall n \in \mathbb N \, \bigl(\alpha(n) \leftrightarrow \neg \beta(n)\bigr). \end{align*} The set demanded by [Delta-zero-one comprehension](/page/Delta-zero-one%20Comprehension) is the set determined by $\alpha$. Define a set $C \subseteq \mathbb N$ by \begin{align*} C := \{n \in \mathbb N : \alpha(n)\}. \end{align*} We claim that $C \le_T P$. On input $n$, an oracle machine with oracle $P$ simultaneously searches for a witness to $\alpha(n)$ and for a witness to $\beta(n)$. The predicates are $\Sigma^0_1$ relative to $P$, so each proposed witness can be checked effectively using the oracle $P$. Since exactly one of $\alpha(n)$ and $\beta(n)$ holds in the standard model, exactly one search eventually succeeds. The machine outputs $1$ if the first successful search is for $\alpha(n)$ and outputs $0$ if the first successful search is for $\beta(n)$. Thus the characteristic function of $C$ is computable from $P$, so $C \le_T P$. Because $P \in \mathcal S$ and $\mathcal S$ is downward closed under Turing reducibility, we obtain $C \in \mathcal S$. This is precisely the set required by $\Delta^0_1$ comprehension. [guided] The point of this step is that $\Delta^0_1$ definability is the same as effective decidability from the available parameters, provided the model satisfies the equivalence between the positive and negative definitions. We begin with finitely many parameters $A_1,\dots,A_k \in \mathcal S$. A Turing machine can use only one oracle set, so we first package the finitely many parameters into one oracle. There is a small issue when there are no parameters. Since $\mathcal S$ is a Turing ideal, it is nonempty; choose $A_0 \in \mathcal S$. The empty set is computable from $A_0$, so $\varnothing \le_T A_0$. Downward closure gives $\varnothing \in \mathcal S$. Thus, if $k=0$, we may take $P := \varnothing$ and still have $P \in \mathcal S$. If $k \ge 1$, we set \begin{align*} P := A_1 \oplus A_2 \oplus \cdots \oplus A_k. \end{align*} The Turing ideal hypothesis gives $P \in \mathcal S$, because closure under binary joins gives $A_1 \oplus A_2 \in \mathcal S$, then $(A_1 \oplus A_2) \oplus A_3 \in \mathcal S$, and so on. Now consider an instance of $\Delta^0_1$ comprehension with these parameters. In the usual formulation of $\mathsf{RCA}_0$, its premise gives $\Sigma^0_1$ formulas $\alpha(n)$ and $\beta(n)$, using only the oracle information coded by $P$, such that the model satisfies that $\alpha$ defines the complement of $\beta$. Because the first-order part is the standard $\mathbb N$, this premise says \begin{align*} \forall n \in \mathbb N \, \bigl(\alpha(n) \leftrightarrow \neg \beta(n)\bigr). \end{align*} The comprehension instance asks for the set defined by $\alpha$, so we define \begin{align*} C := \{n \in \mathbb N : \alpha(n)\}. \end{align*} Why is $C$ computable from $P$? Given $n$, run two searches in parallel. The first search looks for a witness proving $\alpha(n)$; the second search looks for a witness proving $\beta(n)$. Because $\alpha$ and $\beta$ are $\Sigma^0_1$ relative to $P$, each candidate witness can be checked effectively with oracle $P$. The displayed equivalence says that exactly one of these searches must eventually succeed. If the $\alpha$-search succeeds first, output $1$; if the $\beta$-search succeeds first, output $0$. This gives a total oracle computation deciding whether $n \in C$, and hence \begin{align*} C \le_T P. \end{align*} Finally, $P \in \mathcal S$ and $\mathcal S$ is downward closed under Turing reducibility. Therefore $C \in \mathcal S$. This is exactly the closure demanded by [Delta-zero-one comprehension](/page/Delta-zero-one%20Comprehension) in $\mathsf{RCA}_0$. [/guided] [/step] [step:Verify the remaining axioms in the standard first-order part] It remains to check the non-comprehension axioms of $\mathsf{RCA}_0$. The first-order part of $(\mathbb N,\mathcal S)$ is the standard structure $\mathbb N$, so the basic arithmetic axioms, primitive recursive coding axioms, and elementary properties of addition, multiplication, order, pairing, and finite sequences are true. The induction scheme of $\mathsf{RCA}_0$ also holds in $(\mathbb N,\mathcal S)$. Indeed, let $\psi(n)$ be any formula of the induction class allowed in $\mathsf{RCA}_0$, possibly with parameters from $\mathbb N$ and $\mathcal S$. If \begin{align*} \psi(0) \quad\text{and}\quad \forall n \in \mathbb N\,(\psi(n) \implies \psi(n+1)) \end{align*} hold in $(\mathbb N,\mathcal S)$, then ordinary induction in the standard natural numbers gives \begin{align*} \forall n \in \mathbb N\, \psi(n). \end{align*} This argument uses only that the first-order domain is the actual $\mathbb N$; the set parameters merely determine a genuine subset of $\mathbb N$ defined by $\psi$. Thus $(\mathbb N,\mathcal S)$ satisfies the arithmetic axioms, the induction scheme, and $\Delta^0_1$ comprehension. Therefore $(\mathbb N,\mathcal S) \models \mathsf{RCA}_0$. [/step] [step:Combine the two implications] We have shown that every $\omega$-model of $\mathsf{RCA}_0$ has a second-order part that is nonempty, downward closed under Turing reducibility, and closed under Turing join. Conversely, every Turing ideal $\mathcal S$ supplies exactly the closure needed for $\Delta^0_1$ comprehension, while the standard first-order part $\mathbb N$ supplies the arithmetic and induction axioms. Hence \begin{align*} (\mathbb N,\mathcal S) \models \mathsf{RCA}_0 \iff \mathcal S \text{ is a Turing ideal}. \end{align*} This proves the theorem. [/step]