Natural Numbers: Foundational Peano's Axioms

Overview 

This is my study note while reading Analysis by Terence Tao. This is a very interesting and enlightening book. We will first lay the foundations for the number system, building our way up from the very bottom -- the natural numbers.

Peano's Axioms

This is an axiomatic treatment of the natural numbers. We will construct the natural numbers that we know and love from scratch, based on a minimal and powerful set of axioms. First to remind the readers, the natural numbers that we know are

$$0, 1, 2, ...$$

To define this type of numbers, we will need two things: an initial starting point ($0$) and an increment operator ($ ++  $). By incrementing, we mean increasing a number by $ 1 $ so $1 = 0 ++, 2 = 1 ++, ... $. For now, we can think of $++$ as an arbitrary symbol that when applied to a natural number would produce another natural number.

$1, 2, 3, ...$ are of course just convenient notation. $1$ is the "increment of 0". $2$ is the the "increment of 1" or the "increment of "the increment of 0" " and so on. Everything we discuss here still hold if we use a different notations like Roman numerals i.e. $I, II, III, ...$.

Now we will define two foundational axioms.

Axiom 1 (Initial Value) $0$ is a natural number.

Axiom 2 (Recursive increment operator) If $n$ is a natural number, then $n++$ is also a natural number.



However, these two axioms are not sufficient. We might have a weird natural number system that "loops back" like $0, 1, \textbf{2}, 3, \textbf{2}, 4, ...$. In fact, in computer system, overflows will cause the 2's complement representation to loop back like that. In mathematics, we do not allow this behavior. So we will introduce two additional axioms to avoid repetition in our number system.

Axiom 3 (Bounded at one end) $0$ has no predecessor i.e. there does not exist natural number $n$ such that $0 = n++$.

Axiom 4 (Unique Predecessor) If $n$ and $m$ are two different natural numbers, then $n ++$ and $m ++$ are different. Equivalently, if $n ++$ and $m++$ are the same, then $n$ and $m$ must be the same.

In other words, axiom 4 does not allow this type of situation.

Axiom 3 basically re-affirms axiom1 that $0$ is the initial starting point. In the natural number system, there is no number that comes before $0$. From this axiom, we know that $0$ is unique. Axiom 4 basically provides a mechanism that we can use to tell if two given natural numbers are equal to each other.

Example 1 (Uniqueness of $0$) $0$ is not equal to $2$.

Proof

$2 = 1++$, but $0$ does not have a predecessor. Thus, $2$ and $0$ must be different. This argument can be easily extended to say that $0$ is different from $1, 3, 4, ...$ and so on.

Example 2 (Uniqueness of any natural number) $8$ is not equal to $4$.

Proof
For the sake of contradiction, say we have a sequence with two $4$ like

$$0, 1, 2, 3, 4, 5, 6, 7, 4, x, y, z, k, h , ...$$

By the unique predecessor axiom 4, we know that $ 7 = 3$ because $ 4 = 7 ++ = 3++$. Similarly, we know that $6 = 2$, $5 = 1$ and $4 = 0$. The last statement violates example 1, so we know that $4$ can not be repeated. This essentially says proves that $ 8 : = 7 ++ $ is different from $4$.

Figure 1.2 is a little bit concerning since we know that each natural number should also have a unique successor. For this reason, the $++$ increment operator can sometimes be defined as a successor function $S(n) = n ++$. And of course, a function should map a unique $x$ to a unique $y$. Axiom 4 asserts that $S(n)$ is injective.

This is what the natural numbers should look like

However, our $4$ axioms so far are not sufficient to define the natural numbers that we know. We can have a weird natural number system as in the picture that still obeys all the previous axioms.

The problem with this system is that not all "natural numbers" other than $0$ i.e. $\sqrt{2}, \pi, 0.5$ are preceded by a natural number. In other words, we should require the successor function $S: \mathbb{N} \to \mathbb{N} \setminus \{0\}$ to be surjective in addition to being injective in axiom 4. If $S$ is a bijection, then there exists the predecessor function $S^{-1}$ that takes $S^{-1}(n) = n -- $. This would require $\sqrt{2}, \pi, 0.5$ to have predecessors. However, even this would not prevent a situation like

Note that the second chain extends infinitely towards both left and right directions and is totally disconnected from the first chain, which truly is the natural numbers.

In fact, we need to assume a very strong axiom that will serve as a powerful tool for many proofs later on.


Axiom 5 (Induction)

Define a predicate as a Boolean-valued function $f : X \to \{true, false\}$ for some set $X$. A unary predicate that takes in only one single value (instead of a vector for example) is called property $P$. The axiom states that if

•  $P(0)$ is true and 
• for every natural number $n$, $P(n)$ is true implies that $P(n++)$ is true 

then $P$ is true for every natural number.


Note that Figure 1.4 can be eliminated by setting $P(n) = "n$ is $0$ or $n$ has a predecessor" i.e. for every natural numbers $n \not = 0$ there exists $m \in \mathbb{N}$ such that $n = m++$.

We can prevent Figure 1.5 by setting $p(n) = $ " $n$ is $0$ or there is a path (in a graphical sense) from $n$ to $0$. Obviously, if there is a path from $n$ to $0$, then $n++$ can follows the edge from $n++$ to $n$ and will find a path back to $0$. By induction axiom 5, there must be a path from $n$ to $0$ for every natural number $n$. This means that the second chain must be connected to the first chain at some point.

This would violate unique predecessor axiom 4. This is a non-rigorous argument since we have not defined what is a path. To sum up, we have defined $5$ Peano's axioms

• Axiom 1 (starting point): $0 \in \mathbb{N}$. 
• Axiom 2 (increment): If $n \in \mathbb{N}$, then $n++ = S(n) \in \mathbb{N}$. 
• Axiom 3 (bounded): $0$ has no predecessor i.e. there does \textbf{not} exist $m \in N$ such that $m++ = 0$. 
• Axiom 4 (unique predecessor): $S(n)$ is injective. $ m = n$ if and only if $m ++ = n++$. 
• Axiom 5 (Induction) For unary predicate (property) $P$, if $P(0)$ is true and $P(n) \implies P(n++) $, then $P(n)$ is true for all $n \in N$. 

Axiom 4 defines what it means to say two natural numbers are equal. Before proceeding, we will lay down a standard definition of equality that would apply to all number sets including natural numbers, integers, rationals and real numbers.

Definition (Equality) Equality relation $P(x, y)$ is a binary predicate between two objects $x$ and $y$ satisfies three properties:

•  Reflexive: $ x = x$ i.e. $P(x, x)$ is true. 
• Symmetric: If $ x = y$ then $ y = x$ i.e. $P(x, y) \implies P(y, x)$. 
• Transitive: If $ x = y$ and $y = z$, then $ x = z$ i.e. $(P(x, y) \land P(y, z) ) \implies P(x, z)$

Finally, for the case of natural numbers, we also assume that if $x = y$ and $x \in \mathbb{N}$ then $y \in \mathbb{N}$.

We can verify that the equality definition of natural numbers in axiom 4 satisfies three properties above.