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.
- $ 0 $ is a natural number
- Every natural number is equal to itself (equality is reflexive)
- For every pair $ a, b $ of natural numbers, if $ a = b $, then $ b = a $ (equality is symmetric)
- For every trio $ a, b, c $ of natural numbers, if $ a = b $ and $ b = c $, then $ a = c $ (equality is transitive)
- For every natural number $ a $, if $ a = b $, then $ b $ is a natural number (the natural numbers are closed under equality)
- For every natural number $ a $, the successor $ s(a) $ is a natural number (the natural numbers are closed under the successor function)
- 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)
- For every natural number $ a $, $ s(a) \ne 0 $ (there is no natural number whose successor is $ 0 $)
- 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.
Addition.
- $ 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.
- 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 attr_reader :array 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
- 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} $.
- 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.
- 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.
- 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.
- 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.
- 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 $.