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.

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.

  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
    
        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
    
  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 $.