Máté Szabó is visiting Swansea. He will give a talk today as a part of our theory seminar series: Gödel's and Post's Proofs of the Incompleteness Theorem
This talk examines and compares two strikingly different proofs of the first incompleteness theorem. The first proof of the theorem was famously published by Kurt Gödel in 1931. However, during the previous decade, Emil Post already made significant breakthroughs in this topic, even though he was unable to publish his work for various reasons. After taking a short look at Gödel's diagonal proof, we will engage in more detail with Post's lesser-known proof. The latter proof is purely syntactic, and computer scientists of the day could recognize Post's approach as presenting one of the earliest term rewrite systems. By the end of the talk the audience will hopefully agree with Post stating that “with the Principia Mathematica as a common starting point [i.e. of Gödel and Post], the roads followed towards our common conclusions are so different that much may be gained from a comparison of these parallel evolutions”.
