Definition:Natural Numbers/Axiomatization

From ProofWiki
Jump to navigation Jump to search

Definition

The natural numbers $\N$ can be axiomatised in the following ways:


Peano's Axioms

Peano's Axioms are intended to reflect the intuition behind $\N$, the mapping $s: \N \to \N: s \left({n}\right) = 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. The other three are as follows:

\((P3)\)   $:$     \(\displaystyle \forall m, n \in P:\) \(\displaystyle \map s m = \map s n \implies m = n \)    $s$ is injective             
\((P4)\)   $:$     \(\displaystyle \forall n \in P:\) \(\displaystyle \map s n \ne 0 \)    $0$ is not in the image of $s$             
\((P5)\)   $:$     \(\displaystyle \forall A \subseteq P:\) \(\displaystyle \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$             


Naturally Ordered Semigroup

The concept of a naturally ordered semigroup is intended to capture the behaviour of the natural numbers $\N$, addition $+$ and the ordering $\le$ as they pertain to $\N$.


Naturally Ordered Semigroup Axioms

A naturally ordered semigroup is a (totally) ordered commutative semigroup $\left({S, \circ, \preceq}\right)$ satisfying:

\((NO 1)\)   $:$   $S$ is well-ordered by $\preceq$      \(\displaystyle \forall T \subseteq S:\) \(\displaystyle T = \varnothing \lor \exists m \in T: \forall n \in T: m \preceq n \)             
\((NO 2)\)   $:$   $\circ$ is cancellable in $S$      \(\displaystyle \forall m, n, p \in S:\) \(\displaystyle m \circ p = n \circ p \implies m = n \)             
\(\displaystyle p \circ m = p \circ n \implies m = n \)             
\((NO 3)\)   $:$   Existence of product      \(\displaystyle \forall m, n \in S:\) \(\displaystyle m \preceq n \implies \exists p \in S: m \circ p = n \)             
\((NO 4)\)   $:$   $S$ has at least two distinct elements      \(\displaystyle \exists m, n \in S:\) \(\displaystyle m \ne n \)             


1-Based Natural Numbers

The following axioms are intended to capture the behaviour of $\N_{>0}$, the element $1 \in \N_{>0}$, and the operations $+$ and $\times$ as they pertain to $\N_{>0}$:

\((A)\)   $:$     \(\displaystyle \exists_1 1 \in \N_{> 0}:\) \(\displaystyle a \times 1 = a = 1 \times a \)             
\((B)\)   $:$     \(\displaystyle \forall a, b \in \N_{> 0}:\) \(\displaystyle a \times \paren {b + 1} = \paren {a \times b} + a \)             
\((C)\)   $:$     \(\displaystyle \forall a, b \in \N_{> 0}:\) \(\displaystyle a + \paren {b + 1} = \paren {a + b} + 1 \)             
\((D)\)   $:$     \(\displaystyle \forall a \in \N_{> 0}, a \ne 1:\) \(\displaystyle \exists_1 b \in \N_{> 0}: a = b + 1 \)             
\((E)\)   $:$     \(\displaystyle \forall a, b \in \N_{> 0}:\) \(\displaystyle \)Exactly one of these three holds:\( \)             
\(\displaystyle a = b \lor \paren {\exists x \in \N_{> 0}: a + x = b} \lor \paren {\exists y \in \N_{> 0}: a = b + y} \)             
\((F)\)   $:$     \(\displaystyle \forall A \subseteq \N_{> 0}:\) \(\displaystyle \paren {1 \in A \land \paren {z \in A \implies z + 1 \in A} } \implies A = \N_{> 0} \)