Definition:Primitive Recursive

From ProofWiki
Jump to navigation Jump to search

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 if and only if its characteristic function $\chi_A$ is a primitive recursive function.


Relation

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


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