Peano’s Axioms

In class, we talked a little bit about Peano’s axioms.  Specifically, we talked about how the induction axiom allows us to, well, do induction.  But what are Peano’s axioms, exactly, and what are their importance?

Essentially, Peano’s axioms are the axioms we use to form the Natural numbers.  They are as follows:

1.  There is a natural number 0.

2.  For every natural number x, x=x.

3.  For all natural numbers x and y, if x=y, then y=x.

4.  For all natural numbers x, y and z, if x=y and y=z, then x=z.

5.  For all a and b, if a is a natural number and a=b, then b is a natural number.

6.  For every natural number n, S(n) is a natural number.  S(n) is the successor function (1 is defined as the successor of 0, 2 the successor of 1, and so on).  We would know it as n+1, but we haven’t defined addition yet so we don’t “know” that’s the case yet.

7.  For every natural number n, S(n)=0 is false.  In other words, 0 is not the successor of any natural number n.

8.  For all natural numbers n and m, if s(n)=s(m), then n=m.

And finally, we have the induction axiom:

9.  If K is a set such that 1 is in K and for every natural number n, if n is in K then so is S(n), then K contains every natural number.

Visualizing the induction axiom. Image: Jochen Burghardt, via Wikimedia Commons.

Visualizing the induction axiom. Image: Jochen Burghardt, via Wikimedia Commons.

Along with these axioms, one can define the addition operation as follows:

a.  a + 0 = a

b.  a + S(b) = S(a+b)

Let us calculate 5+3 to see how this works.  According to the formula, this equals 5+S(2), which equals S(5+2), which equals S(5+S(1)), which equals S(S(5+1)), which equals S(S(5+S(0))), which equals S(S(S(5))), which equals 8.

Multiplication is defined similarly, as such:

a.  a*0=0,

b.  a*S(b)=a+(a*b).

Lastly, let us prove that induction is possible.  Specifically, we’d like to prove that for some set of statements P (P(m), for example, might be the statement “m is odd or even”), if P(0) is true and if P(n) implies P(n+1), then P(n) is true for all natural numbers.

To the surprise of perhaps nobody, we use the induction axiom to prove this.  Let K be the set of numbers n for which P(n) is true.  Since 0 is in K and for every n in K, n+1 is also in K, K must have all the natural numbers, so P(n) must be true for every natural number.

Now, at first glance these axioms seem a bit excessive.  I mean, they’re so obvious, right?  But, as it turns out, they’re all extremely necessary.  To show this, I will prove for you something that should sound absurdly trivial:  that m+n=n+m.  Note that from the definitions of addition, this isn’t apparent at all.

We’ll start with another necessary result:  That (k+m)+n=k+(m+n) for all k,m,n.  We can write this as P(n), where k and m are assumed to be any integers and n is a specific one we choose.  First, let us prove it for the case P(0):  (k+m) = k + (m).  So far so good.

Now to prove that P(n) implies P(n+1), or that (k+m)+n=k+(m+n) implies (k+m)+S(n)=k+(m+S(n)).  Well, (k+m)+S(n) = S((k+m)+n)=S(k+(m+n)) on the left side.  On the right side, we have k+(m+S(n))=k+S(m+n)=S(k+(m+n)), so we are done.

Now, we must prove 3 more propositions:  Q(m), which is that m+0=0+m for all m, T(m), which is that m+1=1+m, and R(n), which is for all m and n, m+n=n+m.

To start, we prove that 0+0=0+0.  Even this is non-trivial:  We have to use property 1 of the addition definition to show that 0+0=0, and then use axiom 2 to deduce 0=0.

Now, we prove that if m+0 = 0+m, then (m+1)+0=0+(m+1).  The left hand side is simply m+1, which is s(m).  For the right hand side we use P to rewrite it as (0+m)+1, we use our induction hypothesis to rewrite this as (m+0)+1, then we use the definition of addition to write this as m+1=s(m), thus showing Q(m) holds for all m.

Now, we must show T(m).  Again, we start with our base case:  0+1=1+0.  By Q(1), this is true.

Now, we must show that if m+1=1+m, then (m+1)+1=1+(m+1).  On the left hand side this simply becomes S(m+1).  On the left hand side, we use P to rewrite this as (1+m)+1, and use our induction hypothesis to rewrite this as (m+1)+1, which becomes S(m+1).  So we are done.

Finally, we must prove that if R(n), then R(n+1), that is if m+n=n+m, then m+(n+1)=(n+1)+m.  Using P, rewrite the left side as (m+n)+1=S(m+n).  Using P, we can write the right hand side as n+(1+m).  Using T, we can write this as n+(m+1)=n+S(m)=S(n+m), which we then use the induction step to write as S(m+n).  And now we are finally done.

Notice how long it took to prove even such a trivial looking proposition.  In a sense, that’s the trade-off:  Peano’s axioms are incredibly general and assume very little, but in order to prove even basic results with them a lot of work is required.  In the end though, it’s quite worth the trouble, because you can form (at least with natural numbers alone) the foundations required to do anything you would be doing anyways with just these simple axioms.

It’s important to note that it’s impossible just with Peano’s axioms to develop anything like the real numbers.  In fact, all of Peano’s axioms (besides the induction axiom) are part of what is called First-Order logic, which is not enough to describe mathematics.

The development of Peano’s axioms was extremely important.  In fact, they are still used today, nearly unchanged from when Peano developed them, and they are used in the research of very fundamental questions about mathematics, such as asking about the consistency and completeness of number theory itself.  The fact that such a large amount of mathematics can be built off of such a seemingly small foundation is, to me at least, quite interesting.

Sources:

http://en.wikipedia.org/wiki/Peano_axioms

http://en.wikipedia.org/wiki/First-order_logic

Advertisements

4 thoughts on “Peano’s Axioms

    1. drevelynlamb

      Thanks, you’re right. Those errors were relics of an earlier revision, which used 1 as the first natural number instead of 0. (The axioms can work either way. Peano’s original version had 1 as the first natural number, but 0 makes some things make more sense.)

      Like

      Reply
      1. Matt

        Great! I have OCD when I read math and tech stuff, and the my contribution to the majority of conversations are just pointing out typos… Nice to have resources like this out and available to learn from, so thanks for that.

        Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s