Set Operations on Primitive Recursive Relations

From ProofWiki
Jump to navigation Jump to search


Theorem

Let $\RR_1 \subseteq N^k$ and $\RR_2 \subseteq N^k$ be $k$-ary relations on $N^k$.

Let $\RR_1$ and $\RR_2$ be primitive recursive.

Then the following are all primitive recursive relations:

$\TT = \neg \RR_1$
$\UU = \RR_1 \land \RR_2$
$\VV = \RR_1 \lor \RR_2$


Proof

By hypothesis, the characteristic functions $\chi_{\RR_1}, \chi_{\RR_2}$ of $\RR_1$ and $\RR_2$ are primitive recursive.

Then we have that the characteristic functions of $\TT, \UU, \VV$ are given by:

$\chi_\TT = \map {\overline \sgn} {\chi_{\RR_1} }$
$\chi_\UU = \chi_{\RR_1} \times \chi_{\RR_2}$
$\chi_\VV = \map {\overline \sgn} {\chi_{\RR_1} + \chi_{\RR_2} }$

Compare Complement of Primitive Recursive Set, Intersection of Primitive Recursive Sets and Union of Primitive Recursive Sets.

Hence the result.

$\blacksquare$