Von Neumann Construction of Natural Numbers is Minimally Inductive

From ProofWiki
Jump to navigation Jump to search

Theorem

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


$\omega$ is a minimally inductive class under the successor mapping.


Proof

Consider Peano's axioms:

Peano's Axioms are intended to reflect the intuition behind $\N$, the mapping $s: \N \to \N: \map s n = n + 1$ and $0$ as an element of $\N$.


Let there be given a set $P$, a mapping $s: P \to P$, and a distinguished element $0$.

Historically, the existence of $s$ and the existence of $0$ were considered the first two of Peano's Axioms:

\((\text P 1)\)   $:$   \(\ds 0 \in P \)    $0$ is an element of $P$             
\((\text P 2)\)   $:$     \(\ds \forall n \in P:\) \(\ds \map s n \in P \)    For all $n \in P$, its successor $\map s n$ is also in $P$             

The other three are as follows:

\((\text P 3)\)   $:$     \(\ds \forall m, n \in P:\) \(\ds \map s m = \map s n \implies m = n \)    $s$ is injective             
\((\text P 4)\)   $:$     \(\ds \forall n \in P:\) \(\ds \map s n \ne 0 \)    $0$ is not in the image of $s$             
\((\text P 5)\)   $:$     \(\ds \forall A \subseteq P:\) \(\ds \paren {0 \in A \land \paren {\forall z \in A: \map s z \in A} } \implies A = P \)    Principle of Mathematical Induction:             
Any subset $A$ of $P$, containing $0$ and             
closed under $s$, is equal to $P$             


From Inductive Construction of Natural Numbers fulfils Peano's Axioms, $\omega$ fulfils Peano's axioms.

We note that from Peano's Axiom $\text P 1$: $0 \in P$:

$\O \in \omega$

We acknowledge from Peano's Axiom $\text P 2$: $n \in P \implies \map s n \in P$:

the successor mapping defines that $n^+ := n \cup \set n$

and from Peano's Axiom $\text P 5$: Principle of Mathematical Induction the result follows.

$\blacksquare$


Sources