Learn Axioms for the Natural Numbers

** Bloch Chapter 1.2

The Peano system in Bloch has a special element $1\in \mathbb{N}$. The intuitive idea here is that $\mathbb{N} = \{1,2,3,…\}$. However, we can also present much of the same material if we instead choose $\mathbb{N} = \{0,1,2,3,…\}$.

The axioms for this remain the same: A Peano system is a set $\mathbb{N}$ with a distinct element $0\in \mathbb{N}$ and a function $s:\mathbb{N}\rightarrow \mathbb{N}$ such that
# There is no $n\in \mathbb{N}$ such that $s(n) = 0$.
# The function $s$ is injective.
# Let $G$ be a set. Suppose that $0\in G$ and that from $g\in G$ follows that $s(g)\in G$. Then $G=\mathbb{N}$.

In this case, the definition of the operation require something different. In particular, we define $+$ such that
# $n+0 = n$
# $n+s(m) = s(n+m)$

And we define
# $n\cdot 0 = 0$
# $n\cdot s(m) = n\cdot m + m$

 

== Construction of the natural numbers ==

It is possible to construct a Peano system by using only sets. Note that we take a Peano system in the sense of the above definition, where the “first element” is $0$.

The idea is that
$$0 = \emptyset,~1 = \{\emptyset\},~2 = \{\emptyset,\{\emptyset\}\},…$$
In general, we define $0=\emptyset$, and if $n$ is defined, then we define $n+1 = n\cup \{n\}$.

More formally, we call a set $X$ to be inductive if $\emptyset \in X$ and if for all $x\in X$, we have that $x\cup\{x\}$ is an element of $X$. It is an axiom of set theory that an inductive set exists. The set of natural numbers can then be defined as the smallest inductive set, or:
$$\mathbb{N}=\bigcap\{X~\vert~X~\text{is inductive}\}.$$
We can check that this set $\mathbb{N}$ satisfies the Peano axioms with $0 = \emptyset$ and $s(x) = x\cup \{x\}$. Let us do that:

1) There is no $n\in \mathbb{N}$ such that $s(n) = 0$.
Indeed, if such an $n$ exists, then we would have $n\cup \{n\} = \emptyset$. But then $n\in \emptyset$ which is impossible.

2) The function $s$ is injective.
First we prove that every $n\in \mathbb{N}$ is transitive. This means that if $m\in n$, then $m\subseteq n$. Indeed, let $X\subseteq \mathbb{N}$ be the set of all elements $n\in \mathbb{N}$ that are transitive. We prove that $X$ is inductive, from which follows that $X=\mathbb{N}$. It is clear that $\emptyset$ is inductive, so $\emptyset \in X$. Now assume that $n\in X$. Then $n$ is inductive. Now take $m\in n\cup \{n\}$, then either $m = n$, from which follows that $m\subseteq n\cup \{n\}$. Or we have that $m\in n$. Since $n$ is inductive, it follows that $m\subseteq n$. So $X$ is inductive.

Now assume that $s(n) = s(m)$. Then $n\cup \{n\} = m\cup \{m\}$. If $n\neq m$, then we have that $n\in m$ and $m\in n$. But since $n$ is inductive, it follows that $m\subseteq n$. So it follows from $n\in m$ that $n\in n$. We now show that this is impossible for any $n\in \mathbb{N}$. To do this, we take $X$ to be the set of all $n\in \mathbb{N}$ such that $n\notin n$. Clearly, $\emptyset \in X$. Now assume that $n\notin n$. If $n\cup \{n\} \in n\cup \{n\}$, then either $n\cup \{n\}\in n$ or $n\cup \{n\} = n$. We show that both are impossible:
a) If $n\cup \{n\} \in n$, then by transitivity of $n$ follows that $n\cup \{n\}\subseteq n$. Then $n\in n$ which was against the assumption.
b) If $n\cup \{n\} = n$, then $n\in n$, which from the assumption was again impossible.
So we have prove that if $n\in X$, then so is $n\cup \{n\}$. So $X$ is inductive. But then $X=\mathbb{N}$.

3) Assume that $G\in \mathbb{N}$. Assume that $0\in G$ and that from $g\in G$ follows that $s(g)\in G$. Then $G=\mathbb{N}$.
This follows immediately since $G$ is inductive and $\mathbb{N}$ is the smallest inductive set.

== What is a natural number ==

We have now exhibited two definitions of natural numbers: one as a set that satisfies the Peano axioms, and the other a very weird explicit construction in terms of sets. This last definition is very weird, we had things like $1 = \{\emptyset\}$. But surely the number $1$ is something different?

This is a philosophical issue. What exactly is the nature of the number $1$ (or any other number) is unknown and debatable. All mathematicians care about is what properties the natural numbers have. It seems very agreeable to say that the natural numbers (whatever they are) should satisfy the Peano axioms. So what mathematicians do is not worry about what natural numbers are exactly, but rather construct a model that behaves exactly like the natural numbers. The benefit of that is we don’t need anything extra outside of set theory in order to talk about natural numbers.

== Exponentiation ==

Exponentiation of natural numbers can also be defined recursively. The following would generate a useful recursive definition of exponentation:

# $m^1 = m$
# $m^{n+1} = m^n \cdot m$

It is a useful exercise to prove the basic exponentation laws:

# $a^{m+n} = a^m a^n$
# $a^{mn} = (a^m)^n = (a^n)^m$
# $(ab)^m = a^m b^m$

== Independence of the axioms ==

It is a useful mathematical exercise to show that the three Peano axioms are independent. This means that if we assume two of the axioms to be true, then it is impossible to prove the third. Here is how to do this in this case:

1) Assume that the first two axioms are true, then the induction axiom is not necessarily true.
A good example of such a structure is $[1,+\infty)$, with $s(x) = x+1$. Then the function $s$ is clearly injective and there is no $x$ such that $s(x) = 1$. The induction theorem is false. Indeed, consider $\mathbb{N} = \{1,2,3,…\}$. This is a subset of our structure, and it satisfies that $1\in \mathbb{N}$ and if $n\in \mathbb{N}$ then $n+1\in \mathbb{N}$. But our set isn’t entire $[1,+\infty)$.

In this sense, we can see the induction axiom as an axiom delimiting the size of our system. So the induction hypothesis might be seen as an axiom saying that our system is the smallest possible satisfying axiom (1) and (2).

2) Assume that the first axiom and the induction are true, then the second axiom is not necessarily true.
The idea here is to take $X = \{1,2,…,n\}$ with a somewhat weird $s$ function. We define $s(1) = 2$, $s(2) = 3$, etc. until $s(n-1) = n$. The only difference is that we also define $s(n) = 2$. Then the first axiom is clearly satisfied and the induction hypothesis can be satisfied, but $s$ is not injective since $s(n) = s(1) = 2$.

3) Assume that the second axiom and the induction axiom is true, then the first axiom is not necessarily true.
The idea is to take $X = \{1,…,n\}$ and to take $s(1) = 2$, $s(2) = 3$, etc. until $s(n-1) = n$. The only difference with the previous example is by taking $s(n) = 1$. This gives some kind of cyclic structure.

This example is actually a very useful mathematically since it can be used to describe divisibility. A lot of useful theorems of natural numbers actually can be carried over to this context. This yields the example of cyclic groups and rings.

== Uniqueness of Peano system ==

The previous section details that the axioms are dependent. Another question is whether the axioms are categorical, that is: do they give us a unique system. Of course not: uniqueness is too much to ask anyway. Indeed, we can just rename the elements to get another system. Categorical however is about a unique system up to isomorphism: this means that every two systems satisfying the Peano axioms are equivalent “up to renaming”. This is the content of Exercise 1.2.8.

 

== Consistency of the Peano axioms ==

Consistency means that the axioms cannot lead to a contradiction. A contradiction is a statement that can be proven true and false. It is crucial in mathematics that our systems are consistent. For example, consider the following axiom system which is a set $X$ satisfying the following axioms
1) $X$ is nonempty
2) $X$ is empty
Clearly, there is no such axiomatic system, since my axioms are contradictory. So this pretty silly example shows that we cannot just allow anything to be an axiom: for any axiomatic system it has the risk that it is similarly contradictory.

An important question is whether the Peano axioms are consistent. Sadly, it has been shown by Gödel that nobody can show whether the axiomatic system is consistent in itself. Gödel’s result means that we can only talk about the consistency of the Peano axioms relative to another axiomatic system. With that in mind, we can prove that the Peano axioms are consistent within set theory: if set theory is consistent, then so are the Peano axioms. Our construction of the natural numbers above is one way of showing this.

But isn’t the Peano system just a formalized version of the counting numbers? Numbers we use every single day? Yes, but a Peano system also asserts that there are infinitely many such numbers. While this may seem obvious, this is outside the realm of our experience. Surely, the numbers $1$, $2$, $3$ behave as we expect, but why should gigantic numbers like $10^{10^{10}}$ exist at all? It is safe to say that such infinite numbers do not exist in our reality. If they don’t exist in our reality, then nothing guarantees that these made-up numbers make sense at all. And nothing guarantees that the collection of these numbers is a consistent whole.