On Wednesday December 5th, there is a talk in the

DIMACS Theory of Computing Seminar which might be

of some interest to logicians:

Place: CORE 431

Time: 11:00 — 12:00

Speaker: Ran Raz (Weizmann Institute & IAS)

Title: The Surprise Examination Paradox and the Second Incompleteness Theorem

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