Set Operations on Primitive Recursive Relations

From ProofWiki
Jump to navigation Jump to search


Theorem

Let $\mathcal R_1 \subseteq N^k$ and $\mathcal R_2 \subseteq N^k$ be $k$-ary relations on $N^k$.

Let $\mathcal R_1$ and $\mathcal R_2$ be primitive recursive.

Then the following are all primitive recursive relations:

  • $\mathcal T = \neg \mathcal R_1$
  • $\mathcal U = \mathcal R_1 \land \mathcal R_2$
  • $\mathcal V = \mathcal R_1 \lor \mathcal R_2$


Proof

By hypothesis, the characteristic functions $\chi_{\mathcal R_1}, \chi_{\mathcal R_2}$ of $\mathcal R_1$ and $\mathcal R_2$ are primitive recursive.

Then we have that the characteristic functions of $\mathcal T, \mathcal U, \mathcal V$ are given by:

  • $\chi_\mathcal T = \overline{\operatorname{sgn}} \left({\chi_{\mathcal R_1}}\right)$
  • $\chi_\mathcal U = \chi_{\mathcal R_1} \times \chi_{\mathcal R_2}$
  • $\chi_\mathcal V = \operatorname{sgn} \left({\chi_{\mathcal R_1} + \chi_{\mathcal R_2}}\right)$

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

Hence the result.

$\blacksquare$