Principle of Recursive Definition/Proof 4

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\N$ be the natural numbers.

Let $T$ be a class (which may be a set).

Let $a \in T$.

Let $g: T \to T$ be a mapping.


Then there exists exactly one mapping $f: \N \to T$ such that:

$\forall x \in \N: \map f x = \begin{cases} a & : x = 0 \\ \map g {\map f n} & : x = n + 1 \end{cases}$


Proof

From the Principle of Recursive Definition: Strong Version:

Let $\omega$ denote the natural numbers as defined by the von Neumann construction.

Let $A$ be a class.

Let $c \in A$.

Let $g: \omega \times A \to A$ be a mapping.


Then there exists exactly one mapping $f: \omega \to A$ such that:

$\forall x \in \omega: \map f x = \begin{cases} c & : x = \O \\ \map g {n, \map f n} & : x = n^+ \end{cases}$


Let $h: A \to A$ be defined as:

$\forall x \in A: \map h x := \map g {a, x}$ for arbitrary $a \in \omega$

That is:

$\forall y \in \omega: \map g {y, x} = \map h x$


Then a priori there exists exactly one mapping $f: \omega \to A$ such that:

$\forall x \in \omega: \map f x = \begin {cases} c & : x = \O \\ \map h {\map f n} & : x = n^+ \end {cases}$


The result follows on identifying $\omega$ with $\N$, $c$ with $a$, $A$ with $T$, $\O$ with $0$ and $n^+$ with $n + 1$.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Principle_of_Recursive_Definition/Proof_4&oldid=734858"