Wednesday, June 29, 2005

Peano's Postulates

"Mathematics is the art of giving the same name to different things." - Jules Henri Poincare

In my class (Automata and Computability Theory) on Tuesday we discussed Peano's Postulates (also known as Peano's axioms. Giuseppe Peano was a mathematican from the late 1880s (he died in the 1930s). He is best known for his work in the area of set theory.

There are 5 Peano's Postulates.
1. 0 is a number
2. If n is a number then the next number after n is n' = n + 1
3. n' = m', iff n = m
4. There is no natural number before 0
5. If P(0) is true and P(n)=>P(n') then for all n, P(n) is true

The 5th statement actual leads us to doing proofs by mathematical induction (assuming that I didn't get any of the axioms wrong). Now I know you are sitting there thinking - what the heck does this have to do with computers? Using these and a proof by induction we can prove that the square root of 2 is irrational and that real numbers are uncountable. Finally, (after a lot of wondering) we can show that there exists numbers that can not be output from a computer program.

OK, so I am sure you know think I am completely nuts, but I hate to tell you I am not. The proof is easier to understand if you know about the while computer language and a few other things - but it true never the less. Maybe at some future date I will post more of the proof if people are interested.

No comments: