Definition:Recursively Defined Mapping

From ProofWiki
Jump to: navigation, search

Definition

Natural Numbers

Let $p \in \N$ be a natural number.

Let $S = \left\{{x \in \N: p \le x}\right\}$.


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: f \left({x}\right) = \begin{cases} a & : x = p \\ g \left({f \left({n}\right)}\right) & : x = n + 1 \end{cases}$

for $a \in T$.


Then $f$ is said to be recursively defined on $S$.


Peano Structure

Let $\left({P, 0, s}\right)$ 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: f \left({x}\right) = \begin{cases} a & : x = 0 \\ g \left({f \left({n}\right)}\right) & : x = s \left({n}\right) \end{cases}$

where $a \in T$.


Then $f$ is said to be recursively defined on $P$.


Naturally Ordered Semigroup

Let $\left({S, \circ, \preceq}\right)$ be a naturally ordered semigroup.

Let $p \in S$.

Let $S' = \left\{{x \in S: p \preceq x}\right\}$.


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': f \left({x}\right) = \begin{cases} a & : x = p \\ g \left({f \left({n}\right)}\right) & : x = n \circ 1 \end{cases}$

where $a \in T$.


Then $f$ is said to be recursively defined on $S'$.


Minimal Infinite Successor Set

Let $\omega$ be the minimal infinite successor 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: f \left({x}\right) = \begin{cases} a & : x = 0 \\ g \left({f \left({n}\right)}\right) & : x = n^+ \end{cases}$

where $n^+$ is the successor set of $n$.


Then $f$ is said to be recursively defined on $\omega$.


Also see