Definition:Recursively Defined Mapping
Definition
Natural Numbers
Let $p \in \N$ be a natural number.
Let $S = \set {x \in \N: p \le x}$.
Let $T$ be a set.
Let $g: T \to T$ be a mapping.
Let $f: S \to T$ be the mapping defined as:
- $\forall x \in S: \map f x = \begin {cases} a & : x = p \\ \map g {\map f n} & : x = n + 1 \end {cases}$
for $a \in T$.
Then $f$ is said to be recursively defined on $S$.
Peano Structure
Let $\struct {P, 0, s}$ be a Peano structure.
Let $T$ be a set.
Let $g: T \to T$ be a mapping.
Let $f: P \to T$ be the mapping defined as:
- $\forall x \in P: \map f x = \begin {cases} a & : x = 0 \\ \map g {\map f n} & : x = \map s n \end {cases}$
where $a \in T$.
Then $f$ is said to be recursively defined on $P$.
Naturally Ordered Semigroup
Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.
Let $p \in S$.
Let $S' = \set {x \in S: p \preceq x}$.
Let $T$ be a set.
Let $g: T \to T$ be a mapping.
Let $f: S' \to T$ be the mapping defined as:
- $\forall n \in S': \map f x = \begin {cases} a & : x = p \\ \map g {\map f n} & : x = n \circ 1 \end {cases}$
where $a \in T$.
Then $f$ is said to be recursively defined on $S'$.
Minimally Inductive Set
Let $\omega$ be the minimally inductive set.
Let $T$ be a set.
Let $a \in T$.
Let $g: T \to T$ be a mapping.
Let $f: \omega \to T$ be the mapping defined as:
- $\forall x \in \omega: \map f x = \begin {cases} a & : x = 0 \\ \map g {\map f n} & : x = n^+ \end {cases}$
where $n^+$ is the successor set of $n$.
Then $f$ is said to be recursively defined on $\omega$.
Examples
Factorial
The facorial of a positive integer $n$ can be defined recursively as:
- $\map f n = \begin {cases} 0 & : n = 1 \\ n \map f {n - 1} & : n > 1 \end {cases}$
Also known as
A recursive definition is also known as:
Also see
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): recursive
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): recursive