a.1. peano axioms

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