Published on February 5th, 2014 | by Emily Corbett0
Kurt Gödel’s famous incompleteness theorem
By Christopher Taylor, La Trobe University
This student took part in the 2012/13 AMSI Vacation Research Scholarship program. For more information on this years program please click here
Kurt Gödel’s famous incompleteness theorem states that any system of axioms capable of describing elementary arithmetic cannot be simultaneously consistent and complete. A direct consequence of this is that if a system contains no contradictions, then there must be something that can be stated within the system and is true, but cannot be proven so.
One way of interpreting this is to consider the <i>Peano axioms</i>. The Peano axioms are a standard system used to describe the natural numbers. Assuming the Peano axioms are consistent, we can then use them to write a statement about the natural numbers that is true, but which the Peano axioms cannot tell you about. We say that such a statement is <i>independent</i> of the Peano axioms.
Gödel’s theorem is constructive, that is to say, its proof directly results in a statement that is true but not provable within the given system. The statement is highly logical and not particularly accessible. However, some accessible examples of statements that can be shown to be true but not provable within Peano have been found. My project involved gaining an understanding of these theorems and setting up the required tools to prove them true.
One may ask how you show that something is true if it’s already known to be unprovable. It’s easy: you just use a different system. For instance, two of the theorems I looked at – Goodstein’s Theorem and The Hydra Game – are unprovable within the Peano axioms, but can be proven true using <i>ordinal numbers</i>, which are an extension of the natural numbers used to describe well-ordered sets.
I looked at four different theorems in the project: Goodstein’s Theorem, Kirby & Paris’s Hydra Game, Friedman’s Long Finite Sequences, and Friedman’s Tree Embedding Theorem. Unfortunately, the details of the theorems are too technical to include here.
By looking at these theorems, I found that the intuition behind their unprovability is that certain numbers involved simply grow too quickly for Peano arithmetic to describe. There were frequent comparisons to the <i>Ackermann function</i>, a well-studied function known to grow extremely quickly at very low values – for instance, A(5,5) is described by Friedman as being “incomprehensibly large”. One of the functions involved with Fridman’s Tree Embedding Theorem, TREE(k), grows so quickly that a lower bound on TREE(3) involves repeated applications of the Ackermann function to itself, A(187196,187196) times. This number is remarkably huge, and reflects how quickly some of the associated functions grow.
I’d like to thank AMSI for giving me the opportunity to undertake this project and to speak at the Big Day In. It was a valuable experience to get an understanding of mathematical research and to speak among my peers. I would also like to thank my supervisor, Marcel Jackson, for providing the resources used and for assisting me in the project.