© | << < ? > >> | Dror Bar-Natan: Talks:

Gödel's Incompleteness Theorem

Graduate Student Seminar, University of Toronto

SS5017, 1PM, January 13, 2005

Abstract. Gödel's Incompleteness Theorem states that any axiomatization of number theory will miss something; that there will always be a number-theoretic statement that is true and yet unprovable. Along with several other celebrated theorems of logic it sets mathematics apart from all other human endeavors - unlike in physics, economy or history, we mathematicians know our foundations. We have an extremely good collection of axioms so we know what we can do. And we even know, quite for sure, what we will never be able to do - prove all that is right, for one.

Gödel's theorem is famed even outside of math, yet not enough of us know how easy it is. Indeed, here's that statement that is true and yet unprovable:

This Statement Has No Proof

Self reference? Maybe. But remember,

  1. Number theory contains computer science; indeed, all that computers can do is to crunch numbers!
  2. A proof given in full detail can be verified by a computer.
  3. One can write a computer program that prints itself. Even, itself followed by the entire Unabomber Manifesto.

Come to my talk and see how all these facts fit together!