Title: The Surprise Examination Paradox and the Second Incompleteness Theorem
Speaker: Ran Raz, The Weizmann Institute of Science & IAS
Date: Wednesday, December 5, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Few theorems in the history of mathematics have inspired mathematicians and philosophers as much as Godel's first and second incompleteness theorems. The first incompleteness theorem states that for any rich enough consistent mathematical theory, there exists a statement that cannot be proved or disproved within the theory. The second incompleteness theorem states that for any rich enough consistent mathematical theory, the consistency of the theory itself cannot be proved (or disproved) within the theory. We give a new proof for Godel's second incompleteness theorem, based on Kolmogorov complexity and an argument that resembles the surprise examination paradox.
We then go the other way around and suggest that the second incompleteness theorem gives a possible resolution of the surprise examination paradox. Roughly speaking, we argue that the flaw in the derivation of the paradox is that it contains a hidden assumption that one can prove the consistency of the mathematical theory in which the derivation is done; which is impossible by the second incompleteness theorem.
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.
Joint work with Shira Kritchman