Union of Recursively Enumerable Sets

Theorem

Let $S, T \subseteq \N$ be recursively enumerable sets.

Then $S \cup T$ is recursively enumerable.

Proof

Suppose $S = \empty$.

Then by Union with Empty Set:

$S \cup T = T$

which is recursively enumerable by assumption.

$\Box$

Suppose $T = \empty$.

For the same reason:

$S \cup T = S$

which is also recursively enumerable by assumption.

$\Box$

Now, suppose neither $S$ nor $T$ is empty.

By Recursively Enumerable Set is Image of Primitive Recursive Function/Corollary, there exist primitive recursive $f, g : \N \to \N$ such that:

$S = \Img f$

$T = \Img g$

Define:

$\map h {x, c} = \begin{cases}

\map f x & : c = 0 \\ \map g x & : \text{otherwise} \end{cases}$

By:

• Equality Relation is Primitive Recursive
• Definition by Cases is Primitive Recursive/Corollary

$h$ is a primitive recursive function.

By Primitive Recursive Function is Total Recursive Function, it is thus a recursive function.

It remains to be shown that $S \cup T = \Img h$.

Let $x \in S \cup T$.

Then $x \in \Img f$ or $x \in \Img g$.

If $x \in \Img f$, then there is some $z \in \N$ such that $\map f z = x$.

Therefore, $\map h {z, 0} = x$.

Likewise, if $x \in \Img g$, there is some $z \in \N$ such that $\map g z = x$.

Therefore, $\map h {z, 1} = x$.

Thus, $S \cup T \subseteq \Img h$.

Now, $x \in \Img h$.

Then, there are $z, c \in \N$ such that:

$\map h {z, c} = x$

Depending on $c$, either:

$x = \map f z$

or:

$x = \map g z$

In either case, $x \in \Img f \cup \Img g$.

Therefore, $\Img h \subseteq S \cup T$.

Hence, by definition of set equality:

$S \cup T = \Img h$

Therefore, by definition, $S \cup T$ is recursively enumerable.

$\blacksquare$