Teorema ketaklengkapan Gödel

Teorema ketaklengkapan Gödel (bahasa Inggris: Gödel's incompleteness theorems) adalah dua teorema logika matematika yang menetapkan batasan (limitation) inheren dari semua kecuali sistem aksiomatik yang paling trivial yang mampu mengerjakan aritmetika. Teorema-teorema ini, dibuktikan oleh Kurt Gödel pada tahun 1931, penting baik dalam logika matematika maupun dalam filsafat matematika. Kedua hasil ini secara luas, tetapi tidak secara universal, ditafsirkan telah menunjukkan bahwa program Hilbert untuk menghitung himpunan lengkap dan konsisten dari aksioma-aksioma bagi semua matematika adalah tidak mungkin, sehingga memberikan jawaban negatif terhadap soal Hilbert yang kedua.

Teorema ketidaklengkapan Gödel yang pertama pertama kali muncul sebagai "Teorema VI" dalam makalah Gödel pada tahun 1931 berjudul "On Formally Undecidable Propositions in Principia Mathematica and Related Systems I."

Teorema ini ditulis dalam matematika formal yang sangat teknis. Dapat dinyatakan secara lebih sederhana dari terjemahan bahasa Inggris sebagai:

Setiap teori yang dihasilkan secara efektif yang mampu menyatakan aritmetika elementer tidak dapat sama-sama konsisten dan lengkap atau komplet. Khususnya, untuk setiap teori formal yang secara efektif dihasilkan dan yang konsisten, yang membuktikan kebenaran aritmetika dasar tertentu, ada suatu pernyataan aritmetika yang benar,^[1] tetapi tidak dapat dibuktikan dalam teori ini (Kleene 1967, p. 250).

Teorema ketidaklengkapan Gödel yang kedua pertama kali muncul sebagai "Teorema XI" dalam makalah Gödel pada tahun 1931 berjudul "On Formally Undecidable Propositions in Principia Mathematica and Related Systems I."

Sebagaimana dengan teorema ketidaklengkapan pertama, Gödel menulis teorema ini dalam matematika formal yang sangat teknis. Dapat dinyatakan secara lebih sederhana dari terjemahan bahasa Inggris sebagai:

Untuk setiap teori T yang dihasilkan formal secara efektif memuat kebenaran aritmetika dasar dan juga kebenaran tertentuk mengenai provabilitas formal, jika T memuat suatu pernyataan mengenai konsistensinya sendiri,maka T inkonsisten.

Ini menguatkan teorema ketidaklengkapan pertama, karena pernyataan yang dikonstruksi dalam teorema ketidaklengkapan pertama tidak secara langsung menyatakan konsitensi teori itu. Bukti dari teorema ketidaklengkapan kedua diperoleh dengan memformalisasi bukti dari teorema ketidaklengkapan pertama dari dalam teori itu sendiri.

Setelah Gödel mempublikasikan buktinya mengenai teorema kelengkapan sebagai tesis doktoralnya pada tahun 1929, ia beralih kepada problem kedua untuk habilitasinya. Tujuan asalnya adalah untuk memperoleh pemecahan positif dari problem kedua Hilbert (Dawson 1997, p. 63). Pada saat itu, teori-teori bilangan asli dan bilangan real yang mirip dengan aritmetika order kedua dikenal sebagai "analisis", sedangkan teori-teori bilangan asli saja dikenal sebagai "aritmetika".

• Teorema kelengkapan Gödel
• Gödel's speed-up theorem
• Teorema Löb
• Minds, Machines and Gödel
• Münchhausen trilemma
• Non-standard model of arithmetic
• Provability logic
• Tarski's undefinability theorem
• Third Man Argument

1. ^ Kata "benar" digunakan secara disquotational di sini: kalimat Gödel adalah benar dalam hal ini karena "menyatakan unprovability (hakikat tidak dapat dibuktikan) sendiri dan memang unprovable (tidak dapat dibuktikan)" (Smoryński 1977 p. 825; also see Franzén 2005 pp. 28–33). Juga mungkin untuk dibaca sebagai "G_T adalah benar" dalam artian formal bahwa aritmetika rekursif primitif membuktikan implikasi Con(T)→G_T, di mana Con(T) adalah kalimat kanonikal yang menyatakan konsistensi T (Smoryński 1977 p. 840, Kikuchi and Tanaka 1994 p. 403). Namun, pernyataan aritmetika yang dipertanyakan adalah salah dalam sejumlah model aritmetika non-standar.

• 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38: 173-98.
• 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. and On formally undecidable propositions of Principia Mathematica and related systems I in Solomon Feferman, ed., 1986. Kurt Gödel Collected works, Vol. I. Oxford University Press: 144-195. The original German with a facing English translation, preceded by a very illuminating introductory note by Kleene.
  • Hirzel, Martin, 2000, On formally undecidable propositions of Principia Mathematica and related systems I. Diarsipkan 2004-09-16 di Wayback Machine.. A modern translation by Hirzel.
• 1951, Some basic theorems on the foundations of mathematics and their implications in Solomon Feferman, ed., 1995. Kurt Gödel Collected works, Vol. III. Oxford University Press: 304-23.

• B. Meltzer (translation) and R. B. Braithwaite (Introduction), 1962. On Formally Undecidable Propositions of Principia Mathematica and Related Systems, Dover Publications, New York (Dover edition 1992), ISBN 0-486-66980-7 (pbk.) This contains a useful translation of Gödel's German abbreviations on pp. 33–34. As noted above, typography, translation and commentary is suspect. Unfortunately, this translation was reprinted with all its suspect content by

• Stephen Hawking editor, 2005. God Created the Integers: The Mathematical Breakthroughs That Changed History, Running Press, Philadelphia, ISBN 0-7624-1922-9. Gödel's paper appears starting on p. 1097, with Hawking's commentary starting on p. 1089.

• Martin Davis editor, 1965. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable problems and Computable Functions, Raven Press, New York, no ISBN. Gödel's paper begins on page 5, preceded by one page of commentary.
• Jean van Heijenoort editor, 1967, 3rd edition 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, Cambridge Mass., ISBN 0-674-32449-8 (pbk).^[1] van Heijenoort did the translation. He states that "Professor Gödel approved the translation, which in many places was accommodated to his wishes." (p. 595). Gödel's paper begins on p. 595; van Heijenoort's commentary begins on p. 592.
• Martin Davis editor, 1965, ibid. "On Undecidable Propositions of Formal Mathematical Systems." A copy with Gödel's corrections of errata and Gödel's added notes begins on page 41, preceded by two pages of Davis's commentary. Until Davis included this in his volume this lecture existed only as mimeographed notes.

• George Boolos, 1989, "A New Proof of the Gödel Incompleteness Theorem", Notices of the American Mathematical Society v. 36, pp. 388–390 and p. 676, reprinted in Boolos, 1998, Logic, Logic, and Logic, Harvard Univ. Press. ISBN 0-674-53766-1
• Arthur Charlesworth, 1980, "A Proof of Godel's Theorem in Terms of Computer Programs," Mathematics Magazine, v. 54 n. 3, pp. 109–121. JStor
• Martin Davis, "The Incompleteness Theorem", in Notices of the AMS vol. 53 no. 4 (April 2006), p. 414.
• Jean van Heijenoort, 1963. "Gödel's Theorem" in Edwards, Paul, ed., Encyclopedia of Philosophy, Vol. 3. Macmillan: 348-57.
• Geoffrey Hellman, How to Gödel a Frege-Russell: Gödel's Incompleteness Theorems and Logicism. Noûs, Vol. 15, No. 4, Special Issue on Philosophy of Mathematics. (Nov., 1981), pp. 451–468.
• David Hilbert, 1900, "Mathematical Problems." English translation of a lecture delivered before the International Congress of Mathematicians at Paris, containing Hilbert's statement of his Second Problem.
• Kikuchi, Makoto; Tanaka, Kazuyuki (1994), "On formalization of model-theoretic proofs of Gödel's theorems", Notre Dame Journal of Formal Logic, 35 (3): 403–412, doi:10.1305/ndjfl/1040511346, ISSN 0029-4527, MR 1326122 
• Stephen Cole Kleene, 1943, "Recursive predicates and quantifiers," reprinted from Transactions of the American Mathematical Society, v. 53 n. 1, pp. 41–73 in Martin Davis 1965, The Undecidable (loc. cit.) pp. 255–287.
• John Barkley Rosser, 1936, "Extensions of some theorems of Gödel and Church," reprinted from the Journal of Symbolic Logic vol. 1 (1936) pp. 87–91, in Martin Davis 1965, The Undecidable (loc. cit.) pp. 230–235.
• John Barkley Rosser, 1939, "An Informal Exposition of proofs of Gödel's Theorem and Church's Theorem", Reprinted from the Journal of Symbolic Logic, vol. 4 (1939) pp. 53–60, in Martin Davis 1965, The Undecidable (loc. cit.) pp. 223–230
• C. Smoryński, "The incompleteness theorems", in J. Barwise, ed., Handbook of Mathematical Logic, North-Holland 1982 ISBN 978-0-444-86388-1, pp. 821–866.
• Dan E. Willard (2001), "Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles", Journal of Symbolic Logic, v. 66 n. 2, pp. 536–596. DOI:10.2307/2695030
• Richard Zach (2003), "The Practice of Finitism: Epsilon Calculus and Consistency Proofs in Hilbert's Program" (PDF), Synthese, Berlin, New York: Springer-Verlag, 137 (1): 211–259, doi:10.1023/A:1026247421383, ISSN 0039-7857 
• Richard Zach (2005), "Paper on the incompleteness theorems", dalam Ivor Grattan-Guinness, Landmark Writings in Western Mathematics, Elsevier, hlm. 917–25, doi:10.1016/B978-044450871-3/50152-2 

• Francesco Berto. There's Something about Gödel: The Complete Guide to the Incompleteness Theorem John Wiley and Sons. 2010.
• Domeisen, Norbert, 1990. Logik der Antinomien. Bern: Peter Lang. 142 S. 1990. ISBN 3-261-04214-1. Zentralblatt MATH
• Torkel Franzén, 2005. Gödel's Theorem: An Incomplete Guide to its Use and Abuse. A.K. Peters. ISBN 1-56881-238-8 MR2007d:03001
• Douglas Hofstadter, 1979. Gödel, Escher, Bach: An Eternal Golden Braid. Vintage Books. ISBN 0-465-02685-0. 1999 reprint: ISBN 0-465-02656-7. MR80j:03009
• Douglas Hofstadter, 2007. I Am a Strange Loop. Basic Books. ISBN 978-0-465-03078-1. ISBN 0-465-03078-5. MR2008g:00004
• Stanley Jaki, OSB, 2005. The drama of the quantities. Real View Books.
• Per Lindström, 1997, Aspects of Incompleteness, Lecture Notes in Logic v. 10.
• J.R. Lucas, FBA, 1970. The Freedom of the Will. Clarendon Press, Oxford, 1970.
• Ernest Nagel, James Roy Newman, Douglas Hofstadter, 2002 (1958). Gödel's Proof, revised ed. ISBN 0-8147-5816-9. MR2002i:03001
• Rudy Rucker, 1995 (1982). Infinity and the Mind: The Science and Philosophy of the Infinite. Princeton Univ. Press. MR84d:03012
• Smith, Peter, 2007. An Introduction to Gödel's Theorems. Diarsipkan 2005-10-23 di Wayback Machine. Cambridge University Press. MathSciNet^{[pranala nonaktif permanen]}
• N. Shankar, 1994. Metamathematics, Machines and Gödel's Proof, Volume 38 of Cambridge tracts in theoretical computer science. ISBN 0-521-58533-3
• Raymond Smullyan, 1991. Godel's Incompleteness Theorems. Oxford Univ. Press.
• —, 1994. Diagonalization and Self-Reference. Oxford Univ. Press. MR96c:03001
• Hao Wang, 1997. A Logical Journey: From Gödel to Philosophy. MIT Press. ISBN 0-262-23189-1 MR97m:01090

• Francesco Berto. "The Gödel Paradox and Wittgenstein's Reasons" Philosophia Mathematica (III) 17. 2009.
• John W. Dawson, Jr., 1997. Logical Dilemmas: The Life and Work of Kurt Gödel, A. K. Peters, Wellesley Mass, ISBN 1-56881-256-6.
• Goldstein, Rebecca, 2005, Incompleteness: the Proof and Paradox of Kurt Gödel, W. W. Norton & Company. ISBN 0-393-05169-2
• Juliet Floyd and Hilary Putnam, 2000, "A Note on Wittgenstein's 'Notorious Paragraph' About the Gödel Theorem", Journal of Philosophy v. 97 n. 11, pp. 624–632.
• David Hilbert and Paul Bernays, Grundlagen der Mathematik, Springer-Verlag.
• John Hopcroft and Jeffrey Ullman 1979, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, ISBN 0-201-02988-X
• James P. Jones, Undecidable Diophantine Equations, Bulletin of the American Mathematical Society v. 3 n. 2, 1980, pp. 859–862.
• Stephen Cole Kleene, 1967, Mathematical Logic. Reprinted by Dover, 2002. ISBN 0-486-42533-9
• Russell O'Connor, 2005, "Essential Incompleteness of Arithmetic Verified by Coq", Lecture Notes in Computer Science v. 3603, pp. 245–260.
• Graham Priest, 2006, In Contradiction: A Study of the Transconsistent, Oxford University Press, ISBN 0-19-926329-9
• Graham Priest, 2004, Wittgenstein's Remarks on Gödel's Theorem in Max Kölbel, ed., Wittgenstein's lasting significance, Psychology Press, pp. 207–227.
• Graham Priest, 1984, "Logic of Paradox Revisited", Journal of Philosophical Logic, v. 13,` n. 2, pp. 153–179
• Hilary Putnam, 1960, Minds and Machines in Sidney Hook, ed., Dimensions of Mind: A Symposium. New York University Press. Reprinted in Anderson, A. R., ed., 1964. Minds and Machines. Prentice-Hall: 77.
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (edisi ke-3rd), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6 ^{[pranala nonaktif permanen]}.
• Victor Rodych, 2003, "Misunderstanding Gödel: New Arguments about Wittgenstein and New Remarks by Wittgenstein", Dialectica v. 57 n. 3, pp. 279–313. DOI:10.1111/j.1746-8361.2003.tb00272.x
• Stewart Shapiro, 2002, "Incompleteness and Inconsistency", Mind, v. 111, pp 817–32. DOI:10.1093/mind/111.444.817
• Alan Sokal and Jean Bricmont, 1999, Fashionable Nonsense: Postmodern Intellectuals' Abuse of Science, Picador. ISBN 0-312-20407-8
• Joseph R. Shoenfield (1967), Mathematical Logic. Reprinted by A.K. Peters for the Association for Symbolic Logic, 2001. ISBN 978-1-56881-135-2
• Jeremy Stangroom and Ophelia Benson, Why Truth Matters, Continuum. ISBN 0-8264-9528-1
• George Tourlakis, Lectures in Logic and Set Theory, Volume 1, Mathematical Logic, Cambridge University Press, 2003. ISBN 978-0-521-75373-9
• Wigderson, Avi (2010), "The Gödel Phenomena in Mathematics: A Modern View" (PDF), Kurt Gödel and the Foundations of Mathematics: Horizons of Truth, Cambridge University Press 
• Hao Wang, 1996, A Logical Journey: From Gödel to Philosophy, The MIT Press, Cambridge MA, ISBN 0-262-23189-1.
• Richard Zach, 2006, "Hilbert's program then and now", in Philosophy of Logic, Dale Jacquette (ed.), Handbook of the Philosophy of Science, v. 5., Elsevier, pp. 411–447.

• Godel's Incompleteness Theorems di In Our Time di BBC. (listen now)
• (Inggris) Entri Kurt Gödel di Stanford Encyclopedia of Philosophy oleh Juliette Kennedy , July 5, 2011
• (Inggris) Entri Gödel's Incompleteness Theorems di Stanford Encyclopedia of Philosophy oleh Panu Raatikainen, November 11, 2013
• MacTutor biographies:
  • Kurt Gödel. Diarsipkan 2005-10-13 di Wayback Machine.
  • Gerhard Gentzen. Diarsipkan 2012-10-19 di Wayback Machine.
  • What is Mathematics:Gödel's Theorem and Around by Karlis Podnieks. An online free book.
• World's shortest explanation of Gödel's theorem using a printing machine as an example.
• October 2011 RadioLab episode about/including Gödel's Incompleteness theorem
• Hazewinkel, Michiel, ed. (2001) [1994], "Gödel incompleteness theorem", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 

Templat:Metalogic