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.

Teori ketidaklengkapan pertama

sunting

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 kedua

sunting

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.

Sejarah

sunting

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".

Lihat pula

sunting

Catatan

sunting
  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 "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

sunting

Artikel tulisan Gödel

sunting
  • 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

sunting
  • 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

sunting
  1. ^ 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

sunting

Artikel oleh penulis lain

sunting

Buku-buku mengenai teorema

sunting

Pustaka lain-lain

sunting

Pranala luar

sunting

Templat:Metalogic