The Surprise Examination Paradox and the Second Incompleteness Theorem

Preprint English OPEN
Kritchman, Shira; Raz, Ran;
(2010)
  • Subject: Mathematics - Logic | Computer Science - Computational Complexity | Computer Science - Logic in Computer Science

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 t... View more
  • References (14)
    14 references, page 1 of 2

    [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).

  • Metrics
Share - Bookmark