Definition:Primitive Recursive
From ProofWiki
(Redirected from Definition:Primitive Recursive Function)
Contents |
Definition
Function
A function is primitive recursive if it can be obtained from basic primitive recursive functions using the operations of substitution and primitive recursion a finite number of times.
Set
Let $A \subseteq \N$.
Then $A$ is a primitive recursive set iff its characteristic function $\chi_A$ is a primitive recursive function.
Relation
Let $\mathcal R \subseteq \N^k$ be an $n$-ary relation on $\N^k$.
Then $\mathcal R$ is a primitive recursive relation iff its characteristic function $\chi_\mathcal R$ is a primitive recursive function.
