Definition:Recursive

Definition

Function

A function is recursive if and only if it can be obtained from basic primitive recursive functions using the operations of:

substitution

primitive recursion, and

minimization on a function

a finite number of times.

Set

Let $A \subseteq \N$.

Then $A$ is a recursive set if and only if its characteristic function $\chi_A$ is a recursive function.

Relation

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

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

Also see

• Definition:Recursive Definition