# Definition:Basic Primitive Recursive Function

## Definition

The basic primitive recursive functions are:

### Zero Function

The zero function $\Zero: \N \to \N$ is a basic primitive recursive function, defined as:

$\forall n \in \N: \map \Zero n = 0$

### Successor Function

The successor function $\Succ: \N \to \N$ is a basic primitive recursive function, defined as:

$\forall n \in \N: \map \Succ n = n + 1$

### Projection Function

The projection functions $\pr_j^k: \N^k \to \N$ are basic primitive recursive functions, defined as:

$\forall \tuple {n_1, n_2, \ldots, n_k} \in \N^k: \map {\pr_j^k} {n_1, n_2, \ldots, n_k} = n_j$[1]

where $j \in \closedint 1 k$.

### Identity Function

The identity function $I_\N: \N \to \N$ is a basic primitive recursive function, defined as:

$\forall n \in \N: \map {I_\N} n = n$

Note that this is an implementation of the projection function:

$\pr_1^1: \N \to \N: \map {\pr_1^1} {n_1} = n_1$

## Also see

### URM Computability

are each URM computable by a single-instruction URM program.

## Notation

1. The usual notation for the projection function omits the superscript that defines the arity of the particular instance of the projection in question at the time, for example: $\pr_j$. However, in the context of computability theory, it is a very good idea to be completely certain of exactly which projection function is under discussion.