Definition Peano Axioms

The natural numbers are defined axiomatically by the Peano axioms. In other words, their existences and properties are stated outright on the backdrop of a larger theory like set theory or first order logic. In this case, as mentioned earlier, the backdrop is informal set theory. With this overview in mind, one now assumes that there exists a unique set $\mathbb{N}$ such that

0. the symbol $0$ is in it
1. for every $n$ in this set, the string $S(n)$ is in the set too; $S(n)$ is called the successor of $n$ while $n$ is called the predecessor of $S(n)$
2. for every $n,n' \in \mathbb{N}$, $n=n'$ if and only if $S(n)=S(n')$; this says that one can think of $S$ as a function since it maps equals to equals ... furthermore, thought of as a function, it is also injective since it maps only equals to equals
3. there exists no natural number $n$ such that $S(n)=0$
4. if $\Sigma$ is a set where $0\in\Sigma$ and for every $n\in\mathbb{N}$, $n\in\Sigma$ implies $S(n)\in\Sigma$, then $\mathbb{N}\subseteq\Sigma$; this is the principle of induction over the natural numbers

One caveat needs attention: in first order logic, where the very behavior of the equals-sign $=$ is, by default, undefined, one also needs to add two more properties to the list — that $=$ be an equivalence relation (i.e. $x=x$, $x=y \Rightarrow y=x$, $x=y \wedge y=z \Rightarrow x=z$) and that $\mathbb{N}$ be closed under $=$ (i.e. $x\in\mathbb{N} \wedge y=x \Rightarrow y\in\mathbb{N}$). However, I will not split hairs to this extent. Instead, over here, the equals-sign is simply the same equality used in informal set theory with all its expected properties.

Interestingly, one can define $0$ and the successor function $S$ purely using set theory: $0=\emptyset$ and $S(n)=n\cup\{n\}$ for any set $n$. Then one defines a set to be inductive if it contains $0$ and is closed under $S$. Next, one axiomatically asserts that there exists a set that is contained in every inductive set. This (unique) set is defined to be $\mathbb{N}$. When defined in this manner, $\mathbb{N}$ is denoted as $\omega$. The reader can verify that this definition does indeed satisfy all the Peano axioms. This set theoretic definition of the naturals has the advantage that there is no difference between the natural $n$ and the set of all naturals less than $n$: $\text{Fin}(n)$ — they are exactly the same set as can be verified by a quick inductive argument.

The last Peano axiom, the principle of induction, is the main work horse in almost every proof about the naturals. Thus, it is worthwhile to explore a few simple instances of its use.

Lemma ExPre

Existence of a Predecessor. If $n\in\mathbb{N}$ and $n \neq 0$, then there is an $n'\in\mathbb{N}$ such that $S(n')=n$.

Proof: The principle of induction over $\mathbb{N}$, as it was presented, is an axiom that operates on a set $\Sigma$. Thus, to use it in proving lemma like this, one must first convert the lemma into a set like so: $\Sigma=\{n\in\mathbb{N}:\ n=0\ \ \text{or}\ \ \exists n'\in\mathbb{N}\ [n=S(n')]\}$ i.e. one has just made this lemma into the condition of some set $\Sigma$. Now, if one can prove that $\mathbb{N}\subseteq\Sigma$, one will have proved the lemma for all of $\mathbb{N}$. For then, every $n$ in $\mathbb{N}$ would also be in $\Sigma$; thus, it must satisfy the condition of $\Sigma$ — which is the lemma itself.

With this overview of the objective, let's proceed to apply Peano axiom 4, as promised, to $\Sigma$:

• Clearly $0\in\Sigma$ because it satisfies both $n\in\mathbb{N}$ (by the Peano axiom 0) and the first alternative of $\Sigma$'s condition, $n=0$.
• Next, suppose $n$ is in both $\mathbb{N}$ and $\Sigma$. Then clearly $S(n)\in\Sigma$ also because
  • $S(n)\in\mathbb{N}$ by Peano axiom 1 and
  • there is obviously an $n'\in\mathbb{N}$ such that $S(n)=S(n')$, namely, $n$ itself.

Thus, $\mathbb{N}\subseteq\Sigma$ by the conclusion of the last Peano axiom.

Lemma SNoFPs

$S$ has No Fixed Points: For any $n\in\mathbb{N}$, $n \neq S(n)$.

Proof: This time, $\Sigma=\{n\in\mathbb{N}:\ n \neq S(n)\}$.

• $0\in\Sigma$ because it satisfies both the conditions of $\Sigma$ — i.e. both $0\in\mathbb{N}$ and $0 \neq S(0)$ — by Peano axioms 0 and 3 respectively.
• Suppose $n\in\Sigma$, then certainly $n \neq S(n)$ where $S(n)\in\Sigma$ by Peano axiom 1. This, along with the contrapositive of Peano axiom 2, implies that $S(n) \neq S(S(n))$. But then, $S(n)$ satisfies $\Sigma$'s condition so that $S(n)\in\Sigma$.

Thus, by the principle of induction, $\mathbb{N}\subseteq\Sigma$.

Remarks

A couple of key points are already visible in these simple proofs about the naturals.

• Firstly, Peano axioms 0 and 1 are ubiquitous throughout the proofs. In fact, this is the case with all proofs about the naturals. However, unlike the ubiquitous induction principle, they are also very simple. It should be obvious whenever they are applicable. For these reasons, as are the cases with simple results, I henceforth leave them out of all proofs. Their applicability is implicit.
• Secondly, note how the induction principle is applied: one first wraps the lemma/theorem being proven in a set; only then, does Peano axiom 4 become applicable. This is largely unnecessary. One can, instead, state Peano axiom 4 as such
  4. if $\phi$ is an unary property such that $\phi(0)$ is true and for every $n\in\mathbb{N}$, $\phi(n)$ implies $\phi(S(n))$, then $\phi$ is true for all of $\mathbb{N}$