Principle of Recursive Definition

Theorem

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

Let $p \in \left({S, \circ, \preceq}\right)$.

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

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

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

Then there exists one and only 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 one and only 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 the concept of an admissible mapping.

Let $p \in \left({S, \circ, \preceq}\right)$. Let $T$ be a set.

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

$\forall r \in S: p \preceq r \prec n: g \left({r}\right) = \begin{cases} a & : r = p \\ s \left({f\left({y}\right)}\right) & : y = r \circ 1 \end{cases}$

• First we prove existence of the mapping $f: S' \to T$:

Let:

$A = \left\{{x \in S: p \preceq x \land \exists! \text { an admissible mapping for } x}\right\}$

Now $p \in A$ because we can define the mapping $g_p$ such that $g_p \left({p}\right) = a$.

This has the domain $\left\{{p}\right\}$ and is clearly the only admissible mapping for $p$.

Suppose $n \in A$. Let $g$ be the only admissible mapping for $n$.

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) & : \left[{p .. n}\right] \\ s \left({g \left({n}\right)}\right) & : r = n \circ 1 \end{cases}$

Clearly $h$ is admissible for $n \circ 1$.

• First we prove uniqueness of the mapping $f: S' \to T$:

Let $h'$ be any mapping admissible for $n \circ 1$.

The restriction of $h'$ to $\left[{p .. n}\right]$ is also admissible.

Hence, since $n \in T$, so is $g$ admissible.

So:

	\(\displaystyle \)	\(\displaystyle \forall r \in \left[{p .. n}\right]:\)	\(\)	\(\displaystyle h' \left({r}\right) = g \left({r}\right) = h \left({r}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\land\)	\(\displaystyle 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)\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \)	\(\)	\(\displaystyle h' = h\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \)	\(\)	\(\displaystyle n \circ 1 \in T\)	\(\displaystyle \)

So by the Principle of Finite Induction, $T = \left\{{x \in S: p \preceq x}\right\}$.

Now, for each $n \in S: p \preceq n$, let $g_n$ be the unique admissible mapping for $n$.

If $p \preceq n$, the restriction of $g_{n \circ 1}$ to $\left[{p .. n}\right]$ is admissible for $n$, and hence is $g_n$.

Therefore:

$g_{n \circ 1} \left({r}\right) = g_n \left({r}\right)$ for all $r \in \left[{p .. n}\right]$

In particular:

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

Let $f$ be the mapping defined by $\forall n \in S: p \preceq n: f \left({n}\right) = g_n \left({n}\right)$.

Then:

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

and:

	\(\displaystyle \forall n \in S: p \preceq n:\)	\(\displaystyle \)	\(\)	\(\displaystyle f \left({n \circ 1}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle g_{n \circ 1} \left({n \circ 1}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle s \left({g_{n \circ 1} \left({n}\right)}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle s \left({g_n \left({n}\right)}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle s \left({f \left({n}\right)}\right)\)	\(\displaystyle \)

If $f'$ is any mapping satisfying the desired conditions, then for each $n \in S$ such that $p \preceq n$, the restriction of $f'$ to $\left[{p .. n}\right]$ is clearly admissible for $n$.

Hence so is $g_n$.

So:

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

So there is exactly one mapping having the desired properties.

$\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): $\S 16$: Theorem $16.6$