Definition:Primitive Recursive/Relation

From ProofWiki
Jump to: navigation, search

Definition

Let $\mathcal R \subseteq \N^k$ be an $n$-ary relation on $\N^k$.


Then $\mathcal R$ is a primitive recursive relation if and only if its characteristic function $\chi_\mathcal R$ is a primitive recursive function.