The Surprise Examination Paradox and the Second Incompleteness Theorem

Mathematical Conversations
Topic:The Surprise Examination Paradox and the Second Incompleteness Theorem
Speaker:Ran Raz
Affiliation:Weizmann Institute of Science; Visiting Professor, School of Mathematics
Date:Friday, November 14
Time/Room:6:00pm - 7:00pm/Dilworth Room

Few theorems in the history of mathematics have inspired mathematicians and philosophers as much as Godel’s first and second incompleteness theorems. I will present a new proof for Godel's second incompleteness theorem, based on Kolmogorov complexity and an argument that resembles the surprise examination paradox. If time allows, I will show (or, more realistically, just hint) how to go the other way around and suggest that the second incompleteness theorem gives a possible resolution of the surprise examination paradox. I will start with a short informal introduction to the known proofs for Godel's incompleteness theorems and their relations to the liar paradox, Kolmogorov complexity and Berry's paradox. No knowledge in logic will be assumed. Based on a joint work with Shira Kritchman.