Set is Recursive iff Set and Complement are Recursively Enumerable

== Theorem ==
Let $S \subseteq \N$ be a set of natural numbers.
Then:
:$S$ is a recursive set
:
:$S$ and $\N \setminus S$ are recursively enumerable sets.
== Proof ==
=== Necessary Condition ===
By Complement of Primitive Recursive Set, $\N \setminus S$ is a recursive set as well.
Thus, it suffices to show that every recursive $S$ is recursively enumerable.
By definition of recursive set, the characteristic function $\chi_S$ is recursive.
Define:
:$\map f x = \map {\mu z} {\map {\overline {\operatorname{sgn}}} {\map {\chi_S} x}}$
As $f$ is obtained by substitution and minimization, and:
* Signum Complement Function is Primitive Recursive
* Primitive Recursive Function is Total Recursive Function
it follows that $f$ is a recursive function.
We now show that $\Dom f = S$.
Suppose $x \in S$.
Then, by definition of characteristic function:
:$\map {\chi_S} x = 1$
Thus, by definition of the signum-bar function:
:$\map {\overline {\operatorname{sgn}}} {\map {\chi_S} x} = 0$
Therefore, by the definition of minimization:
:$\map {\mu z} {\map {\overline {\operatorname{sgn}}} {\map {\chi_S} x}} = 0$
as the previous equation is true for every value of $z$, and $0$ is the smallest natural number.
Hence, $f$ is defined at $x$, so $x \in \Dom f$.
Now, suppose $x \notin S$.
By definition of characteristic function:
:$\map {\chi_S} x = 0$
By definition of the signum-bar function:
:$\map {\overline {\operatorname{sgn}}} {\map {\chi_S} x} = 1$
Therefore, by the definition of minimization:
:$\map {\mu z} {\map {\overline {\operatorname{sgn}}} {\map {\chi_S} x}}$ is undefined
as there is no $z$ that causes the function to be equal to $0$.
Hence, $x \notin \Dom f$.
As we have shown $x \in S \iff x \in \Dom f$, it follows that $S = \Dom f$.
By Set is Recursively Enumerable iff Domain of Recursive Function, $S$ is then recursively enumerable.
=== Sufficient Condition ===
Let $S$ and $\N \setminus S$ be recursively enumerable.
Suppose $S$ is the empty set.
Then $\map {\chi_S} x = 0$ is the characteristic function of $S$.
In that case, $\chi_S$ is recursive by:
* Constant Function is Primitive Recursive
* Primitive Recursive Function is Total Recursive Function
and so $S$ is recursive by definition.
Suppose instead that $\N \setminus S$ is the empty set.
Then $\map {\chi_S} x = 1$ is the characteristic function of $S$.
By the same argument, it follows that $S$ is recursive.
Now, suppose neither $S$ nor $\N \setminus S$ are empty.
Then, Recursively Enumerable Set is Image of Primitive Recursive Function/Corollary applies.
Therefore, there exist primitive recursive $f, g : \N \to \N$ such that:
:$S = \Img f$
:$\N \setminus S = \Img g$
Define:
:$\map h x = \map {\mu z} {x = \map f z \lor x = \map g z}$
By:
* Equality Relation is Primitive Recursive
* Set Operations on Primitive Recursive Relations
* Minimization on Relation Equivalent to Minimization on Function
$h$ is a recursive function.
Finally, define:
:$\map {\chi_S} x = \map {\chi_{\operatorname{eq}}} {x, \map f {\map h x}}$
$\chi_S$ is recursive, as it is defined by substitution on recursive functions.
We now show that $\chi_S$ is the characteristic function of $S$.
Suppose $x \in S$.
Then, $x \in \Img f$ and $x \notin \Img g$.
That is:
:There is some $z \in \N$ such that $\map f z = x$
:There is no $z \in \N$ such that $\map g z = x$
Therefore, $\map h x$ is defined to be the least $z$ such that $\map f z = x$.
Thus, $\map {\chi_S} x = 1$, as expected.
Suppose $x \notin S$.
Then, conversely, $x \notin \Img f$ and $x \notin \Img g$.
The same argument applies, and:
:There is no $z \in \N$ such that $\map f z = x$
:$\map h x$ is the least $z$ such that $\map g z = x$, which necessarily exists
Thus, $\map f {\map h z} \ne x$, and $\map {\chi_S} x = 0$.
Since the characteristic function of $S$ is recursive, $S$ is a recursive set by definition.
Category:Recursion Theory