Peano Axioms: Construction of Natural Numbers and Properties

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 operations requires something different. In particular, we define $+$ such that

• $n+0 = n$
• $n+s(m) = s(n+m)$

And we define multiplication by recursion:

• $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 using only sets. 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, a set $X$ is called inductive if $\emptyset \in X$ and if for all $x\in X$ we have $x\cup\{x\}\in 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$ existed, 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: if $m\in n$, then $m\subseteq n$. 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 it follows that $X=\mathbb{N}$.

It is clear that $\emptyset$ is transitive, so $\emptyset \in X$. Now assume $n\in X$. Take any $m\in n\cup\{n\}$; then either $m=n$, from which $m\subseteq n\cup\{n\}$, or $m\in n$, and by transitivity of $n$ we have $m\subseteq n$. Hence $X$ is inductive.

Now assume $s(n) = s(m)$, so $n\cup \{n\} = m\cup \{m\}$. If $n\neq m$ then one would have $n\in m$ and $m\in n$. Since each element is transitive, $m\subseteq n$ follows, and from $n\in m$ we would deduce $n\in n$, which we now show is impossible for any $n\in \mathbb{N}$.

Let $Y$ be the set of all $n\in \mathbb{N}$ such that $n\notin n$. Clearly $\emptyset\in Y$. Assume $n\in Y$. If $n\cup\{n\}\in n\cup\{n\}$, then either $n\cup\{n\}\in n$ or $n\cup\{n\} = n$. Both are impossible:

• a) If $n\cup\{n\}\in n$, then by transitivity of $n$ we have $n\cup\{n\}\subseteq n$, hence $n\in n$, contradicting the assumption.
• b) If $n\cup\{n\} = n$, then $n\in n$, again a contradiction.

Thus if $n\in Y$ then $n\cup\{n\}\in Y$, so $Y$ is inductive and therefore $Y=\mathbb{N}$. This proves injectivity of $s$.

3) Let $G\subseteq \mathbb{N}$. Assume that $0\in G$ and that whenever $g\in G$ it 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 as a very explicit construction in terms of sets. This latter construction is unusual: for example $1 = \{\emptyset\}$. But is the number $1$ really “that” set?

This is a philosophical issue. What exactly the nature of the number $1$ (or any other number) is, is debatable. Mathematicians typically care about the properties of the natural numbers rather than their metaphysical nature. It is natural to require that whatever the natural numbers are, they satisfy the Peano axioms. Constructing a model of the Peano axioms within set theory means we need nothing beyond set theory to discuss natural numbers.

Exponentiation

Exponentiation of natural numbers can also be defined recursively. A convenient recursive definition is

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

It is a useful exercise to prove the basic exponentiation 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 assuming any two of the axioms does not allow one to prove the third. Here are examples:

1) Assume the first two axioms are true; the induction axiom need not hold.

A structure demonstrating this is $[1,+\infty)$ with $s(x)=x+1$. The function $s$ is injective and there is no $x$ with $s(x)=1$, but induction fails: the subset $\{1,2,3,\dots\}$ satisfies the base and successor conditions but is not the whole structure.

2) Assume the first axiom and induction are true; the second axiom need not hold.

Take $X=\{1,2,\dots,n\}$ with $s(1)=2, s(2)=3,\dots, s(n-1)=n$ and also set $s(n)=2$. Then the first axiom holds and induction can be arranged, but $s$ is not injective since $s(n)=s(1)=2$.

3) Assume the second axiom and induction are true; the first axiom need not hold.

Take $X=\{1,\dots,n\}$ and set $s(1)=2, s(2)=3,\dots, s(n-1)=n$, and $s(n)=1$, giving a cyclic structure. This is useful: many theorems about natural numbers carry over to cyclic contexts and yield examples such as cyclic groups and rings.

Uniqueness of Peano systems

The previous section details that the axioms are independent. Another question is whether the axioms are categorical: do they determine a unique system up to isomorphism? They are categorical in that every two systems satisfying the Peano axioms are isomorphic (equivalent up to renaming elements). This is the content of Exercise 1.2.8.

Consistency of the Peano axioms

Consistency means the axioms cannot lead to a contradiction (a statement provable both true and false). For example, the axiomatic system given by the two statements “1) $X$ is nonempty” and “2) $X$ is empty” is inconsistent because the axioms directly contradict one another.

An important question is whether the Peano axioms are consistent. Gödel showed that one cannot prove the consistency of a sufficiently strong axiomatic system from within that system. Thus we can only show consistency of the Peano axioms relative to another system. In particular, by constructing the natural numbers inside set theory we show: if set theory is consistent, then the Peano axioms are consistent.

But isn’t the Peano system just a formalization of the counting numbers we use every day? Yes, but the Peano system also asserts there are infinitely many numbers. While that seems obvious for small numbers, the existence of extremely large numbers such as $10^{10^{10}}$ is not physically evident. If one doubts such infinite collections, one must also examine whether the axioms describing them are consistent. The construction above shows that within set theory there is a coherent model for the Peano axioms.