Principle of Recursive Definition

Theorem

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

Let $p \in S$.

Let $T$ be a set and let $a \in T$.

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

Let $S\,' = \mathop{\bar \uparrow} \left({p}\right) = \left\{{x \in S: p \preceq x}\right\}$, the weak upper closure of $p$.

Then there exists exactly one mapping $f: S\,' \to T$ such that:

$\forall x \in S\,': f \left({x}\right) = \begin{cases} a & : x = p \\ s \left({f\left({y}\right)}\right) & : x = y \circ 1 \end{cases}$

Alternative Formulation

Let $\omega$ be the minimal infinite successor set.

Let $T$ be a set and let $a \in T$.

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

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

$\forall x \in \omega: f \left({x}\right) = \begin{cases} a & : x = 0 \\ s \left({f \left({n}\right)}\right) & : x = n^+ \end{cases}$

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

Proof

First, we define an admissible mapping.

For each $n \in S\,'$, we say that $g$ is an admissible mapping for $n$ iff $g: \left[{p \,.\,.\, n}\right] \to T$ is a mapping such that:

$\forall r \in \left[{p \,.\,.\, n}\right]: g \left({r}\right) = \begin{cases} a & : r = p \\ s \left({f\left({y}\right)}\right) & : r = y \circ 1 \end{cases}$

Here, $\left[{p \,.\,.\, n}\right]$ denotes a closed interval.

Define:

$A = \left\{{x \in S\,': \exists! \text { an admissible mapping for } x}\right\}$

Here, the symbol $\exists!$ means "there exists exactly one".

We now use the principle of finite induction to prove that $A = S\,'$.

The base case $p \in A$ holds because we can define the mapping $g_p$ such that $g_p \left({p}\right) = a$. Clearly, $g_p$ is the only admissible mapping for $p$.

Now assume the induction hypothesis that $n \in A$. Let $g$ be the only admissible mapping for $n$.

We now complete the induction step.

By Precedes Next:

$n \circ 1 \notin \left[{p \,.\,.\, n}\right]$

So by Closed Interval of Successor:

$\left[{p \,.\,.\, n \circ 1}\right] = \left[{p \,.\,.\, n}\right] \cup \left\{{n \circ 1}\right\}$

So we can define a mapping $h: \left[{p \,.\,.\, n \circ 1}\right] \to T$ by:

$\forall r \in \left[{p \,.\,.\, n \circ 1}\right]: h \left({r}\right) = \begin{cases} g \left({r}\right) & : r \in \left[{p \,.\,.\, n}\right] \\ s \left({g \left({n}\right)}\right) & : r = n \circ 1 \end{cases}$

Clearly, $h$ is an admissible mapping for $n \circ 1$.

Let $h'$ be any admissible mapping for $n \circ 1$. We then prove that $h = h'$ (i.e., that $h$ is the only admissible mapping for $n \circ 1$).

The restriction of $h'$ to $\left[{p \,.\,.\, n}\right]$ is an admissible mapping for $n$, and is therefore equal to $g$ by hypothesis.

It follows that:

$h' \left({n \circ 1}\right) = s \left({h' \left({n}\right)}\right) = s \left({g \left({n}\right)}\right) = h \left({n \circ 1}\right)$

Thus the assertion that $A = S\,'$ has been proven.

For all $n \in S\,'$, let $g_n$ be the unique admissible mapping for $n$.

Let $f : S\,' \to T$ be the mapping defined by $f \left({n}\right) = g_n \left({n}\right)$ for all $n \in S\,'$.

The restriction of $g_{n \circ 1}$ to $\left[{p \,.\,.\, n}\right]$ is an admissible mapping for $n$, and is therefore equal to $g_n$.

So:

$g_{n \circ 1} \left({n}\right) = g_n \left({n}\right)$

Then:

$f \left({p}\right) = g_p \left({p}\right) = a$

and, for all $n \in S\,'$:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle f \left({n \circ 1}\right)\)	\(=\)	\(\displaystyle g_{n \circ 1} \left({n \circ 1}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle s \left({g_{n \circ 1} \left({n}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle s \left({g_n \left({n}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle s \left({f \left({n}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Thus $f : S\,' \to T$ is a mapping with the desired properties.

Let $f\,'$ be any mapping satisfying the desired properties. We prove that $f\,' = f$ (i.e., that $f$ is the only mapping with the desired properties).

For all $n \in S\,'$, the restriction of $f\,'$ to $\left[{p \,.\,.\, n}\right]$ is clearly an admissible mapping for $n$, and is therefore equal to $g_n$.

So:

$f\,' \left({n}\right) = g_n \left({n}\right) = f \left({n}\right)$

completing the proof.

$\blacksquare$

Proof of Alternative Formulation

The proof of the alternative formulation follows the same lines.

Alternatively it can be noted that:

• The Natural Numbers are a Naturally Ordered Semigroup and that Naturally Ordered Semigroups Isomorphism Unique
• The Natural Numbers are Elements of the Minimal Infinite Successor Set.

All these objects are different ways of discussing the same thing, and so they share the same properties.

Hence the result.

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 12$: The Peano Axioms
• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 16$: Theorem $16.6$