Proving the Obvious

GEK1517 Examination / Question 1:

(i) Preface: Peano's Axioms
UT: The set of all natural numbers ℕ = {1, 2, 3, ...}
UT: 1
UT: Successor (here denoted by ')
(A1): 1 is a natural number
(A2): If a number a is a natural number, its successor is also a natural number
(A3): 1 is not the successor to any natural number
(A4): If two numbers have the same successor, they are the same number.
(A5): If 1 is a member of set K, and if for every natural number a, a is a member of K implies that a' is a member of K, then K is the set of all natural numbers. (Mathematical Induction).
The proofs in the following also feature reflexive equality (Ar) strongly. This is the first axiom in Peano's original list of axioms but was omitted from class notes. Essentially, it means x = x.

(ii) In the Peano axiomatic system for natural numbers, addition '+' is given inductively by the following two properties.
(+₁): a + 1 = a' for a ∈ ℕ
(+₂): a + b' = (a + b)' for a, b ∈ ℕ
Using (+₁), (+₂), and mathematical induction, show that
1 + a = a + 1 for all a ∈ ℕ

Solution:
Let P(a) denote (1 + a = a + 1 for all a ∈ ℕ)
P(1): 1 + 1 = 1 + 1 (true because (Ar))
P(k): 1 + k = k + 1 (force true)
P(k'): 1 + k' = k' + 1
(+₁): 1 + k' = (k + 1) + 1
(+₁): 1 + k' = (k + 1)'
(+₂): (1 + k)' = (k + 1)'
(A4): 1 + k = k + 1 (true because P(k))
(A5): Statement proven for for all a ∈ ℕ

Lemma 1 (L1): Commutativity of +
To prove: a + b = b + a for all a, b ∈ ℕ
Let P(a) denote (a + b = b + a) , b ∈ ℕ
P(1): 1 + b = b + 1 (true because (ii))
P(k): k + b = b + k (force true)
P(k'): k' + b = b + k'
(+₁): k + 1 + b = b + k'
(ii): k + b + 1 = b + k'
(+₁): k + b' = b + k'
(+₂): (k + b)' = (b + k)'
(A4): k + b = b + k (true because P(k))
(A5): Statement (L1) proven for for all a, b ∈ ℕ

(iii) In the Peano axiomatic system for natural numbers, multiplication '×' is given inductively by the following two properties.
(×₁): a × 1 = a for a ∈ ℕ
(×₂): a × b' = (a × b) + a for a, b ∈ ℕ
Using (×₁), (×₂), and mathematical induction, show that
a × 2 = a + a, and
a' × b = a × b + b for a, b ∈ ℕ

Solution part 1:
Let P(a) denote (a x 2 = a + a)
P(1): 1 × 2 = 1 + 1
What is 2? Take 2 = 1' (oh no...)
P(1): 1 × 1' = 1 + 1
(×₂): (1 x 1) + 1 = 1 + 1
(×₁): 1 + 1 = 1 + 1 (P(1) true because (Ar))
P(k): k × 2 = k + k (force true)
P(k'): k' × 2 = k' + k'
(2 = 1'): k' × 1' = k' + k'
(×₂): (k' × 1) + k' = k' + k'
(×₁): k' + k' = k' + k' (true because (Ar))
(A5): Statement proven for for all a ∈ ℕ

Solution part 2: Commutativity of ×
Let P(b) denote (a' × b = (a × b) + b), a ∈ ℕ
P(1): a' × 1 = (a × 1) + 1
(×₁): a' = a + 1
(+₁): a' = a' (true because (Ar))
P(k): a' × k = (a × k) + k (force true)
P(k'): a' × k' = (a × k') + k'
(×₂): (a' × k) + a' = (a × k) + a + k'
using P(k): (a × k) + k + a' = (a × k) + a + k'
(+₂): (a × k) + (k + a)' = (a × k) + (a + k)'
(L1): a + k = k + a
so (a × k) + (a + k)' = (a × k) + (a + k)' (true because (Ar))
(A5): Statement proven for for all a, b ∈ ℕ

Colophon:
The idea: you must forget all your arithmetic before you tackle this question. There is no arguing that "everyone knows" a+b = b+a; the only way is to prove it from the given axioms and properties. This is the intellectual equivalent of bailing out from a plane into the rainforest and building civilisation from the bottom up, right down to foraging for food, starting a fire, etc.

This is the first and only real proof in the series... I hope this is rigorous enough, and I hope the formatting makes it clear to follow (Facebook users please allow yourselves to be redirected to the "original post")

Regrettably, I did this only today, when the dust has settled over the exam period and freedom, merriment and general goofing off is in order. Never mind, enjoy the holidays folks.