[proofplan] For the forward direction, a computable $X$ has a computable indicator, and both $X$ and its complement $X^c$ are computable (swap the roles of $a$ and $\varepsilon$ in the indicator). Computable sets are computably enumerable (exhibit as domain of the computable indicator — or equivalently, as the domain of a partial function that equals $\varepsilon$ on $X$ and diverges off $X$), hence by [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824) both $X$ and $X^c$ are $\Sigma_1$; so $X \in \Sigma_1 \cap \Pi_1 = \Delta_1$. For the reverse direction, let $X$ be $\Delta_1$: both $X = p(Y_1)$ and $X^c = p(Y_2)$ for computable witness sets $Y_1, Y_2$. We use dovetailing to search in parallel for a witness in $Y_1$ or $Y_2$: define a computable function $F(w, v)$ that tests, for an input $v$ that encodes both a choice of "which witness set to probe" and a candidate for the witness, whether the probe succeeds. Because $w$ lies in exactly one of $X$ and $X^c$, at least one $Y_i$ contains a pair over $w$, so the minimisation of $F$ is total. Reading off the parity bit of the minimiser tells us which of $X$ or $X^c$ $w$ belongs to, giving a total computable indicator for $X$. [/proofplan] [step:Fix definitions of the $\Sigma_1$, $\Pi_1$, and $\Delta_1$ classes] Retain notation from Step 1 of the proof of [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824): $\mathbb{W} = \Sigma^*$, $a \in \Sigma$ is the fixed distinguished accept letter, and for $X \subseteq \mathbb{W}^k$ we have \begin{align*} X \text{ is } \Sigma_1 &\iff X = p(Y) \text{ for some computable } Y \subseteq \mathbb{W}^{k+1}, \\ X \text{ is } \Pi_1 &\iff X^c \text{ is } \Sigma_1, \\ X \text{ is } \Delta_1 &\iff X \text{ is both } \Sigma_1 \text{ and } \Pi_1. \end{align*} Here $X^c = \mathbb{W}^k \setminus X$. Recall further that a set $X \subseteq \mathbb{W}^k$ is *computable* iff its indicator $\mathbb{1}_X : \mathbb{W}^k \to \mathbb{W}$ is total computable (with values in $\{a, \varepsilon\}$). The complement $X^c$ is computable iff $X$ is, because $\mathbb{1}_{X^c} = \mathrm{flip} \circ \mathbb{1}_X$ where $\mathrm{flip}$ is the computable swap of $a$ and $\varepsilon$ (see the Claim "$\chi$ is total and computable" in Step 3 of the proof of [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824)). [/step] [step:Prove $(\Rightarrow)$: computable implies $\Delta_1$] Let $X \subseteq \mathbb{W}^k$ be computable. We show $X \in \Sigma_1$ and $X \in \Pi_1$. *$X$ is computably enumerable.* Define \begin{align*} \psi : \mathbb{W}^k &\rightharpoonup \mathbb{W}, \\ w &\mapsto \begin{cases} \varepsilon & \text{if } w \in X, \\ \uparrow & \text{if } w \notin X. \end{cases} \end{align*} A register machine $M_\psi$ witnessing $\psi$ runs $\mathbb{1}_X$ (computable by hypothesis) on $w$, reads the result; if $a$, erases register $0$ and halts (output $\varepsilon$); if $\varepsilon$, enters a divergent loop. The construction is the same as the Claim "$f$ is computable" in Step 2 of the proof of [The Halting Problem](/theorems/1823), with the roles of $a$ and $\varepsilon$ adjusted. Hence $\psi$ is computable with $\operatorname{dom} \psi = X$, so $X$ is computably enumerable. By [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), $X$ is $\Sigma_1$. *$X^c$ is computably enumerable.* By Step 1, $X^c$ is computable, so the argument above with $X$ replaced by $X^c$ gives that $X^c$ is computably enumerable, hence $\Sigma_1$. By definition, this means $X$ is $\Pi_1$. Combining, $X$ is $\Sigma_1 \cap \Pi_1 = \Delta_1$. [/step] [step:Prove $(\Leftarrow)$: $\Delta_1$ implies computable — set up witness sets] Let $X \subseteq \mathbb{W}^k$ be $\Delta_1$. By definition, $X$ is $\Sigma_1$ and $X^c$ is $\Sigma_1$, so there exist computable sets $Y_1, Y_2 \subseteq \mathbb{W}^{k+1}$ with \begin{align*} X &= p(Y_1) = \{w : \exists v, \; (w, v) \in Y_1\}, \\ X^c &= p(Y_2) = \{w : \exists v, \; (w, v) \in Y_2\}. \end{align*} Since every $w \in \mathbb{W}^k$ lies in exactly one of $X$ and $X^c$, we have: for every $w \in \mathbb{W}^k$, there exists $v \in \mathbb{W}$ such that $(w, v) \in Y_1 \cup Y_2$. Our goal is to exploit this existential guarantee to produce a total computable indicator for $X$. The plan is: (i) fix a computable bijection $\mathbb{W} \to \{1, 2\} \times \mathbb{W}$ that lets us decode an input word $u$ into "which witness set to probe" and "what candidate to probe with"; (ii) define a computable function that tests the probe; (iii) apply minimisation, which is total by the existential guarantee; (iv) read off the decoded probe choice to determine membership in $X$. [/step] [step:Fix a computable pairing that decomposes a word into a tag and a candidate] Fix any letter $a_0 \in \Sigma$ (for concreteness take $a_0 = a$, the distinguished accept letter). Define a computable decoding \begin{align*} \pi : \mathbb{W} &\to \{1, 2\} \times \mathbb{W}, \\ u &\mapsto \begin{cases} (1, u') & \text{if } u = a_0 \cdot u' \text{ (i.e. $u$ begins with letter $a_0$)}, \\ (2, u') & \text{if } u = u' \text{ with $u$ not beginning with $a_0$, including } u = \varepsilon. \end{cases} \end{align*} We clarify: the choice of decoding above is one concrete realisation, and for the proof we need only (a) a total computable function $\pi$ that extracts a tag in $\{1, 2\}$ and a residual word from each input, and (b) the surjectivity property that for every $i \in \{1, 2\}$ and every $v \in \mathbb{W}$, there is some $u \in \mathbb{W}$ with $\pi(u) = (i, v)$. The decoding above has both properties: it is computed by a register machine that tests the first letter of the input and either strips it off (tag $1$) or leaves the input intact (tag $2$); every $(1, v)$ is hit by $u = a_0 \cdot v$, and every $(2, v)$ is hit by $u = v$ if $v$ does not begin with $a_0$ (or by extending $v$ to a word that does not begin with $a_0$ via a fresh leading letter other than $a_0$ — but this case requires $|\Sigma| \ge 2$; if $|\Sigma| = 1$, all non-empty words begin with $a_0$, and we adjust by tagging on position parity instead). *Robustification for $|\Sigma| \ge 2$.* Assume $|\Sigma| \ge 2$ so the decoding above is surjective in the required sense. If $|\Sigma| = 1$, replace the decoding by one based on length parity: write $\#u$ in binary via the order-isomorphism $\# : \mathbb{W} \to \mathbb{N}$ of [Shortlex Order and Computable Successor](/theorems/1815) and decompose $\#u = 2 m + i$ with $i \in \{0, 1\}$; set $\pi(u) = (i + 1, v)$ where $v$ is the unique word with $\#v = m$. This is computable (arithmetic on $\#$, which is a computable bijection, is computable via [Shortlex Order and Computable Successor](/theorems/1815)), and hits every $(i, v)$ via $u = \#^{-1}(2 \#v + i - 1)$. Either way, we have a total computable $\pi : \mathbb{W} \to \{1, 2\} \times \mathbb{W}$ that is surjective onto the pair space. Write $\pi(u) = (i(u), v(u))$; the component maps $i : \mathbb{W} \to \{1, 2\}$ and $v : \mathbb{W} \to \mathbb{W}$ are both total computable. [/step] [step:Define the dovetailed probe function $F$ and verify its computability] Define \begin{align*} F : \mathbb{W}^{k+1} &\to \mathbb{W}, \\ (w, u) &\mapsto \begin{cases} \varepsilon & \text{if } (w, v(u)) \in Y_{i(u)}, \\ a & \text{otherwise}. \end{cases} \end{align*} The condition "$(w, v(u)) \in Y_{i(u)}$" means: if $i(u) = 1$, the pair $(w, v(u))$ is in $Y_1$; if $i(u) = 2$, the pair $(w, v(u))$ is in $Y_2$. [claim:$F$ is total and computable] On input $(w, u)$ in registers $0, \ldots, k$, a register machine $M_F$ proceeds as follows: (a) Save a master copy of $w$ into scratch registers $R_1, \ldots, R_k$. (b) Compute $\pi(u)$ using the total computable $\pi$ from Step 4, storing the tag $i(u) \in \{1, 2\}$ into a scratch register $R_i$ and the residual $v(u)$ into a scratch register $R_v$. (c) Branch on $R_i$: - If $R_i = 1$: restore $w$ from $R_1, \ldots, R_k$ into input registers $0, \ldots, k - 1$, copy $R_v$ into input register $k$, and run the machine $M_{\mathbb{1}_{Y_1}}$ witnessing the (total) indicator of the computable set $Y_1$. It halts with register $0$ holding $a$ (if $(w, v(u)) \in Y_1$) or $\varepsilon$ (otherwise). - If $R_i = 2$: the same with $Y_1$ replaced by $Y_2$. The branching is a hard-wired finite case distinction on $R_i$. (d) *Flip the result.* After the indicator machine halts, read the single letter in register $0$: if it is $a$ (the set membership held), erase register $0$ and halt (output $\varepsilon$); if it is $\varepsilon$ (the set membership failed), write $a$ to register $0$ and halt (output $a$). Each step is a bounded computation plus calls to total computable sub-routines. Hence $M_F$ is a total register machine and computes $F$. So $F$ is total and computable. [/claim] The key design feature of $F$: its value $\varepsilon$ on $(w, u)$ corresponds to "$u$ decodes to a successful probe against one of the two witness sets", and the convention that $\mu$ searches for the shortlex-least $u$ with $F(w, u) = \varepsilon$ matches this "find a witness" semantics. [/step] [step:Show that $\mu F$ is total on $\mathbb{W}^k$] Apply minimisation to $F$: \begin{align*} g : \mathbb{W}^k &\rightharpoonup \mathbb{W}, \\ w &\mapsto (\mu F)(w) = \min \{u \in \mathbb{W} : F(w, u) = \varepsilon\} \end{align*} (where $\min$ is the shortlex-minimum and the "defined on all earlier $u'$" clause in the definition of $\mu$ is vacuous because $F$ is total). [claim:$g$ is computable] $g = \mu F$ is the minimisation of the total computable $F$, hence computable by L3 in Step 6 of the proof of [Recursive Implies Computable](/theorems/1817). [/claim] [claim:$g$ is total, i.e. $\operatorname{dom} g = \mathbb{W}^k$] Fix $w \in \mathbb{W}^k$. Because $X \cup X^c = \mathbb{W}^k$, either $w \in X$ or $w \in X^c$. - If $w \in X = p(Y_1)$, there exists $v^\star \in \mathbb{W}$ with $(w, v^\star) \in Y_1$. By Step 4's surjectivity, there exists $u^\star \in \mathbb{W}$ with $\pi(u^\star) = (1, v^\star)$, i.e. $i(u^\star) = 1$ and $v(u^\star) = v^\star$. Then $F(w, u^\star) = \varepsilon$ since $(w, v(u^\star)) = (w, v^\star) \in Y_1 = Y_{i(u^\star)}$. - If $w \in X^c = p(Y_2)$, the analogous argument with tag $2$ produces $u^\star \in \mathbb{W}$ with $\pi(u^\star) = (2, v^\star)$ where $(w, v^\star) \in Y_2$, and $F(w, u^\star) = \varepsilon$. In either case the set $\{u : F(w, u) = \varepsilon\}$ is non-empty. The shortlex-minimum of a non-empty subset of $(\mathbb{W}, <)$ exists by well-orderedness (see [Shortlex Order and Computable Successor](/theorems/1815)), so $g(w) = (\mu F)(w)$ is defined. [/claim] [/step] [step:Define the indicator $\mathbb{1}_X$ via the parity of $g$ and conclude] Define \begin{align*} \mathbb{1}_X : \mathbb{W}^k &\to \mathbb{W}, \\ w &\mapsto \begin{cases} a & \text{if } i(g(w)) = 1, \\ \varepsilon & \text{if } i(g(w)) = 2. \end{cases} \end{align*} Here $i(\cdot)$ is the total computable tag-extraction map from Step 4. [claim:$\mathbb{1}_X$ is total computable] $\mathbb{1}_X$ is the composition: first $g$, then $i$, then a hard-wired case map $\{1, 2\} \to \{a, \varepsilon\}$. The function $g$ is total (Step 6), $i$ is total computable (Step 4), and the case map is a fixed finite sub-routine. Total computable functions compose to total computable functions (L1 in Step 4 of the proof of [Recursive Implies Computable](/theorems/1817)); the fixed case map is computable by inspection. Hence $\mathbb{1}_X$ is total computable. [/claim] [claim:$\mathbb{1}_X(w) = a$ iff $w \in X$] Let $w \in \mathbb{W}^k$ and let $u^\star := g(w)$, so $F(w, u^\star) = \varepsilon$. By definition of $F$, this means $(w, v(u^\star)) \in Y_{i(u^\star)}$. - If $i(u^\star) = 1$: $(w, v(u^\star)) \in Y_1$, so $w \in p(Y_1) = X$. - If $i(u^\star) = 2$: $(w, v(u^\star)) \in Y_2$, so $w \in p(Y_2) = X^c$, i.e. $w \notin X$. Because $X$ and $X^c$ are disjoint, at most one of these can hold; because $w \in X \cup X^c$, exactly one does. Hence \begin{align*} \mathbb{1}_X(w) = a &\iff i(g(w)) = 1 \iff w \in X, \\ \mathbb{1}_X(w) = \varepsilon &\iff i(g(w)) = 2 \iff w \in X^c \iff w \notin X. \end{align*} [/claim] Hence $\mathbb{1}_X$ is a total computable indicator for $X$, so $X$ is computable. This completes $(\Leftarrow)$. [/step] [step:Conclude] By Step 2 ($\Rightarrow$), every computable set is $\Delta_1$. By Steps 3–7 ($\Leftarrow$), every $\Delta_1$ set is computable. Therefore $X \subseteq \mathbb{W}^k$ is computable if and only if $X$ is $\Delta_1$. [/step]