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.

A pause, while I regroup....

I had a post I was working on, defining addition and proving its properties, when I ran into a glitch: my proofs didn't work.

Rather than leave you hanging, as if I had forgotten about this blog or got bored and give up, I'm letting you know what's up.

Specifically, I had given a definition of addition of natural numbers, proved it was well-defined, and was attempting to prove that it was commutative. At one part in my proof, I realized that things weren't in the form I needed them, and couldn't continue.

I'll be back soon with a good proof.

Peano's Axioms for natural numbers

The modern formalism of numbers generally begins with the "Natural Numbers" ℕ, which are fairly easy to model, and then builds from there. From natural numbers, one can create a set of definitions for integers, rational numbers, real numbers, and complex numbers, all the way making appropriate definitions for the operators and relations we want to hold for all these different numbers and verifying that the operators and relations hold the way we want. But it all begins with ℕ.

Wikipedia lists 9 axioms in for Peano's Axioms of ℕ, but most formulations I've seen generally list 4 -- the other 5 are either assumed or subsumed by the 4. Peano stated, for instance, that equality of natural numbers was reflexive (a=a), symmetric (a=b implies b=a), transitive (a=b and b=c implies a=c) and closed (if a is a natural number, and a=b, then b is a natural number). In general, people tend to assume these 4 properties of equality, but they are reasonable to state in a full formalization. When we get to defining other numbers in terms of natural numbers, we are going to have to define equality as well, and show that these 4 properties hold for our definitions, so it's good to be explicit about them. But generally, most mathematicians today hold those four properties as being part of the concept of equality.

As for the rest, Peano assumed that the system of natural numbers consisted of two things at it's base, a set ℕ, and a function S:ℕ→ℕ (i.e. a function which takes natural numbers to natural numbers), with the following properties:

A. 1 is a natural number.
B. If n is a natural number, then S(n) is a natural number.
C. For all natural numbers n, S(n) ≠ 1.
D. For all natural numbers n, m, if S(n) = S(m), then n=m
and
E. If P(n) is a proposition on natural numbers such that P(1) is true and if P(n) is true then P(S(n)) is true for all natural numbers n, then P(n) is true for all natural numbers.

The last one is a bit complex, but it allows us to prove things for all natural numbers rather easily. It's simple once you get the hang of it.

S is called the "successor" function, and the axioms can be stated as "B. Every natural number has a unique successor", "C. 1 is not the successor of any number", "D. Every natural number is the successor of at most one number", and "E. If P is true for 1, and true for the successor of any number it is true for, then it is true for all numbers". While this restatement is somewhat less formal, it provides a more fluid way of speaking of the axioms.

Here's an example of a theorem that can be proved using the axioms (and a demonstration of axiom E)

Theorem: Every natural number n other than 1 is the successor of a natural number.
Proof: Let P(n) be the proposition that n is 1 or the successor of a natural number. If P(n) is true for all n, then that proves our theorem. P(1) is obviously true. Assume P(n) is true, then P(S(n)) is true since S(n), by definition, is the successor of a natural number. So P(1) is true, and P(n) implies P(S(n)). By Axiom E, P(n) is therefor true for all natural numbers. That is what we were to demonstrate.

This technique of proving P(1) and proving P(n)→P(S(n)) to prove P(ℕ) is called "mathematical induction", and is a powerful technique. Needless to say, we will be using it alot.

Tomorrow, I'll discuss order.