Union of Primitive Recursive Sets

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A, B \subseteq \N$ be subsets of the set of natural numbers $\N$.

Let $A$ and $B$ both be primitive recursive.

Then $A \cup B$, the union of $A$ and $B$, is primitive recursive.


Proof

$A$ and $B$ are primitive recursive, therefore so are their characteristic functions $\chi_A$ and $\chi_B$.

Let $n \in \N$ be a natural number.

Then $n \in A \cup B \iff \chi_A \left({n}\right) + \chi_B \left({n}\right) > 0$.


So:

\(\ds \chi_{A \cup B} \left({n}\right)\) \(=\) \(\ds \operatorname{sgn} \left({\chi_A \left({n}\right) + \chi_B \left({n}\right)}\right)\) Signum Function is Primitive Recursive
\(\ds \) \(=\) \(\ds \operatorname{sgn} \left({\operatorname{add} \left({\chi_A \left({n}\right), \chi_B \left({n}\right)}\right)}\right)\) Addition is Primitive Recursive


Thus $A \cup B$ is defined by substitution from the primitive recursive functions $\operatorname{sgn}$, $\operatorname{add}$, $\chi_A$ and $\chi_B$.

Hence the result.

$\blacksquare$