Addition of Naturals, take S(1)....

Ok, I've looked it up figured out where I was going wrong. It turns out it's easier to prove associativity first, and then use that to prove commutivity.

To recap:

Peano's Axioms for Natural numbers are:

A. 1 is a Natural number,
B. If n is a Natural number, then S(n) (read: the successor to n) is also a natural number.
C. If n is a Natural number, then S(n) ≠ 1 (i.e., 1 is not the successor of any natural number.)
D. If S(n) = S(m), then n=m (i.e., every natural number is the successor of at most one natural number).
E. If P(1) is true, and P(n) implies P(S(n)) for all n, then P(n) is true for all n. (the Induction Axiom)

Peano's axioms don't refer to addition directly. It is necessary to define addition such that it has all the properties we associate with addition, assuming Peano's Axioms hold. Peano's Axioms limit what we can talk about, however. Our proofs can only use 1, S, and induction, until we prove other things.

Addition of natural numbers has two standard properties that are typically used in other proofs: associativity and commutivity. "Addition is associative" means that when you have 3 or more numbers added together, the grouping of addition doesn't matter. It's easy to show that if grouping doesn't matter for 3 numbers, it doesn't matter for more. By "grouping", I mean (a+b)+c = a+(b+c). It doesn't matter if you add b to a, then add c to the result, or if you add c to b, then add that to a.

"Addition is commutative", beside being a lyric in a Tom Lehrer song, means that the order of addition doesn't matter. In other words, a+b = b+a.

The trouble with saying "addition is commutative and associative" and leaving it at that is that multiplication is also associative and commutative. So those properties don't distinguish between addition and multiplication. So more properties are needed. I'm not sure how to define such properties, but I'm willing to accept a "spot check": does our definition agree with the notion that 2+3=5? It's not a perfect proof, but it'll do.

We also need to show that our definition is well defined: that a+b is a unique natural number for all natural numbers a, b. That's easy enough to do.

Here's our definition:

Def: Addition + of natural numbers.
If a, b are natural numbers, then
a+1 ≝ S(a)
a+S(b) ≝ S(a+b)

To show that a+b is well-defined, we'll use induction on b. Assume that a is a natural number.
Base case (b=1): By definition, a+b = a+1 = S(a). By property B, S(a) is a well-defined natural number, so a+1 is a well-defined natural number.
Inductive case: Assume that a+b is a well-defined natural number. Then a+S(b) = S(a+b), and the successor of a natural number is a well-defined natural number, so S(a+b) is well-defined, so a+S(b) is well defined. Therefore, a+b is well-defined.

In my first attempt, I tried to prove that addition was commutative. It turns out that it's easier to prove commutativity if you have associativity to work with first. And that's not too difficult to prove (assuming you know the right way to do it).

To show that (a+b)+c = a+(b+c), we'll do it via induction on c. Assume that a, b are natural numbers.

Base case (c=1): (a+b)+1 = S(a+b) = a+S(b) = a+(b+1).
Inductive case: Assume that (a+b)+c = a+(b+c),
then (a+b)+S(c) = S((a+b) + c) = S(a + (b+c)) = a + S(b+c) = a + (b + S(c))
So by induction (a+b)+c = a+(b+c) for all a, b, and c.

To show that addition is commutative, we can use associativity to our advantage. We have to use nested induction proofs: to prove commutativity, we'll use induction on b. To prove the base case, we'll use induction on a.

Base Case (b=1): To show a+1 = 1+a, we'll use induction on a.
SubBaseCase (a=1). If a=1, then we have 1+1 = 1+1, which is trivially true.
SubInduction Case. Assume a+1 = 1+a, then
S(a)+1 = S(S(a)) = S(a+1) = S(1+a) = 1+S(a).
So a+1 = 1+a for all a, thus proving the Base Case.

Induction Case: Assume a+b = b+a. Then
a + S(b)
= a + (b + 1)
= (a + b) + 1 (by associativity)
= (b + a) + 1 (by hypothesis)
= b + (a + 1) (by associativity)
= b + (1 + a) (by the base-case)
= (b + 1) + a (by associativity)
= S(b) + a
So by induction, a+b = b+a for all a, b.

Now to spot-check addition against our idea that 2+3=5, note that 2 = S(1), 3 is S(S(1)), and 5 is S(S(S(S(1)))), so we want to check the value of S(1) + S(S(1))

2 + 3 = S(1) + S(S(1)) = S(S(1) + S(1)) = S( S(S(1) + 1) = S( S( S(S(1)))) = 5, which is just what we expect.

Next stop, the order relationship of integers.