Teorema ketaklengkapan Gödel (bahasa Inggris:Gödel's incompleteness theoremscode: en is deprecated ) adalah dua teoremalogika 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 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).
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.
Sejarah
Setelah Gödel memublikasikan 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".
↑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 "GT adalah benar" dalam artian formal bahwa aritmetika rekursif primitif membuktikan implikasi Con(T)→GT, 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.
Bibliografi
Artikel tulisan Gödel
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.
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.
Terjemahan makalah Gödel ke dalam bahasa Inggris semasa hidupnya
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.
Referensi
↑van Heijenoort, Jean. "From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931". This link goes to the Google Books page for the text. The original print book was published by Harvard University Press in 1977 and is widely available from booksellers. Diakses tanggal 9 April 2014.
Pustaka tambahan
Artikel oleh penulis lain
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
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, ISSN0029-4527, MR1326122
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.
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.
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.
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
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", 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.
