PlanetMath: primitive recursive function

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

primitive recursive function

(Definition)

Notation and Terminology
$\boldsymbol{F} = \bigcup \lbrace F_k \mid k \in \mathbb{N} \rbrace$ , where for each $k \in \mathbb{N}$ , $F_k = \lbrace f \mid f \colon \mathbb{N}^{k} \to \mathbb{N} \rbrace$ . For each $k \in \mathbb{N}$ , $\boldsymbol{z}(k) = 0$ , $\boldsymbol{s}(k) = k+1$ , and for each $m \le k$ and $\langle n_1, n_2, \ldots, n_k \rangle \in \mathbb{N}^{k}$ , $\boldsymbol{p}^{k}_{m}(n_1, n_2, \ldots, n_k) = n_m$ . The functions $\boldsymbol{z}$ and $\boldsymbol{s}$ are the zero and successor functions, respectively; the functions $\boldsymbol{p}^{k}_{m}$ are the projection functions.

Definition (Primitive Recursive Function)
The set, PR, primitive recursive functions is the smallest subset

of $\boldsymbol{F}$ such that:

1.: $\boldsymbol{z} \in P$ ;
2.: $\boldsymbol{s} \in P$ ;
3.: for each $k \in \mathbb{N}$ and $m\le k$ , $\boldsymbol{p}^{k}_{m}\, \in P$ ;

and

4.

(

is closed under composition)
If $\lbrace g_1, g_2, \ldots, g_m \rbrace \subseteq P \,\cap \,F_{k}$ and $h \in P \,\cap \,F_m$ , then $f \in P \,\cap \,F_{k}$ , where $\\ [2ex] f(n_1, n_2,\ldots, n_k) = h(g_1(n_1, n_2, \ldots, n_k), g_2(n_1, n_2, \ldots, n_k), \ldots, g_m(n_1, n_2, \ldots, n_k)) \\ [2ex]$ for $\langle n_1, n_2,\ldots, n_k \rangle \in \mathbb{N}^{k}$ ;

5.

(

is closed under primitive recursion)
If $g \in P \,\cap \,F_{k}$ and $h \in P \,\cap \,F_{k+2}$ , then $f \in P \,\cap \,F_{k+1}$ , where

$\displaystyle f(n_1, n_2,\ldots, n_k, 0)$	$\displaystyle =$	$\displaystyle g(n_1, n_2, \ldots, n_k)$
$\displaystyle f(n_1, n_2,\ldots, n_k, \boldsymbol{s}(n))$	$\displaystyle =$	$\displaystyle h(n_1, n_2, \ldots, n_k, n, f(n_1, n_2, \ldots, n_k, n))$

for $\langle n_1, n_2,\ldots, n_k \rangle \in \mathbb{N}^{k}$ and $n \in \mathbb{N}$ .

"primitive recursive function" is owned by ratboy. [ full author list (2) | owner history (1) ]

(view preamble | get metadata)

Other names:

primitive recursive function

Attachments:: characterization of primitive recursive functions of one variable (Theorem) by rspuzio

Log in to rate this entry.
(view current ratings)

Cross-references: primitive recursion, composition, closed under, subset, recursive function, projection, successor, functions

This is version 11 of primitive recursive function, born on 2002-03-23, modified 2007-10-25.
Object id is 2801, canonical name is PrimitiveRecursive.
Accessed 8594 times total.

Classification:

AMS MSC:

03D20 (Mathematical logic and foundations :: Computability and recursion theory :: Recursive functions and relations, subrecursive hierarchies)

Pending Errata and Addenda

None.[ View all 2 ]

Discussion

forum policy

No messages.

Interact