publication . Preprint . 2010

The Surprise Examination Paradox and the Second Incompleteness Theorem

Kritchman, Shira; Raz, Ran;
Open Access English
  • Published: 22 Nov 2010
We give a new proof for Godel's second incompleteness theorem, based on Kolmogorov complexity, Chaitin's incompleteness theorem, 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.
free text keywords: Mathematics - Logic, Computer Science - Computational Complexity, Computer Science - Logic in Computer Science
Download from

[Boolos89] G. Boolos. A New Proof of the Go¨del Incompleteness Theorem. Notices Amer. Math. Soc. 36: 388-390 (1989)

[Chaitin71] G. J. Chaitin. Computational Complexity and G¨odel's Incompleteness Theorem. ACM SIGACT News 9: 11-12 (1971)

[Chow98] T. Y. Chow. The Surprise Examination or Unexpected Hanging Paradox. Amer. Math. Monthly 105: 41-51 (1998)

[Fitch64] F. Fitch. A Go¨delized Formulation of the Prediction Paradox. Amer. Phil. Quart. 1: 161-164 (1964)

[Go¨del31] K. Go¨del. U¨ ber formal unentscheidbare Sa¨tze der Principia Mathematica und verwandter Systeme I. Monatshehte fu¨r Mathematik und Physik 38: 173-198 (1931)

[HM86] J. Halpern, Y. Moses. Taken by Surprise: The Paradox of the Surprise Test Revisited. Journal of Philosophical Logic 15: 281-304 (1986)

[Kikuchi94] M. Kikuchi. A Note on Boolos' Proof of the Incompleteness Theorem. Math. Logic Quart. 40: 528-532 (1994)

[Kikuchi97] M. Kikuchi. Kolmogorov Complexity and the Second Incompleteness Theorem. Arch. Math. Logic 36: 437-443 (1997)

[Kotlarski04] H. Kotlarski. The Incompleteness Theorems After 70 Years. Ann. Pure Appl. Logic 126: 125-138 (2004)

[Kreisel50] G. Kreisel. Notes on Arithmetical Models for Consistent Formulae of the Predicate Calculus. Fund. Math. 37: 265-285 (1950).

[Mendelson97] E. Mendelson. Introduction to Mathematical Logic. CRC Press (1997)

[Shaw58] R. Shaw. The Unexpected Examination. Mind 67: 382-384 (1958)

[Smoryn´ski77] C. A. Smoryn´ski. The Incompleteness Theorem. In: Introduction to Mathematical Logic (J. Barwise, ed.). North-Holland, 821-865 (1977).

[Vopenka66] P. Vopenka. A New Proof on the Go¨del's Result of Non-Provability of Consistency. Bull. Acad. Polon. Sci. 14: 111-116 (1966)

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue