Salah satu teorema logika matematika yang paling terkenal, beruntung dan tidak beruntung pada saat bersamaan. Dalam hal ini mirip dengan teori relativitas khusus Einstein. Di satu sisi, hampir semua orang telah mendengar sesuatu tentang mereka. Di sisi lain, dalam interpretasi populer, teori Einstein, seperti yang Anda ketahui, "mengatakan segala sesuatu di dunia ini relatif". Dan teorema ketidaklengkapan Gödel (selanjutnya hanya TGN), dalam formulasi rakyat yang kira-kira sama bebasnya, "membuktikan bahwa ada hal-hal yang tidak dapat dipahami oleh pikiran manusia". Maka beberapa orang mencoba untuk mengadaptasinya sebagai argumen melawan materialisme, sementara yang lain, sebaliknya, membuktikan dengan bantuannya bahwa tidak ada Tuhan. Ini lucu tidak hanya bahwa kedua belah pihak tidak bisa benar pada saat yang sama, tetapi juga bahwa tidak satu atau yang lain peduli untuk mencari tahu apa sebenarnya yang dikatakan teorema ini.
Terus? Di bawah ini saya akan mencoba "dengan jari" untuk membicarakannya. Eksposisi saya, tentu saja, tidak ketat dan intuitif, tetapi saya akan meminta ahli matematika untuk tidak menilai saya secara ketat. Mungkin saja bagi non-matematika (yang sebenarnya saya juga termasuk), akan ada sesuatu yang baru dan berguna dalam apa yang diceritakan di bawah ini.
Logika matematika memang ilmu yang agak rumit, dan yang terpenting, tidak terlalu familiar. Ini membutuhkan manuver yang hati-hati dan ketat, di mana penting untuk tidak membingungkan yang benar-benar terbukti dengan fakta bahwa "itu sudah jelas." Namun, saya berharap untuk memahami “garis besar pembuktian TGN” berikut ini, pembaca hanya membutuhkan pengetahuan matematika sekolah / ilmu komputer, keterampilan berpikir logis dan waktu 15-20 menit.
Menyederhanakan agak, TGN menegaskan bahwa dalam bahasa yang cukup kompleks ada proposisi yang tidak dapat dibuktikan. Namun dalam kalimat ini, hampir setiap kata membutuhkan penjelasan.
Mari kita mulai dengan mencoba mencari tahu apa itu bukti. Mari kita ambil beberapa masalah sekolah dalam aritmatika. Misalnya, biarkan diperlukan untuk membuktikan kebenaran rumus sederhana berikut: "" (Saya mengingatkan Anda bahwa simbol dibaca "untuk apa saja" dan disebut "kuantifier universal"). Ini dapat dibuktikan dengan mentransformasikan secara identik, katakanlah, seperti ini:
Transisi dari satu formula ke formula lain terjadi sesuai dengan aturan tertentu yang terkenal. Transisi dari rumus ke-4 ke rumus ke-5 terjadi, katakanlah, karena setiap bilangan sama dengan dirinya sendiri - demikianlah aksioma aritmatika. Dan seluruh prosedur pembuktian, dengan demikian, menerjemahkan rumus ke dalam nilai boolean TRUE. Hasilnya bisa SALAH - jika kita menyangkal beberapa formula. Dalam hal ini, kami akan membuktikan negasinya. Adalah mungkin untuk membayangkan sebuah program (dan program semacam itu sebenarnya ditulis) yang akan membuktikan proposisi semacam itu (dan lebih kompleks) tanpa campur tangan manusia.
Mari kita nyatakan hal yang sama sedikit lebih formal. Misalkan kita memiliki satu set yang terdiri dari string karakter dari beberapa alfabet, dan ada aturan di mana subset dari apa yang disebut pernyataan- yaitu, frasa yang bermakna secara tata bahasa, yang masing-masing benar atau salah. Kita dapat mengatakan bahwa ada fungsi yang cocok dengan pernyataan dari salah satu dari dua nilai: TRUE atau FALSE (yaitu, memetakannya ke kumpulan dua elemen Boolean).
Mari kita panggil pasangan seperti itu - satu set pernyataan dan fungsi dari ke - "bahasa pernyataan". Perhatikan bahwa dalam pengertian sehari-hari konsep bahasa agak lebih luas. Misalnya, frasa Rusia "Nah, datang ke sini!" tidak benar dan tidak salah, yaitu dari sudut pandang logika matematika, itu bukan pernyataan.
Untuk apa yang berikut, kita membutuhkan gagasan tentang suatu algoritma. Saya tidak akan memberikan definisi formalnya di sini - ini akan membawa kita cukup jauh ke samping. Saya akan membatasi diri pada informal: "algoritma"- urutan instruksi yang tidak ambigu ini ("program"), yang dalam jumlah langkah yang terbatas mengubah data masukan menjadi keluaran. Huruf miring pada dasarnya penting - jika program terhenti pada beberapa data awal, maka itu tidak menjelaskan algoritme. Untuk kesederhanaan dan dalam aplikasi untuk kasus kami, pembaca dapat mempertimbangkan bahwa algoritma adalah program yang ditulis dalam bahasa pemrograman apa pun yang dikenalnya, yang, untuk data input apa pun dari kelas tertentu, dijamin untuk menyelesaikan pekerjaannya dengan hasil Boolean.
Mari kita bertanya pada diri sendiri: apakah ada "algoritma pembuktian" untuk setiap fungsi (atau, singkatnya, "deduktif") setara dengan fungsi ini, yaitu menerjemahkan setiap pernyataan ke dalam nilai boolean yang sama persis dengannya? Lebih ringkasnya, pertanyaan yang sama dapat dirumuskan sebagai berikut: apakah setiap fungsi di atas sekumpulan proposisi? dapat dihitung? Seperti yang sudah bisa Anda tebak, validitas TGN mengikuti bahwa tidak, tidak ada - ada fungsi yang tidak dapat dihitung dari jenis ini. Dengan kata lain, tidak setiap pernyataan yang benar dapat dibuktikan.
Sangat mungkin bahwa pernyataan ini akan menyebabkan Anda protes internal. Hal ini disebabkan oleh beberapa keadaan. Pertama, ketika kita diajarkan matematika sekolah, terkadang ada kesan yang salah bahwa frasa “teorema itu benar” dan “teorema dapat dibuktikan atau diverifikasi” hampir identik. Tapi kalau dipikir-pikir, itu sama sekali tidak jelas. Beberapa teorema terbukti cukup sederhana (misalnya, dengan menghitung sejumlah kecil opsi), dan beberapa sangat sulit. Pertimbangkan, misalnya, Teorema Terakhir Fermat yang terkenal:
bukti yang ditemukan hanya tiga setengah abad setelah formulasi pertama (dan itu jauh dari dasar). Penting untuk membedakan antara kebenaran suatu pernyataan dan pembuktiannya. Itu tidak berarti bahwa tidak ada pernyataan yang benar, tetapi tidak dapat dibuktikan (dan tidak sepenuhnya dapat diverifikasi).
Argumen intuitif kedua melawan TGN lebih halus. Misalkan kita memiliki beberapa pernyataan yang tidak dapat dibuktikan (dalam kerangka deduktif ini). Apa yang mencegah kita menerimanya sebagai aksioma baru? Jadi, kami akan sedikit memperumit sistem pembuktian kami, tetapi ini tidak buruk. Argumen ini akan sepenuhnya benar jika ada sejumlah proposisi yang tidak dapat dibuktikan. Dalam praktiknya, hal berikut dapat terjadi - setelah mendalilkan aksioma baru, Anda akan menemukan pernyataan baru yang tidak dapat dibuktikan. Ambillah sebagai aksioma lain - Anda akan menemukan yang ketiga. Dan seterusnya ad infinitum. Mereka mengatakan deductica akan tetap tidak lengkap. Kami juga dapat mengambil tindakan tegas sehingga algoritme pembuktian berakhir setelah sejumlah langkah terbatas dengan beberapa hasil untuk pernyataan bahasa apa pun. Tetapi pada saat yang sama, dia akan mulai berbohong - mengarah pada kebenaran untuk pernyataan yang salah, atau kebohongan - untuk orang beriman. Dalam kasus seperti itu dikatakan bahwa deduktif kontradiktif. Dengan demikian, satu lagi formulasi TGN terdengar seperti ini: "Ada bahasa proposisi yang tidak memungkinkan deduksi konsisten yang lengkap" - karenanya nama teorema.
Kadang-kadang disebut "teorema Godel" adalah pernyataan bahwa setiap teori mengandung masalah yang tidak dapat dipecahkan dalam kerangka teori itu sendiri dan memerlukan generalisasinya. Dalam arti tertentu ini benar, meskipun formulasi seperti itu mengaburkan masalah daripada memperjelasnya.
Saya juga mencatat bahwa jika kita berbicara tentang fungsi biasa yang memetakan himpunan bilangan real ke dalamnya, maka "non-komputabilitas" dari fungsi tersebut tidak akan mengejutkan siapa pun (jangan bingung antara "fungsi yang dapat dihitung" dan "angka yang dapat dihitung" - ini adalah hal yang berbeda). Setiap anak sekolah tahu bahwa, katakanlah, dalam kasus suatu fungsi, Anda pasti sangat beruntung dengan argumennya sehingga proses penghitungan representasi desimal yang tepat dari nilai fungsi ini berakhir dalam sejumlah langkah yang terbatas. Dan kemungkinan besar Anda akan menghitungnya menggunakan deret tak hingga, dan perhitungan ini tidak akan pernah menghasilkan hasil yang pasti, meskipun bisa mendekati itu - hanya karena nilai sinus dari sebagian besar argumen tidak rasional. TGN hanya memberi tahu kita bahwa bahkan di antara fungsi yang argumennya adalah string dan nilainya nol atau satu, fungsi yang tidak dapat dihitung, meskipun diatur dengan cara yang sama sekali berbeda, juga ada.
Untuk selanjutnya, kami akan menjelaskan "bahasa aritmatika formal". Mari kita pertimbangkan kelas string teks dengan panjang terbatas, yang terdiri dari angka Arab, variabel (huruf alfabet Latin) yang mengambil nilai alami, spasi, tanda operasi aritmatika, persamaan dan ketidaksetaraan, quantifier (“ada”) dan (“untuk any”) dan, mungkin, , beberapa simbol lain (jumlah dan komposisi persisnya tidak penting bagi kami). Jelas bahwa tidak semua baris seperti itu bermakna (misalnya, "" tidak masuk akal). Bagian dari ekspresi bermakna dari kelas ini (yaitu, string yang benar atau salah dalam istilah aritmatika biasa) akan menjadi kumpulan pernyataan kami.
Contoh pernyataan aritmatika formal:
dll. Sekarang mari kita sebut "rumus dengan parameter bebas" (FSP) string yang menjadi pernyataan jika bilangan asli diganti ke dalamnya sebagai parameter ini. Contoh FSP (dengan parameter):
dll. Dengan kata lain, FSP setara dengan fungsi argumen alami dengan nilai Boolean.
Tunjukkan himpunan semua FSP dengan huruf. Jelas bahwa itu dapat diurutkan (misalnya, pertama-tama kita menulis rumus satu huruf yang diurutkan menurut abjad, diikuti oleh rumus dua huruf, dll.; tidak mendasar bagi kami di alfabet mana urutan akan dilakukan). Dengan demikian, FSP apa pun sesuai dengan nomornya dalam daftar yang dipesan, dan kami akan menunjukkannya .
Sekarang mari kita beralih ke sketsa bukti TGN dalam rumusan berikut:
- Untuk bahasa proposisional aritmatika formal, tidak ada deduksi yang konsisten dan lengkap.
Kami akan membuktikan dengan kontradiksi.
Jadi mari kita asumsikan bahwa deduktif seperti itu ada. Mari kita jelaskan algoritma bantu berikut yang memberikan nilai boolean ke bilangan asli sebagai berikut:
Sederhananya, algoritma menghasilkan nilai TRUE jika dan hanya jika hasil subtitusi ke dalam FSP nomornya sendiri dalam daftar kami memberikan pernyataan yang salah.
Di sini kita datang ke satu-satunya tempat di mana saya akan meminta pembaca untuk mengambil kata-kata saya untuk itu.
Jelas, di bawah asumsi di atas, setiap FSP dari dapat dikaitkan dengan algoritma yang berisi bilangan asli pada input dan nilai Boolean pada output. Yang kurang jelas adalah kebalikannya:
Bukti dari lemma ini akan membutuhkan setidaknya definisi formal, bukan intuitif, dari gagasan suatu algoritma. Namun, jika Anda memikirkannya sedikit, itu cukup masuk akal. Memang, algoritma ditulis dalam bahasa algoritmik, di antaranya ada yang eksotis seperti, misalnya, Brainfuck , yang terdiri dari delapan kata satu karakter, di mana, bagaimanapun, algoritma apa pun dapat diimplementasikan. Akan aneh jika bahasa yang lebih kaya dari rumus aritmatika formal yang telah kami jelaskan ternyata lebih buruk - meskipun, tidak diragukan lagi, itu tidak terlalu cocok untuk pemrograman biasa.
Setelah melewati tempat yang licin ini, kami segera sampai di ujung.
Jadi, kami telah menjelaskan algoritma di atas. Menurut lemma yang saya minta untuk Anda percayai, ada FSP yang setara. Ini memiliki beberapa nomor dalam daftar - katakanlah . Mari kita bertanya pada diri kita sendiri, apa gunanya? Biarkan itu menjadi BENAR. Kemudian, menurut konstruksi algoritme (dan karenanya fungsi yang setara dengannya), ini berarti bahwa hasil mensubstitusikan suatu bilangan ke dalam fungsi adalah FALSE. Kebalikannya diperiksa dengan cara yang sama: dari FALSE mengikuti TRUE. Kita telah sampai pada suatu kontradiksi, yang berarti bahwa asumsi semula salah. Jadi, untuk aritmatika formal, tidak ada deduksi konsisten yang lengkap. Q.E.D.
Di sini tepat untuk mengingat Epimenides (lihat potret dalam judul), yang, seperti yang Anda ketahui, menyatakan bahwa semua orang Kreta adalah pembohong, karena dirinya sendiri adalah orang Kreta. Dalam rumusan yang lebih ringkas, pernyataannya (dikenal sebagai "paradoks pembohong") dapat dirumuskan sebagai: "Saya berbohong." Justru pernyataan seperti itu, yang dengan sendirinya menyatakan kepalsuannya, telah kami gunakan sebagai bukti.
Sebagai kesimpulan, saya ingin mencatat bahwa TGN tidak mengklaim sesuatu yang sangat mengejutkan. Lagi pula, semua orang telah lama terbiasa dengan fakta bahwa tidak semua angka dapat direpresentasikan sebagai rasio dua bilangan bulat (ingat, pernyataan ini memiliki bukti yang sangat elegan yang berusia lebih dari dua ribu tahun?). Dan akar-akar polinomial dengan koefisien rasional juga tidak semuanya bilangan. Dan sekarang ternyata tidak semua fungsi argumen alami dapat dihitung.
Sketsa bukti yang diberikan adalah untuk aritmatika formal, tetapi tidak sulit untuk melihat bahwa THN juga berlaku untuk banyak bahasa proposisional lainnya. Tentu tidak semua bahasa seperti itu. Misalnya, mari kita definisikan bahasa seperti ini:
- "Setiap frasa dalam bahasa Cina adalah pernyataan yang benar jika ada dalam buku kutipan Kamerad Mao Tse Tung, dan tidak benar jika tidak ada."
Kemudian algoritme pembuktian yang lengkap dan konsisten yang sesuai (dapat disebut "deduktif dogmatis") terlihat seperti ini:
- “Baliklah buku kutipan Kamerad Mao Tse Tung sampai Anda menemukan pernyataan yang Anda cari. Jika ditemukan, maka benar, dan jika buku kutipan selesai, dan pernyataan tidak ditemukan, maka itu salah.
Di sini kita diselamatkan oleh fakta bahwa kutipan apa pun jelas terbatas, sehingga proses "pembuktian" pasti akan berakhir. Dengan demikian, TGN tidak dapat diterapkan pada bahasa pernyataan dogmatis. Tapi kita berbicara tentang bahasa yang kompleks, bukan?
Ide dari pembuktiannya adalah untuk membangun sebuah ekspresi yang akan membuktikannya
ketidakterbuktian sendiri. Membangun ini dapat dilakukan dalam tiga langkah:
Tahap pertama adalah pembentukan korespondensi antara aritmatika formal dan himpunan bilangan bulat (gedelisasi);
Tahap kedua adalah konstruksi beberapa properti khusus yang tidak diketahui apakah itu teorema aritmatika formal atau bukan;
Tahap ketiga adalah substitusi sebagai ganti x dari bilangan bulat tertentu yang terkait dengan dirinya sendiri, yaitu penggantian dengan angka-angka ini dari semua
Tahap pertama. Godelisasi aritmatika formal
Aritmatika formal dapat diaritmatika (yaitu, Gaedelized) dengan cara berikut: masing-masing teorema diberi nomor tertentu. Namun, karena bilangan apa pun juga merupakan teorema, maka teorema apa pun dapat dianggap, di satu sisi, sebagai teorema aritmatika formal, dan di sisi lain, sebagai teorema di atas seperangkat teorema aritmatika formal, yaitu sebagai metateorema yang sesuai dengan bukti teorema tertentu.
Dengan demikian, kita dapat menyimpulkan bahwa sistem aritmatika formal juga mengandung metasistemnya sendiri.
Kami sekarang menyajikan hasil kami lebih konkret dan rinci.
Pertama, kita dapat mengasosiasikan dengan setiap simbol dan aritmatika formal sebuah kode khusus yang disebut dalam hal ini bilangan Gödel
Kedua, kami menetapkan untuk setiap urutan karakter nomor Gödel yang sama menggunakan beberapa fungsi komposisi Let mana urutan karakter yang membentuk
Ketiga (dan ini penting), setiap bukti barisan aksioma dan aturan substitusi (atau aturan substitusi) diberi nomor di mana menunjukkan urutan teorema yang digunakan dalam pembuktian.
Jadi, untuk bukti apa pun dalam aritmatika formal ada bilangan tertentu yang sesuai - bilangan Gödelnya.Penalaran apa pun dari aritmatika formal diubah menjadi perhitungan pada himpunan bilangan asli.
Jadi, alih-alih memanipulasi simbol, teorema, bukti, Anda dapat menggunakan
perhitungan pada himpunan bilangan bulat. Ekspresi apa pun seperti, misalnya, berikut ini: dapat dibuktikan dalam aritmatika formal," sekarang sesuai dengan angka tertentu, yang akan kita nyatakan sebagai
Mari kita rumuskan proposisi berikut.
Metaaritmatika formal terkandung dalam himpunan bilangan asli, dan itu sendiri terkandung dalam interpretasi aritmatika formal.
Situasi dengan aritmatika formal ini menyerupai situasi dengan bahasa alami: lagi pula, tidak ada yang menghalangi kita untuk menggunakannya untuk merumuskan konsep dan aturan dasarnya di dalamnya.
Pilihan fungsi yang tepat memungkinkan seseorang untuk membuat transisi yang jelas dari A ke, yaitu, untuk menetapkan dua bilangan-bilangan yang berbeda ke dua bukti yang berbeda. Misalnya, seseorang dapat memilih angka Gödel sedemikian rupa sehingga setiap simbol alfabet aritmatika formal memiliki bilangan primanya sendiri, seperti yang ditunjukkan, misalnya, pada Tabel 1. 3.2.
Tabel 3.2
Setiap rumus (terdiri dari simbol-simbol yang bervariasi dari 1 hingga pada gilirannya dikodekan oleh urutan yang terdiri dari bilangan prima pertama, yaitu bilangan
dimana adalah bilangan prima.
Pada gilirannya, buktinya, yaitu urutan rumus akan dikodekan dengan cara yang sama dengan nomor
Dan sebaliknya, berkat metode pembentukan bilangan ini, menjadi mungkin, mulai dari bilangan tertentu, dengan menguraikannya menjadi faktor prima (karena keunikan penguraian bilangan asli menjadi produk dari kekuatan bilangan prima), untuk kembali menjadi dua. langkah-langkah ke eksponen, yaitu, ke simbol primitif aritmatika formal. Tentu saja, ini sebagian besar penting secara teoritis, karena jumlahnya dengan cepat menjadi terlalu besar.
sehingga mereka dapat dimanipulasi. Namun, perlu dicatat bahwa kemungkinan mendasar dari operasi ini sangat penting.
Contoh. Biarkan nomor T diberikan, sesuai dengan beberapa bukti dan mewakili produk bilangan prima:
Penguraian ini berarti bahwa pembuktian teorema mengandung dua tahap: satu sesuai dengan bilangan 1981027125 253, dan yang lainnya dengan bilangan 1981027125 211. Menguraikan lagi menjadi faktor prima masing-masing bilangan ini, kita dapatkan
Dari tabel pengkodean alfabet aritmatika formal (Tabel 3.2) kami menemukan bahwa angka Gödel kami untuk dua angka ini
akan cocok dengan bukti berikut:
Rumus mengikuti dari rumus
Jadi, dalam metaaritmatika, nilai bilangan asli diperoleh dari aritmatika formal.
Fase kedua. Lemma Godel
Setiap bilangan T yang diasosiasikan dengan suatu pembuktian sesuai dengan suatu teorema yang dapat dibuktikan dalam aritmatika formal. Aritmatika formal “tergaudelisasi” disebut aritmatika formal teraritmatika. Karena setiap aksioma dan setiap aturan aritmatika formal berkorespondensi dengan beberapa operasi aritmatika, maka dengan bantuan pemeriksaan sistematis dimungkinkan untuk menentukan apakah bilangan T yang diberikan sesuai dengan bukti beberapa teorema bilangan T dan dalam hal ini bentuk sepasang bilangan konjugasi. Ekspresi dan adalah konjugat” Dapat diwakili dalam aritmatika formal yang paling banyak di aritmatika. Artinya ada bilangan Gödel yang mendigitalkan pernyataan ini.
Kami telah sampai pada titik kritis dari bukti Gödel. Misalkan A adalah ekspresi dari aritmatika formal yang mengandung beberapa variabel bebas. Sebagai gantinya, Anda dapat membuat substitusi dari beberapa istilah. Secara khusus, dimungkinkan untuk mengganti ekspresi A dengan ekspresi A itu sendiri. Dalam hal ini, ekspresi bilangan A secara bersamaan melakukan dua peran yang berbeda (lihat konstruksi di atas
Cantor dan Richard): itu adalah ekspresi sebenarnya untuk substitusi dan istilah yang dihasilkan. Substitusi khusus ini akan dilambangkan sebagai Jadi rumusnya berarti bahwa bilangan tersebut adalah bilangan Gödel yang diperoleh dengan mengganti - ke ekspresi A:
Gödel kemudian membangun sebuah ekspresi (yang tidak diketahui apakah itu teorema atau non-teorema) di mana ia memperkenalkan substitusi ini. Ekspresinya terlihat seperti ini:
Tahap ketiga. Substitusi terakhir
Dalam aritmatika formal aritmatika, ekspresi ini direpresentasikan dalam bentuk numerik. Misalkan E adalah bilangan Godelnya. Karena ekspresi berisi variabel bebas, kami memiliki hak untuk melakukan substitusi - menggantikan angka E dan menunjukkan - mengganti E:
Kami menyatakan ekspresi kedua ini dengan a dan nomor Gödelnya dengan E. Mari kita berikan interpretasi ekspresi e.
Interpretasi pertama. Tidak ada pasangan seperti itu yang berikut ini akan secara bersamaan berlaku: di satu sisi, T adalah jumlah bukti aritmatika dari teorema aritmatika dengan sendirinya, dan di sisi lain, akan ada pengganti Tapi karena ada transformasi yang sama seperti yang lain, itu diwakili dalam hal dan dalam notasi kode mereka - nomor Gödel dan, oleh karena itu, nomor seperti itu ada. Maka mungkin angka T tidak ada.
Interpretasi kedua. Tidak ada bukti aritmatika T dari teorema yang merupakan substitusi - dari E. Jadi, jika tidak ada bukti, itu karena teorema itu sendiri bukan teorema. Ini mengarah pada interpretasi ketiga.
Interpretasi ketiga. Ekspresi di mana bilangan Gödel adalah substitusi - dari E bukanlah teorema dalam aritmatika formal yang diaritmatika. Tetapi di sinilah letak kontradiksinya, karena dengan konstruksi itu sendiri merupakan -substitusi dari E, dan bilangan itu dengan konstruksi tidak lain dari bilangan E itu sendiri. Ini menyiratkan interpretasi terakhir dari e.
09senSetiap sistem aksioma matematika, mulai dari tingkat kerumitan tertentu, secara internal tidak konsisten atau tidak lengkap.
Pada tahun 1900, Konferensi Dunia Matematikawan diadakan di Paris, di mana David Gilbert(David Hilbert, 1862–1943) menguraikan dalam bentuk tesis 23 tugas paling penting, menurut pendapatnya, yang harus diselesaikan oleh para ahli teori abad kedua puluh yang akan datang. Nomor dua dalam daftarnya adalah salah satu masalah sederhana yang tampak jelas sampai Anda menggali lebih dalam. Dalam istilah modern, itu adalah pertanyaan: apakah matematika cukup dengan sendirinya? Tugas kedua Hilbert direduksi menjadi kebutuhan untuk membuktikan secara ketat bahwa sistem aksioma - pernyataan dasar yang diambil dalam matematika sebagai dasar tanpa bukti - adalah sempurna dan lengkap, yaitu memungkinkan deskripsi matematis dari segala sesuatu yang ada. Itu perlu untuk membuktikan bahwa adalah mungkin untuk mengatur sistem aksioma sedemikian rupa sehingga, pertama, mereka akan saling konsisten, dan kedua, seseorang dapat menarik kesimpulan dari mereka mengenai kebenaran atau kesalahan pernyataan apa pun.
Mari kita ambil contoh dari geometri sekolah. Dalam planimetri Euclidean standar (geometri pada bidang datar), dapat dibuktikan tanpa syarat bahwa pernyataan "jumlah sudut suatu segitiga adalah 180°" adalah benar, dan pernyataan "jumlah sudut suatu segitiga adalah 137° " itu palsu. Berbicara pada dasarnya, dalam geometri Euclidean, pernyataan apa pun salah atau benar, dan yang ketiga tidak diberikan. Dan pada awal abad kedua puluh, matematikawan secara naif percaya bahwa situasi yang sama harus diamati dalam sistem yang konsisten secara logis.
Dan kemudian pada tahun 1931 beberapa matematikawan berkacamata Wina Kurt Godel- mengambil dan menerbitkan artikel pendek yang hanya menjungkirbalikkan seluruh dunia yang disebut "logika matematika". Setelah pembukaan matematika dan teoretis yang panjang dan kompleks, ia benar-benar menetapkan yang berikut ini. Mari kita ambil pernyataan seperti: "Asumsi #247 secara logis tidak dapat dibuktikan dalam sistem aksioma ini" dan menyebutnya "pernyataan A". Jadi, Gödel hanya membuktikan properti menakjubkan berikut dari setiap sistem aksioma:
“Jika pernyataan A dapat dibuktikan, maka pernyataan non-A dapat dibuktikan.”
Dengan kata lain, jika mungkin untuk membuktikan keabsahan pernyataan “Asumsi 247 tidak dapat dibuktikan”, maka dimungkinkan juga untuk membuktikan keabsahan pernyataan “Asumsi 247 dapat dibuktikan”. Artinya, kembali ke rumusan masalah Hilbert kedua, jika sistem aksiomanya lengkap (yaitu, pernyataan apa pun di dalamnya dapat dibuktikan), maka itu tidak konsisten.
Satu-satunya jalan keluar dari situasi ini adalah menerima sistem aksioma yang tidak lengkap. Artinya, kita harus menerima fakta bahwa dalam konteks sistem logis apa pun kita masih akan memiliki pernyataan "tipe A" yang jelas-jelas benar atau salah - dan kita dapat menilai kebenarannya hanya di luar kerangka aksioma yang kita miliki diadopsi. Jika tidak ada pernyataan seperti itu, maka aksioma kita kontradiktif, dan dalam kerangkanya pasti akan ada formulasi yang dapat dibuktikan dan disangkal.
Jadi rumusan teorema ketidaklengkapan pertama, atau lemah, Gödel adalah: "Setiap sistem aksioma formal mengandung asumsi yang belum terselesaikan". Tetapi Gödel tidak berhenti di situ, merumuskan dan membuktikan teorema ketidaklengkapan kedua atau kuat Gödel: “Kelengkapan logis (atau ketidaklengkapan) dari sistem aksioma apa pun tidak dapat dibuktikan dalam kerangka sistem ini. Untuk membuktikan atau menyangkalnya, diperlukan aksioma tambahan (penguatan sistem).
Akan lebih aman untuk berpikir bahwa teorema Godel bersifat abstrak dan tidak menjadi perhatian kita, tetapi hanya bidang logika matematika yang luhur, tetapi pada kenyataannya ternyata berhubungan langsung dengan struktur otak manusia. Matematikawan dan fisikawan Inggris Roger Penrose (lahir 1931) menunjukkan bahwa Teorema Godel dapat digunakan untuk membuktikan adanya perbedaan mendasar antara otak manusia dan komputer. Inti dari penalarannya sederhana. Komputer beroperasi secara logis dan tidak dapat menentukan apakah pernyataan A benar atau salah jika melampaui cakupan aksiomatik, dan pernyataan seperti itu, menurut teorema Gödel, pasti ada. Seseorang, dihadapkan dengan pernyataan A yang tidak dapat dibuktikan secara logis dan tidak dapat disangkal, selalu dapat menentukan kebenaran atau kepalsuannya - berdasarkan pengalaman sehari-hari. Setidaknya dalam hal ini, otak manusia lebih unggul daripada komputer yang dibelenggu oleh rangkaian logika murni. Otak manusia mampu memahami kedalaman penuh kebenaran yang terkandung dalam teorema Gödel, tetapi komputer tidak akan pernah bisa. Oleh karena itu, otak manusia tidak lain adalah komputer. Dia mampu membuat keputusan, dan tes Turing akan berlalu.
Setiap sistem aksioma matematika, mulai dari tingkat kerumitan tertentu, secara internal tidak konsisten atau tidak lengkap.
Pada tahun 1900, Konferensi Dunia Matematikawan diadakan di Paris, di mana David Hilbert (1862-1943) mempresentasikan dalam bentuk abstrak 23 masalah terpenting, menurutnya, yang dirumuskan olehnya, yang harus dipecahkan oleh para ilmuwan teoretis. dari abad kedua puluh yang akan datang. Nomor dua dalam daftarnya adalah salah satu masalah sederhana yang tampak jelas sampai Anda menggali lebih dalam. Dalam istilah modern, itu adalah pertanyaan: apakah matematika cukup dengan sendirinya? Masalah kedua Hilbert adalah untuk membuktikan secara ketat bahwa sistem aksioma- pernyataan dasar yang diambil dalam matematika sebagai dasar tanpa bukti - sempurna dan lengkap, yaitu, memungkinkan Anda untuk menggambarkan segala sesuatu yang ada secara matematis. Itu perlu untuk membuktikan bahwa adalah mungkin untuk mengatur sistem aksioma sedemikian rupa sehingga, pertama, mereka akan saling konsisten, dan kedua, seseorang dapat menarik kesimpulan dari mereka mengenai kebenaran atau kesalahan pernyataan apa pun.
Mari kita ambil contoh dari geometri sekolah. Standar Planimetri Euclidean(geometri pada bidang datar) adalah mungkin untuk membuktikan tanpa syarat bahwa pernyataan "jumlah sudut suatu segitiga adalah 180°" adalah benar, dan pernyataan "jumlah sudut suatu segitiga adalah 137°" adalah salah. Berbicara pada dasarnya, dalam geometri Euclidean, pernyataan apa pun salah atau benar, dan yang ketiga tidak diberikan. Dan pada awal abad kedua puluh, matematikawan secara naif percaya bahwa situasi yang sama harus diamati dalam sistem yang konsisten secara logis.
Dan kemudian pada tahun 1931, beberapa matematikawan berkacamata Wina Kurt Godel mengambil dan menerbitkan sebuah artikel pendek yang hanya menjungkirbalikkan seluruh dunia yang disebut "logika matematika". Setelah pembukaan matematika dan teoretis yang panjang dan kompleks, ia benar-benar menetapkan yang berikut ini. Mari kita ambil pernyataan seperti: "Asumsi #247 secara logis tidak dapat dibuktikan dalam sistem aksioma ini" dan menyebutnya "pernyataan A". Jadi Gödel hanya membuktikan properti luar biasa berikut setiap sistem aksioma:
“Jika pernyataan A dapat dibuktikan, maka pernyataan non-A dapat dibuktikan.”
Dengan kata lain, jika mungkin untuk membuktikan validitas pernyataan "Asumsi 247" bukan dibuktikan", maka dimungkinkan untuk membuktikan validitas pernyataan "Asumsi 247 terbukti". Artinya, kembali ke rumusan masalah Hilbert kedua, jika sistem aksiomanya lengkap (yaitu, pernyataan apa pun di dalamnya dapat dibuktikan), maka itu tidak konsisten.
Satu-satunya jalan keluar dari situasi ini adalah menerima sistem aksioma yang tidak lengkap. Artinya, kita harus menerima fakta bahwa dalam konteks sistem logis apa pun kita akan dibiarkan dengan pernyataan "tipe A" yang jelas benar atau salah - dan kita hanya dapat menilai kebenarannya. di luar kerangka aksiomatik yang telah kita adopsi. Jika tidak ada pernyataan seperti itu, maka aksioma kita kontradiktif, dan dalam kerangkanya pasti akan ada formulasi yang dapat dibuktikan dan disangkal.
Jadi kata-katanya pertama,atau lemah Teorema ketidaklengkapan Gödel: "Setiap sistem aksioma formal mengandung asumsi yang belum terselesaikan." Tapi Gödel tidak berhenti di situ, merumuskan dan membuktikan kedua, atau kuat Teorema ketidaklengkapan Godel: “Kelengkapan logis (atau ketidaklengkapan) dari setiap sistem aksioma tidak dapat dibuktikan dalam kerangka sistem ini. Untuk membuktikan atau menyangkalnya, diperlukan aksioma tambahan (penguatan sistem).”
Akan lebih aman untuk berpikir bahwa teorema Godel bersifat abstrak dan tidak menjadi perhatian kita, tetapi hanya bidang logika matematika yang luhur, tetapi pada kenyataannya ternyata berhubungan langsung dengan struktur otak manusia. Matematikawan dan fisikawan Inggris Roger Penrose (lahir 1931) menunjukkan bahwa teorema Gödel dapat digunakan untuk membuktikan perbedaan mendasar antara otak manusia dan komputer. Inti dari penalarannya sederhana. Komputer beroperasi secara logis dan tidak dapat menentukan apakah pernyataan A benar atau salah jika melampaui cakupan aksiomatik, dan pernyataan seperti itu, menurut teorema Gödel, pasti ada. Seseorang, dihadapkan dengan pernyataan A yang tidak dapat dibuktikan secara logis dan tidak dapat disangkal, selalu dapat menentukan kebenaran atau kepalsuannya - berdasarkan pengalaman sehari-hari. Setidaknya dalam hal ini, otak manusia lebih unggul daripada komputer yang dibelenggu oleh rangkaian logika murni. Otak manusia mampu memahami kedalaman penuh kebenaran yang terkandung dalam teorema Gödel, tetapi komputer tidak akan pernah bisa. Oleh karena itu, otak manusia tidak lain adalah komputer. Dia mampu untuk membuat keputusan, dan tes Turing akan lulus.
Saya ingin tahu apakah Hilbert tahu seberapa jauh pertanyaannya akan membawa kita?
Kurt Godel, 1906-78
Austria, kemudian matematikawan Amerika. Lahir di Brünn (Brünn, sekarang Brno, Republik Ceko). Dia lulus dari Universitas Wina, di mana dia tetap menjadi guru di Departemen Matematika (sejak 1930 - seorang profesor). Pada tahun 1931 ia menerbitkan sebuah teorema yang kemudian menerima namanya. Menjadi orang yang murni apolitis, ia sangat sulit bertahan dari pembunuhan teman dan karyawan departemennya oleh seorang mahasiswa Nazi dan jatuh ke dalam depresi berat, yang kambuh menghantuinya sampai akhir hayatnya. Pada 1930-an, ia beremigrasi ke Amerika Serikat, tetapi kembali ke negara asalnya Austria dan menikah. Pada tahun 1940, pada puncak perang, ia terpaksa melarikan diri ke Amerika dalam perjalanan melalui Uni Soviet dan Jepang. Untuk beberapa waktu dia bekerja di Princeton Institute for Advanced Study. Sayangnya, jiwa ilmuwan tidak tahan, dan dia meninggal karena kelaparan di klinik psikiatri, menolak untuk makan, karena dia yakin bahwa mereka bermaksud meracuninya.
Uspensky V.A.
Teorema ketidaklengkapan Gödel. 1994.
Ilmu Komputer Teoritis 130,1994, pp.273-238.
Mungkin teorema ketidaklengkapan Gödel benar-benar unik. Unik karena mereka menyebutnya ketika mereka ingin membuktikan "segala sesuatu di dunia" - dari kehadiran para dewa hingga ketiadaan akal. Saya selalu tertarik pada "pertanyaan utama" - dan siapa di antara mereka yang mengacu pada teorema ketidaklengkapan yang tidak hanya dapat merumuskannya, tetapi juga membuktikannya? Saya menerbitkan artikel ini karena menyajikan rumusan teorema Gödel yang sangat mudah diakses. Saya sarankan Anda membaca artikel Tullio Regge Kurt Gödel terlebih dahulu dan teoremanya yang terkenal
Kesimpulan tentang ketidakmungkinan kriteria kebenaran universal adalah
konsekuensi langsung dari hasil yang diperoleh Tarski dengan menggabungkan
Teorema ketidakpastian Gödel dengan teori kebenarannya sendiri, menurut
yang tidak dapat menjadi kriteria universal kebenaran bahkan untuk relatif
area sempit teori bilangan, dan karenanya untuk ilmu apa pun yang menggunakan
hitung. Secara alami, hasil ini menerapkan fortiori pada konsep kebenaran
dalam bidang pengetahuan non-matematis apa pun yang luasnya
aritmatika digunakan.
Karl Popper
Uspensky Vladimir Andreevich lahir pada 27 November 1930 di Moskow. Lulus dari Fakultas Mekanika dan Matematika Universitas Negeri Moskow (1952). Doktor Ilmu Fisika dan Matematika (1964). Guru Besar, Kepala Departemen Logika Matematika dan Teori Algoritma Fakultas Mekanika dan Matematika (1966). Membaca mata kuliah "Pengantar Logika Matematika", "Fungsi yang Dapat Dihitung", "Teorema Kelengkapan Gödel". Menyiapkan 25 calon dan 2 doktor ilmu
1. Pernyataan masalah
Teorema ketidaklengkapan, rumusan yang tepat yang akan kami berikan di akhir bab ini, dan mungkin nanti (jika pembaca tertarik pada ini) dan buktinya, menyatakan kira-kira sebagai berikut: dalam kondisi tertentu dalam bahasa apa pun ada yang benar, tetapi pernyataan yang tidak dapat dibuktikan.
Ketika kita merumuskan teorema dengan cara ini, hampir setiap kata membutuhkan penjelasan. Oleh karena itu, kami akan mulai dengan menjelaskan arti dari kata-kata yang kami gunakan dalam formulasi ini.
Kami tidak akan memberikan definisi bahasa yang paling umum, lebih memilih untuk membatasi diri pada konsep-konsep bahasa yang akan kami butuhkan nanti. Ada dua konsep seperti itu: "abjad bahasa" dan "kumpulan pernyataan bahasa yang benar".
1.1.1. Alfabet
Yang kami maksud dengan alfabet adalah sekumpulan tanda dasar yang terbatas (yaitu, hal-hal yang tidak dapat dipecah menjadi bagian-bagian komponen). Karakter ini disebut huruf alfabet. Dengan kata alfabet yang kami maksud adalah urutan huruf yang terbatas. Misalnya, kata-kata biasa dalam bahasa Inggris (termasuk nama diri) adalah kata-kata dengan 54 huruf alfabet (26 huruf kecil, 26 huruf besar, tanda hubung, dan tanda kutip). Contoh lain - bilangan asli dalam notasi desimal adalah kata-kata dari alfabet 10 huruf, yang hurufnya adalah tanda: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Kami akan menggunakan huruf kapital biasa untuk menunjukkan alfabet. Jika L adalah alfabet, maka L? akan menunjukkan himpunan semua kata dari alfabet L, - kata-kata yang dibentuk dari huruf-hurufnya. Kami akan berasumsi bahwa setiap bahasa memiliki alfabetnya sendiri, sehingga semua ekspresi bahasa ini (yaitu - nama berbagai objek, pernyataan tentang objek ini, dll.) adalah kata-kata dari alfabet ini. Misalnya, kalimat apa pun dalam bahasa Inggris, serta teks apa pun yang ditulis dalam bahasa Inggris, dapat dianggap sebagai kata dari alfabet 54 huruf yang diperluas, yang juga mencakup tanda baca, spasi antarkata, karakter garis merah, dan mungkin beberapa karakter berguna lainnya. Dengan asumsi bahwa ekspresi bahasa adalah kata-kata dari beberapa alfabet, dengan demikian kami mengecualikan dari pertimbangan ekspresi "multilayer" seperti ???f(x)dx. Namun, batasan ini tidak terlalu signifikan, karena ekspresi seperti itu, menggunakan konvensi yang sesuai, dapat "diregangkan" ke dalam bentuk linier. Setiap himpunan M terkandung dalam L? disebut himpunan kata dari abjad L. Jika kita hanya mengatakan bahwa M adalah himpunan kata, maka yang kita maksud adalah kata dari beberapa abjad. Sekarang asumsi bahasa di atas dapat direfrase sebagai berikut: dalam bahasa apapun, himpunan ekspresi apapun adalah himpunan kata.
1.1.2. Banyak klaim yang benar
Kita asumsikan bahwa kita diberi subset T dari himpunan L? (di mana L adalah alfabet dari beberapa bahasa yang kita pertimbangkan), yang disebut himpunan "pernyataan benar" (atau hanya "kebenaran"). Melewati langsung ke subset T, kami menghilangkan langkah-langkah penalaran menengah berikut: pertama, kata-kata alfabet L mana yang merupakan ekspresi bahasa yang terbentuk dengan baik, yaitu, mereka memiliki makna tertentu dalam interpretasi kami tentang bahasa ini (misalnya , 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 adalah ekspresi yang terbentuk dengan baik, sedangkan ekspresi seperti +=x tidak); kedua, ekspresi mana yang merupakan formula, mis. mungkin bergantung pada parameter (misalnya, x=3, x=y, 2=3, 2=2); ketiga, rumus mana yang merupakan rumus tertutup, mis. pernyataan yang tidak bergantung pada parameter (misalnya, 2=3, 2=2); dan terakhir, rumus tertutup mana yang merupakan pernyataan benar (misalnya, 2=2).
1.1.3. Pasangan bahasa dasar
1.2. "Tidak dapat dibuktikan"
"Tidak dapat dibuktikan" berarti tidak memiliki bukti.
1.3. Bukti
Terlepas dari kenyataan bahwa istilah "bukti" mungkin salah satu yang paling penting dalam matematika (Bourbaki memulai buku mereka "Fundamentals of Mathematics" dengan kata-kata: "Dari zaman Yunani kuno, mengatakan "matematika" berarti sama dengan mengatakan "bukti""), dia tidak memiliki definisi yang tepat. Secara umum, konsep pembuktian dengan semua cabang semantiknya lebih merupakan milik bidang psikologi daripada matematika. Tapi bagaimanapun, bukti hanyalah sebuah argumen yang kita sendiri temukan cukup meyakinkan untuk meyakinkan orang lain.
Ketika ditulis, buktinya menjadi sebuah kata dalam beberapa abjad P, sama seperti teks bahasa Inggris lainnya adalah kata dalam abjad L, contohnya diberikan di atas. Himpunan semua bukti membentuk himpunan bagian (dan himpunan bagian yang cukup besar) dari himpunan P?. Kami tidak akan mencoba memberikan definisi yang tepat dari konsep pembuktian "naif" dan "mutlak" ini, atau - yang setara - untuk mendefinisikan subset yang sesuai dari P?. Sebagai gantinya, kami akan mempertimbangkan analog formal dari konsep yang tidak jelas ini, di mana kami masih akan menggunakan istilah "bukti" berikut ini. Analog ini memiliki dua fitur yang sangat penting yang membedakannya dari konsep intuitif (walaupun ide intuitif bukti masih mencerminkan fitur ini sampai batas tertentu). Pertama-tama, kita berasumsi bahwa ada konsepsi yang berbeda dari pembuktian, yaitu, subset yang berbeda dari pembuktian di P? diperbolehkan, dan bahkan lebih dari itu: kita akan, pada kenyataannya, berasumsi bahwa alfabet pembuktian dari P itu sendiri dapat berubah. . Berikut ini, kita akan mensyaratkan bahwa untuk setiap konsepsi dari suatu bukti, terdapat metode yang efisien, dengan kata lain, suatu algoritma yang akan menentukan apakah kata tertentu dari alfabet P adalah suatu bukti atau tidak. Kami juga berasumsi bahwa ada algoritma yang selalu dapat digunakan untuk menentukan pernyataan mana yang dibuktikan oleh bukti tertentu. (Dalam banyak situasi, pernyataan yang dibuktikan hanyalah pernyataan terakhir dalam urutan langkah-langkah yang membentuk pembuktian.)
Dengan demikian, kata-kata terakhir kami dari definisi adalah sebagai berikut:
(1) Kami memiliki alfabet L (abjad bahasa) dan alfabet P (abjad pembuktian).
(2) Kita diberikan himpunan P yang merupakan himpunan bagian dari P? dan elemen-elemennya disebut "bukti". Berikut ini, kita akan mengasumsikan bahwa kita juga memiliki algoritme yang memungkinkan kita untuk menentukan apakah kata arbitrer dari alfabet P adalah elemen dari himpunan P, yaitu, bukti, atau bukan.
(3) Kami juga memiliki fungsi? (untuk menemukan apa yang sebenarnya telah terbukti), domain siapa? memenuhi kondisi P???P?, dan yang jangkauannya ada di P?. Kami berasumsi bahwa kami memiliki algoritme yang menghitung fungsi ini (arti sebenarnya dari kata-kata "algoritma menghitung fungsi" adalah sebagai berikut: nilai fungsi diperoleh dengan menggunakan algoritme ini - seperangkat aturan transformasi khusus). Kami akan mengatakan bahwa elemen p? P adalah bukti kata?(p) dari alfabet L.
Suatu rangkap tiga yang memenuhi syarat (1)-(3) disebut sistem deduktif atas alfabet L.
Bagi pembaca yang akrab dengan cara biasa mendefinisikan "bukti" dalam istilah "aksioma" dan "aturan inferensi", sekarang kami akan menjelaskan bagaimana metode ini dapat dianggap sebagai kasus khusus dari definisi yang diberikan di bagian 1.3.2. Artinya, bukti biasanya didefinisikan sebagai urutan ekspresi bahasa tersebut, yang masing-masing merupakan aksioma atau diperoleh sebelumnya dari pernyataan yang sudah ada dengan menggunakan salah satu aturan inferensi. Jika kita menambahkan kata baru * ke alfabet bahasa kita, maka kita dapat menulis bukti seperti kata yang disusun menggunakan alfabet yang dihasilkan: urutan ekspresi menjadi kata C1*C2*...*Cn. Dalam hal ini, fungsi yang menentukan apa yang sebenarnya telah dibuktikan memiliki nilainya di bagian kata ini segera setelah huruf terakhir * dalam urutan. Algoritme yang keberadaannya diperlukan dalam Bagian 1.3.2. definisi, dapat dengan mudah dibangun setelah kita secara tepat mendefinisikan salah satu arti yang diterima dari kata "aksioma" dan "aturan inferensi".
1.4 Upaya untuk secara akurat merumuskan teorema ketidaklengkapan
1.4.1. Percobaan pertama
"Dalam kondisi tertentu, untuk pasangan dasar bahasa alfabet L dan sistem deduktif di atas L, selalu ada kata dalam T yang tidak memiliki bukti." Opsi ini masih terlihat kabur. Secara khusus, kita dapat dengan mudah menemukan sejumlah sistem deduktif yang hanya memiliki sedikit kata yang dapat dibuktikan. Misalnya, dalam sistem deduktif kosong (di mana P = ?) tidak ada kata sama sekali yang memiliki bukti.
1.4.2. Percobaan kedua
Ada pendekatan lain yang lebih alami. Misalkan kita diberi bahasa - dalam arti bahwa kita diberikan pasangan dasar bahasa ini. Sekarang kita akan mencari sistem deduktif atas L (secara intuitif, kita mencari teknik pembuktian) yang dengannya kita dapat membuktikan sebanyak mungkin kata dari T, dalam batas semua kata dari teorema T. Gödel menggambarkan situasi di mana sistem deduktif seperti itu (di mana setiap kata dalam T dapat dibuktikan) tidak ada. Oleh karena itu, kami ingin merumuskan pernyataan berikut:
"Dalam kondisi tertentu mengenai pasangan fundamental, tidak ada sistem deduktif di mana setiap kata dari T akan memiliki bukti."
Namun, pernyataan seperti itu jelas salah, karena hanya perlu mengambil sistem deduktif di mana P = L, P = P? dan?(p) = p untuk semua p di P?; lalu setiap kata dari L? sepele dapat dibuktikan. Oleh karena itu, kita perlu menerima beberapa batasan pada sistem deduktif yang kita gunakan.
1.5. Konsistensi
Akan sangat wajar untuk mensyaratkan bahwa hanya "pernyataan yang benar", yaitu, hanya kata-kata dari T, yang dapat dibuktikan. Kita akan mengatakan bahwa sistem deduktif konsisten terhadap pasangan fundamental jika?(P)?T. Dalam semua penalaran berikutnya, kita hanya akan tertarik pada sistem deduktif yang konsisten seperti itu. Jika kita diberi bahasa, maka akan sangat menggoda untuk menemukan sistem deduktif yang konsisten di mana setiap pernyataan yang benar akan memiliki bukti. Varian teorema Gödel yang menarik bagi kita dengan tepat menyatakan bahwa dalam kondisi tertentu sehubungan dengan pasangan fundamental, tidak mungkin menemukan sistem deduktif seperti itu.
1.6. kelengkapan
Dikatakan bahwa sistem deduktif lengkap terhadap pasangan fundamental, asalkan ?(P)?T. Kemudian rumusan teorema ketidaklengkapan kita mengambil bentuk berikut:
Dalam kondisi tertentu sehubungan dengan pasangan fundamental, tidak ada sistem deduktif atas L yang akan lengkap dan relatif konsisten.
