Studentsky logicky seminar

Literatura k tematu "Gödelovy vety a slozitost " (jaro 2011):

(Postupne bude doplnovano.)


  • K.Godel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38, (19310, 173-98.
    English translation.

  • P.Pudlak, a chapter from his forthcoming book, 2011.

  • C.Smorynski, The incompleteness theorems, chapter D1 (pp.821-865) in: Handbook of Mathematical Logic, ed.J.Barwise, Elsevier Science Publishing Co., 1977.
    (elektronickou versi dodam)

    Longer expositions

    Rada standartnich ucebnic logiky ci teorie dukazu podava dukaz Godelovych vet. Dale tez napr.:

  • Torkel Franzen, Godel's Theorem: An Incomplete Guide to Its Use and Abuse, Taylor&Francis Inc., A K Peters, 2005.

  • Peter Smith, An Introduction to Gödel's theorems, CUP. 2005 preliminary version, and its pdf.

  • P.Smith, Godel without tears, 2011 notes. Pdf.

    Proofs using other paradoxes

    These are just rather arbitrary examples:

  • G.Chaitin, Computational complexity and Gödel's incompleteness theorem, ACM SIGACT News, No. 9 (April 1971), pp. 11-12.

  • Shira Kritchman and Ran Raz, The Surprise Examination Paradox and the Second Incompleteness Theorem, Notices AMS, Vol.11, (2010), pp.1454-1458.

    Finitistic Godel's theorem

  • H.Friedman, On the consistency, completeness and correctness probelms, unpublished manuscript, Ohio State Univ., 1979.

  • P. Pudlak: On the length of proofs of finitistic consistency statements in first order theories, in: Logic Colloquium 84, North Holland P.C., 1986 pp.165-196.

  • P. Pudlak: Improved bounds to the length of proofs of finitistic consistency statements. In: Contemporary mathematics Vol.65, 1987 pp.309-331.

    Links with proof complexity

  • S.A.Cook, Feasibly constructive proofs and the propositional calculus , Proc. of 7th annual ACM symposium on Theory of computing, Albuerque, New Mexico, pp.83-97, (1975).

  • J.Krajicek and P.Pudlak, Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations, J. Symbolic Logic, 54(3), (1989), pp. 1063-1079.

    Combinatorial indepence

  • A.Bovykin, Brief introduction to unprovability, in: Logic Colloquium 2006, Lecture Notes in Logic, (2009), pp.38-64.

  • J.Paris and L.Harrington, A Mathematical Incompleteness in Peano Arithmetic, in: Handbook for Mathematical Logic (Ed. J. Barwise). Amsterdam, Netherlands: North-Holland, 1977, pp.1133-1142.


  • J.Krajicek, A Note of Proofs of Falsehood, Archiv f. Mathematikal Logik u. Grundlagen 26 (3-4), (1987), pp. 169-179.

  • P. Pudlak, Cuts, consistency statements and interpretations, Journ. Symb. Logic Vol.50, 1985, pp.423-441.

  • Pavel Pudlak, text o Feasible incompleteness thesis (sekce 3)

  • P. Pudlak: A note on applicability of the incompleteness theorem to human mind, Annals of Pure and Applied Logic 96 (1999), pp. 335-342