[proofplan]
We construct an explicit total computable reduction $f : \mathbb{W} \to \mathbb{W}$ from $A$ to $B$. Non-triviality of $B$ provides two fixed words, one inside $B$ and one outside; computability of $A$ provides a total computable decision procedure $\mathbb{1}_A : \mathbb{W} \to \mathbb{W}$. The reduction $f$ routes each input to one of the two fixed words according to the verdict of $\mathbb{1}_A$, so $f(w) \in B \iff w \in A$. The computability of $f$ is by case distinction on the output of $\mathbb{1}_A$, which is exactly the primitive L2 of the register-machine closure lemmas.
[/proofplan]
[step:Fix setup and pick two witnesses from the non-triviality of $B$]
Fix the course alphabet $\Sigma$ with distinguished accept letter $a \in \Sigma$ and write $\mathbb{W} = \Sigma^*$. Let $A \subseteq \mathbb{W}$ be computable, so that by definition the indicator
\begin{align*}
\mathbb{1}_A : \mathbb{W} &\to \mathbb{W},\\
w &\mapsto \begin{cases} a & \text{if } w \in A,\\ \varepsilon & \text{if } w \notin A \end{cases}
\end{align*}
is total computable. Let $B \subseteq \mathbb{W}$ satisfy $B \neq \varnothing$ and $B \neq \mathbb{W}$. Non-triviality yields two witnesses:
- since $B \neq \varnothing$, fix $v \in B$;
- since $B \neq \mathbb{W}$, fix $u \in \mathbb{W} \setminus B$, i.e. $u \notin B$.
Recall (from Step 1 of the proof of [Many-One Reducibility Is a Preorder](/theorems/???), where the definition is introduced) that a *many-one reduction* from $A$ to $B$ is a total computable function $f : \mathbb{W} \to \mathbb{W}$ such that $w \in A \iff f(w) \in B$ for every $w \in \mathbb{W}$; in this case we write $A \leq_m B$.
[/step]
[step:Define the reduction $f$ by routing through $\mathbb{1}_A$]
Define
\begin{align*}
f : \mathbb{W} &\to \mathbb{W}, \\
w &\mapsto \begin{cases} v & \text{if } w \in A, \\ u & \text{if } w \notin A. \end{cases}
\end{align*}
[claim:$f$ is total computable]
A register machine $M_f$ witnessing $f$ runs as follows. On input $w$ in register $0$:
(a) Run the register machine for $\mathbb{1}_A$ on $w$. Since $\mathbb{1}_A$ is total computable, this halts with $a$ in register $0$ if $w \in A$ and $\varepsilon$ in register $0$ if $w \notin A$.
(b) Case-distinguish on register $0$ using the case-distinction primitive (L2 of Step 4 of the proof of [Recursive Implies Computable](/theorems/1817)): if register $0$ is $a$, overwrite register $0$ with the constant $v$ (the constant-$v$ machine is total computable by L0 of Step 3 of the proof of [Recursive Implies Computable](/theorems/1817)); if register $0$ is $\varepsilon$, overwrite register $0$ with the constant $u$. Halt.
Formally, $f = g \circ \mathbb{1}_A$ where $g : \mathbb{W} \to \mathbb{W}$ is the case-distinction $g(a) = v$, $g(\varepsilon) = u$ (total computable by L2). Composition preserves total computability (L1 of Step 4 of the proof of [Recursive Implies Computable](/theorems/1817)), so $f$ is total computable.
[/claim]
[/step]
[step:Verify the biconditional $w \in A \iff f(w) \in B$]
We check both implications.
$(\Rightarrow)$ If $w \in A$, then by definition $f(w) = v$, and $v \in B$ by choice of $v$. Hence $f(w) \in B$.
$(\Leftarrow)$ Contrapositively, if $w \notin A$, then by definition $f(w) = u$, and $u \notin B$ by choice of $u$. Hence $f(w) \notin B$.
Combining, $w \in A \iff f(w) \in B$ for every $w \in \mathbb{W}$.
[guided]
The symmetry of the argument is complete: the two witnesses $v, u$ play perfectly opposite roles.
*Why is the forward direction $w \in A \Rightarrow f(w) \in B$ automatic?* Because on inputs $w \in A$ the reduction routes to the fixed word $v$, and by *choice* $v \in B$. No computation other than evaluating $\mathbb{1}_A$ is involved.
*Why is the reverse direction forced by the $u \notin B$ choice?* We use the contrapositive "$w \notin A \Rightarrow f(w) \notin B$", which follows because on inputs $w \notin A$ the reduction routes to $u$, and $u$ was chosen to lie *outside* $B$.
*What role does non-triviality of $B$ play?* It is exactly what guarantees the two witnesses exist. If $B = \varnothing$, no $v \in B$ exists; if $B = \mathbb{W}$, no $u \notin B$ exists. In either trivial case the theorem fails: $\mathbb{W} \not\leq_m \varnothing$ (any reduction into $\varnothing$ would have empty image, but "$w \in \mathbb{W} \iff f(w) \in \varnothing$" reads "true $\iff$ false") and similarly $\varnothing \not\leq_m \mathbb{W}$. The two trivial sets $\varnothing$ and $\mathbb{W}$ form the bottom and top of the $\leq_m$ order below computable sets, and the present theorem says: apart from these extremes, every non-trivial set is $\leq_m$-above every computable set.
*Why doesn't the argument give anything stronger?* Because $f$ takes only two values $\{u, v\}$, its image is a two-element set. It cannot, for example, reduce a non-computable set to $B$: the structure of the reduction is entirely carried by the decision procedure for $A$, and $A$ must be decidable for that to exist.
[/guided]
[/step]
[step:Conclude]
The total computable function $f$ of Step 2 satisfies $w \in A \iff f(w) \in B$ for all $w \in \mathbb{W}$ by Step 3. Therefore $A \leq_m B$, as claimed.
[/step]
