Wednesday, February 20, 2013

Addition

I just talked about how to define the Natural Numbers. Now let’s talk about addition within them. That is, using the Peano Axioms, we’re going to build the operation of addition under which the Natural Numbers are closed.

Addition is defined recursively by the following:

m + 0 = m

m + S(n) = S(m + n)

So let’s take some number. Any number. Let’s take 3. 3 is the symbol we invented to denote SSS0. So if we want to add 3 to any number:

n + 3 = n + S2 = S(n + 2) = S(n + S1) = SS(n + 1) = SS(n + S0) = SSS(n + 0) = SSS(n)

So adding 3 to any number equals applying the successorship operation on that number thrice. It is in fact easy to show that

image

Therefore, addition is nothing more than repeated succession, and everything we prove using its rules is derived in fact from that repeated succession and the basic Peano Axioms. So let’s prove some properties of addition based on that. For that, we’ll use mathematical induction: we’ll prove that a property is valid at 0, and then prove that validity at k implies validity at S(k).

Commutativity

Basically, we want to prove that m + n = n + m.

Commutativity with 0

First let’s prove that this is valid in the case of k + 0. By definition: 0 + 0 = 0 = 0 + 0, so that’s already valid when k is 0. Furthermore, if any property is valid at 0 and some property being valid at k implies it being valid at S(k), then it’s valid for all natural numbers.

So what we want to see is whether the premise k + 0 = k = 0 + k implies the conclusion S(k) + 0 = S(k) = 0 + S(k).

1. 0 + S(k) = S(0 + k) [Definition of addition]

2. S(0 + k) = S(k + 0) [Premise]

3. S(k + 0) = S(k) [Definition of addition]

4. S(k) = S(k) + 0 [Definition of addition]

Since the commutativity at k implies commutativity at S(k) and we know that addition with 0 commutes at 0, then addition with 0 commutes for all natural numbers.

Commutativity with Successor

Next, we need to know that S(m) + k = S(m + k). We know that this is true for k = 0. If being true at k means it’s also true at S(k) then it will be true for all natural k.

1. S(m) + S(k) = S(S(m) + k) [Definition of addition]

2. S(S(m) + k) = S(S(m + k)) [Premise]

3. S(S(m + k)) = S(m + S(k)) [Definition of addition]

So the commutativity with successor is valid for all natural numbers.

Commutativity for all natural numbers

Next, we want to prove that m + k = k + m. We just proved that this property is valid when k = 0 (i.e. m + 0 = 0 + m). If validity at k implies validity at S(k), then this property will be valid for all natural numbers.

1. m + S(k) = S(m + k) [Definition of addition]

2. S(m + k) = S(k + m) [Premise]

3. S(k + m) = S(k) + m [Commutativity with Successor]

And thus addition is commutative for all natural numbers. Q.E.D.

Associativity

This means that m + (n + p) = (m + n) + p. First, let’s show it’s valid for p = 0:

1. m + (n + 0) = m + n [Definition of addition]

2. m + n = (m + n) + 0 [Definition of addition]

Now we need to prove that validity at p implies validity at S(p), which will prove associativity for all natural numbers.

1. m + (n + S(p)) = m + S(n + p) [Definition of addition]

2. m + S(n + p) = S(m + (n + p)) [Definition of addition]

3. S(m + (n + p)) = S((m + n) + p) [Premise]

4. S((m + n) + p) = (m + n) + S(p) [Definition of addition]

And thus associativity is valid for all natural numbers. Q.E.D.

—-

These properties may have been intuitively obvious, but anyway, it’s a nice example of a mathematical proof at work, where each step produced a true statement from the previous step, and helped us prove formally the obvious based on the very definitions we created.

Notes

  1. genius-vision reblogged this from math-is-beautiful
  2. irazuexperiment reblogged this from math-is-beautiful
  3. can-i-leave-this-blank reblogged this from math-is-beautiful
  4. math-is-beautiful reblogged this from scientiststhesis
  5. scientiststhesis posted this