# a.1. peano axioms

There are many ways to define the set of natural numbers $\mathbb{N}$ and their arithmetic. One of the most common is the Peano axioms. This appendix contains a brief introduction to the axioms and some properties that can be derived from them.

Peano axioms. The set $\mathbb{N}$ of natural numbers is defined according to the following axioms where $s: \mathbb{N} \to \mathbb{N}$ is the successor function.

1. $0$ is a natural number
2. Every natural number is equal to itself (equality is reflexive)
3. For every pair $a, b$ of natural numbers, if $a = b$, then $b = a$ (equality is symmetric)
4. For every trio $a, b, c$ of natural numbers, if $a = b$ and $b = c$, then $a = c$ (equality is transitive)
5. For every natural number $a$, if $a = b$, then $b$ is a natural number (the natural numbers are closed under equality)
6. For every natural number $a$, the successor $s(a)$ is a natural number (the natural numbers are closed under the successor function)
7. For every pair $a, b$ of natural numbers, $a = b$ if and only if $s(a) = s(b)$ (the successor is a one-to-one function)
8. For every natural number $a$, $s(a) \ne 0$ (there is no natural number whose successor is $0$)
9. If $K$ is a set containing $0$ that is closed under $s$, then $K = \mathbb{N}$ (every natural number besides $0$ is the successor of a natural number)

The decimal expansion of the positive natural numbers are then defined as

• $1 = s(0)$
• $2 = s(1) = s(s(0))$
• $3 = s(2) = s(s(s(0)))$
• $4 = s(3) = s(s(s(s(0))))$
• ...etc

The addition and multiplication of the natural numbers can be defined recursively using the successor function.

• $a + 0 = a$ for all $a \in \mathbb{N}$
• $a + s(b) = s(a + b)$ for all $a, b \in \mathbb{N}$

For example, \begin{align} a + 1 &= a + s(0) = s(a + 0) = s(a) \\ a + 2 &= a + s(1) = s(a + 1) = s(s(a)) \\ a + 3 &= a + s(2) = s(a + 2) = s(s(s(a))) \end{align}

Multiplication.

• $a \cdot 0 = 0$ for all $a \in \mathbb{N}$
• $a \cdot s(b) = a + a \cdot b$ for all $a, b \in \mathbb{N}$

For example, \begin{align} a \cdot 1 &= a \cdot s(0) = a + a \cdot 0 = a + 0 = a \\ a \cdot 2 &= a \cdot s(1) = a + a \cdot 1 = a + a \\ a \cdot 3 &= a \cdot s(2) = a + a \cdot 2 = a + (a + a) \end{align}

The total ordering of the natural numbers is defined as follows.

Total ordering. Given $a, b \in \mathbb{N}$, we say that $a \le b$ if and only if $b = a + n$ for some $n \in \mathbb{N}$.

For example, for any $a \in \mathbb{N}$ \begin{align} a = 0 + a \quad & \longrightarrow \quad 0 \le a \\ a = a + 0 \quad & \longrightarrow \quad a \le a \\ s(a) = s(a + 0) = a + s(0) \quad & \longrightarrow \quad a \le s(a) \end{align}

## models

Set-theoretic model. One explicit construction of the natural numbers uses set theory.

• $0$ is defined to be the empty set
• the successor of a set $a$ is defined to be the union of $a$ with the set containing $a$

\begin{align} 0 &= \{ \} \\ 1 &= s(0) = 0 \cup \{ 0 \} = \{ \} \cup \{ 0 \} = \{ 0 \} \\ 2 &= s(1) = 1 \cup \{ 1 \} = \{ 0 \} \cup \{ 1 \} = \{ 0, 1 \} \\ 3 &= s(2) = 2 \cup \{ 2 \} = \{ 0, 1 \} \cup \{ 2 \} = \{ 0, 1, 2 \} \end{align}

## exercises

Here are just a few examples of familiar properties that can be proved using the Peano axioms. There are a great deal more, but these are enough for this introduction.

1. Define a set-theoretic model of the natural numbers with addition and multiplication using arrays in the programming language of your choice. It will likely be non-performant, but perhaps enlightening.
solution
module Peano
INTEGER_LOOKUP = {}

module_function

def integer(n)
if n.to_i != n || n < 0
raise ArgumentError.new("#{n} is not a natural number")
end

INTEGER_LOOKUP[n] ||= n == 0 ?
Integer.zero :
integer(n - 1).successor
end

class Integer
include Comparable

def self.zero
Integer.new([])
end

def initialize(array)
@array = array
end

def inspect
# eg the number "4" is displayed as [0, 1, 2, 3]
@array.map(&:size)
end

def zero?
@array.empty?
end

def successor
Integer.new(@array + [@array])
end

def predecessor
return if zero?
Integer.new(@array.take(@array.size - 1))
end

def +(other)
return self if other.zero?
(self + other.predecessor).successor
end

def *(other)
return Integer.zero if other.zero?
self + (self * other.predecessor)
end

def <=>(other)
return 0 if @array == other.array
return -1 if (@array - other.array).empty?
return 1 if (other.array - @array).empty?
nil
end

def to_i
@array.size
end
end
end

2. Prove that addition is associative: for any $a, b, c \in \mathbb{N}$ $$(a + b) + c = a + (b + c).$$
solution

Given $a, b \in \mathbb{N}$, define $K$ to be the set of natural numbers that satisfy the associativity relation, ie, $$K = \{ k \in \mathbb{N} \mid (a + b) + k = a + (b + k) \}.$$ Clearly $0 \in K$, since $$(a + b) + 0 = a + b = a + (b + 0).$$ We want to prove that $K$ is closed under the successor function. Let $k \in K$ and consider its successor $s(k)$. The left-hand side of the associativity relation is $$(a + b) + s(k) = s((a + b) + k)$$ and the right-hand side is $$a + (b + s(k)) = a + s(b + k) = s(a + (b + k)).$$ Since $k \in K$, these are equal, which proves that $s(k) \in K$. By Axiom 9, $K$ must be equal to the set of natural numbers, so addition is associative for any $a, b, c \in \mathbb{N}$.

3. Prove that addition is commutative: for any $a, b \in \mathbb{N}$ $$a + b = b + a.$$
solution

For any $k \in \mathbb{N}$, let $C_k$ be the set of natural numbers that commute with $k$, $$C_k = \{ c \in \mathbb{N} \mid k + c = c + k \}.$$ We want to prove that $C_k = \mathbb{N}$ for all $k \in \mathbb{N}$.

We want to use Axiom 9 to do this, so we let $K$ be the set of natural numbers that commute with all natural numbers, $$K = \{ k \in \mathbb{N} \mid C_k = \mathbb{N} \}.$$

Firstly, we prove that $0 \in K$, ie, that $C_0 = \mathbb{N}$ By definition, $0 \in C_0$ (every natural number commutes with itself), so using Axiom 9, it remains to show that $C_0$ is closed under the successor function. Let $c \in C_0$ so that $0 + c = c + 0 = c$. Then $$0 + s(c) = s(0 + c) = s(c) = s(c) + 0,$$ so $s(c) \in C_0$. Therefore, $C_0 = \mathbb{N}$.

Next, suppose that $k \in K$, so that $C_k = \mathbb{N}$. In other words, we know that $k$ commutes with every natural number. Consider the set $C_{s(k})$, the set of natural numbers that commute with $s(k)$. We know that $0 \in C_{s(k)}$ since $0$ commutes with ever natural number. To use Axiom 9 again, let $c$ be an element of $C_{s(k)}$ so that $s(k) + c = c + s(k)$. Now consider $s(c)$: \begin{align} s(k) + s(c) &= s(s(k) + c) \\ &= s(c + s(k)) \\ &= s(s(c + k)) \\ &= s(s(k + c)) \\ &= s(k + s(c)) \\ &= s(s(c) + k) \\ &= s(c) + s(k) \end{align} Therefore $C_{s(k)}$ is closed under the successor function and must be equal to $\mathbb{N}$.

We have now shown that $0 \in K$ and that $K$ itself is closed under the successor function. Therefore, $K = \mathbb{N}$ and addition of natural numbers is commutative.

4. Prove the distributive property: for any $a, b, c \in \mathbb{N}$ $$a \cdot (b + c) = (a \cdot b) + (a \cdot c).$$
solution

Given $a, b$, let $$K = \{ k \in \mathbb{N} \mid a \cdot (b + k) = (a \cdot b) + (a \cdot k) \}.$$ We have that $0 \in K$ since \begin{align} a \cdot (b + 0) &= a \cdot b \\ &= (a \cdot b) + 0 \\ &= (a \cdot b) + (a \cdot 0) \end{align} Given $k \in K$, we can show that $s(k) \in K$ as well: \begin{align} a \cdot (b + s(k)) &= a \cdot s(b + k) \\ &= a + (a \cdot (b + k)) \\ &= (a \cdot (b + k)) + a \\ &= ((a \cdot b) + (a \cdot k)) + a \\ &= (a \cdot b) + ((a \cdot k) + a) \\ &= (a \cdot b) + (a + (a \cdot k)) \\ &= (a \cdot b) + (a \cdot s(k)) \end{align} Therefore $K = \mathbb{N}$ and the distributive law holds in general.

5. Prove that multiplication is associative: for any $a, b, c \in \mathbb{N}$ $$(a \cdot b) \cdot c = a \cdot (b \cdot c).$$
solution

Given $a, b \in \mathbb{N}$, define $K$ to be the set of natural numbers that satisfy the associativity relation, ie, $$K = \{ k \in \mathbb{N} \mid (a \cdot b) \cdot k = a \cdot (b \cdot k) \}.$$ Clearly $0 \in K$, since $$(a \cdot b) \cdot 0 = 0$$ and $$a \cdot (b \cdot 0) = a \cdot 0 = 0.$$ We want to prove that $K$ is closed under the successor function. Let $k \in K$ and consider its successor $s(k)$. Using the distributive law, we get \begin{align} (a \cdot b) \cdot s(k) &= (a \cdot b) + ((a \cdot b) \cdot k) \\ &= (a \cdot b) + (a \cdot (b \cdot k)) \\ &= a \cdot (b + b \cdot k) \\ &= a \cdot (b \cdot s(k)) \end{align} so $s(k) \in K$, which completes the proof.

6. Prove that multiplication is commutative: for any $a, b \in \mathbb{N}$ $$a \cdot b = b \cdot a.$$
solution

For any $k \in \mathbb{N}$, let $C_k$ be the set of natural numbers that commute with $k$, $$C_k = \{ c \in \mathbb{N} \mid k \cdot c = c \cdot k \}.$$ We want to prove that $C_k = \mathbb{N}$ for all $k \in \mathbb{N}$.

We want to use Axiom 9 to do this, so we let $K$ be the set of natural numbers that commute with all natural numbers, $$K = \{ k \in \mathbb{N} \mid C_k = \mathbb{N} \}.$$

Firstly, we prove that $0 \in K$, ie, that $C_0 = \mathbb{N}$ By definition, $0 \in C_0$ (every natural number commutes with itself), so using Axiom 9, it remains to show that $C_0$ is closed under the successor function. Let $c \in C_0$ so that $0 \cdot c = c \cdot 0 = 0$. Then $$0 \cdot s(c) = 0 + 0 \cdot c = 0 + 0 = 0,$$ so $s(c) \in C_0$. Therefore, $C_0 = \mathbb{N}$.

Next, suppose that $k \in K$, so that $C_k = \mathbb{N}$. In other words, we know that $k$ commutes with every natural number. Consider the set $C_{s(k})$, the set of natural numbers that commute with $s(k)$. We know that $0 \in C_{s(k)}$ since $0$ commutes with ever natural number. To use Axiom 9 again, let $c$ be an element of $C_{s(k)}$ so that $s(k) \cdot c = c \cdot s(k)$. Now consider $s(c)$: \begin{align} s(k) \cdot s(c) &= s(k) + (s(k) \cdot c) \\ &= s(k) + (c \cdot s(k)) \\ &= (c \cdot s(k)) + s(k) \\ &= (c + c \cdot k) + s(k) \\ &= c + (c \cdot k + s(k)) \\ &= c + s(c \cdot k + k) \\ &= s(c + (c \cdot k + k)) \\ &= s(c + (k + c \cdot k)) \\ &= s(c + (k + k \cdot c)) \\ &= s((k + k \cdot c) + c) \\ &= s(k + (k \cdot c + c)) \\ &= k + s(k \cdot c + c) \\ &= k + (k \cdot c + s(c)) \\ &= (k + k \cdot c) + s(c) \\ &= (k \cdot s(c)) + s(c) \\ &= s(c) + (k \cdot s(c)) \\ &= s(c) + (s(c) \cdot k) \\ &= s(c) \cdot s(k) \end{align} Therefore $C_{s(k)}$ is closed under the successor function and must be equal to $\mathbb{N}$.

We have now shown that $0 \in K$ and that $K$ itself is closed under the successor function. Therefore, $K = \mathbb{N}$ and multiplication of natural numbers is commutative.

7. Prove that the ordering is transitive: for any $a, b, c \in \mathbb{N}$ if $a \leq b$ and $b \leq c$, then $a \leq c$.
solution

Suppose that $a \leq b$ and $b \leq c$. Then $b = a + m$ and $c = b + n$ for some natural numbers $m, n$. Therefore $$c = b + n = (a + m) + n = a + (m + n)$$ which proves that $a \leq c$.