Set Operations on Primitive Recursive Relations
Jump to navigation
Jump to search
This page has been identified as a candidate for refactoring of basic complexity. In particular: Three separate pages Until this has been finished, please leave {{Refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code. |
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$