Principle of Recursive Definition/General Result

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\N$ be the natural numbers.

Let $T$ be a set.

Let $a \in T$.

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

Let $p \in \N$.

Let $p^\geq$ be the upper closure of $p$ in $\N$.


Then there exists exactly one mapping $f: p^\geq \to T$ such that:

$\forall x \in p^\geq: f \left({x}\right) = \begin{cases} a & : x = p \\ g \left({f \left({n}\right)}\right) & : x = n + 1 \end{cases}$


Proof

Consider $\N$, defined as a naturally ordered semigroup $\left({S, \circ, \preceq}\right)$.

For simplicity, let $S' = p^\geq$.


First an admissible mapping is defined.

Let $n \in S'$.

The mapping $h: \left[{p \,.\,.\, n}\right] \to T$ is defined as an admissible mapping for $n$ if and only if:

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

where $\left[{p \,.\,.\, n}\right]$ denotes an integer interval of $S$:

$\left[{p \,.\,.\, n}\right] = \left\{ {r \in S: p \le r \le n}\right\}$


Define:

$A = \left\{{x \in S': x \text { has exactly one admissible mapping }}\right\}$

We now use the Principle of Mathematical Induction for a Naturally Ordered Semigroup to prove that $A = S'$.


Basis for the Induction

Consider the integer interval $\left[{p \,.\,.\, p}\right] = \left\{ {p}\right\}$.

Let the mapping $h_p: \left\{ {p}\right\} \to T$ be defined as:

$h_p \left({p}\right) = a$

By definition, $h_p$ is the unique admissible mapping for $p$.

Thus $p \in A$.

This is the basis for the induction.


Induction Hypothesis

Let $n \in A$ such that $p \le n$.

That is, there exists a unique admissible mapping for $n$.

This is the induction hypothesis.


Induction Step

From the induction hypothesis:

Let $h$ be the unique admissible mapping for $n$.


By Sum with One is Immediate Successor in Naturally Ordered Semigroup:

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

So by Closed Interval of Naturally Ordered Semigroup with Successor equals Union with Successor:

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


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

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

By definition, $\phi$ is an admissible mapping for $n \circ 1$.


Let $\phi'$ be an admissible mapping for $n \circ 1$.

Uniqueness of $\phi$ is then proved by showing that $\phi' = \phi$, as follows.


The restriction of $\phi'$ to $\left[{p \,.\,.\, n}\right]$ is an admissible mapping for $n$

Thus by the induction hypothesis:

$\phi' {\restriction_{\left[{p \,.\,.\, n}\right]}} = \phi {\restriction_{\left[{p \,.\,.\, n}\right]}}$


It follows that:

\(\displaystyle \phi' \left({n \circ 1}\right)\) \(=\) \(\displaystyle g \left({\phi' \left({n}\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle g \left({h \left({n}\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \phi \left({n \circ 1}\right)\)

Thus as:

$\phi' {\restriction_{\left[{p \,.\,.\, n}\right]}} = \phi {\restriction_{\left[{p \,.\,.\, n}\right]}}$

and:

$\phi' \left({n \circ 1}\right) = \phi \left({n \circ 1}\right)$

it follows by Equality of Mappings that:

$\phi' = \phi$

Thus:

$n \circ 1 \in A$

Thus by the Principle of Mathematical Induction for a Naturally Ordered Semigroup it follows that:

$A = S'$


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

Let $n \ge p$.

The restriction of $h_{n \circ 1}$ to $\left[{p \,.\,.\, n}\right]$ is an admissible mapping for $n$.

Therefore:

$h_{n \circ 1} {\restriction_{\left[{p \,.\,.\, n}\right]}} = h_n$

So:

$\forall r \in \left[{p \,.\,.\, n}\right]: h_{n \circ 1} \left({r}\right) = h_n \left({r}\right)$

and in particular:

$h_{n \circ 1} \left({n}\right) = h_n \left({n}\right)$


Let $f: S' \to T$ be the mapping defined as:

$\forall n \in S': f \left({n}\right) = h_n \left({n}\right)$

Then:

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

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

\(\displaystyle f \left({n \circ 1}\right)\) \(=\) \(\displaystyle h_{n \circ 1} \left({n \circ 1}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle g \left({h_{n \circ 1} \left({n}\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle g \left({h_n \left({n}\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle g \left({f \left({n}\right)}\right)\)

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


Let $f'$ be any mapping satisfying the desired properties.

It remains to be proved that:

$f' = f$

that is, that $f$ is the only mapping with the desired properties.


By the foregoing, for all $n \in S'$, the restriction of $f'$ to $\left[{p \,.\,.\, n}\right]$ is an admissible mapping for $n$.

Therefore:

$f' = h_n$

So:

$\forall n \in S': f' \left({n}\right) = h_n \left({n}\right) = f \left({n}\right)$

and the proof is complete.

$\blacksquare$


Sources