rumah » Otomatis/Moto » Inti dari teorema Gödel. Pengakuan Seorang Ahli Logika Hebat

Inti dari teorema Gödel. Pengakuan Seorang Ahli Logika Hebat

Saya sudah lama tertarik dengan apa itu teorema Gödel yang sensasional. Dan bagaimana manfaatnya bagi kehidupan. Dan akhirnya saya bisa mengetahuinya.

Rumusan teorema yang paling populer adalah sebagai berikut:
“Setiap sistem aksioma matematika, mulai dari tingkat kompleksitas tertentu, bertentangan secara internal atau tidak lengkap.”

Saya akan menerjemahkannya ke dalam bahasa non-matematis manusia sebagai berikut (aksioma adalah posisi awal suatu teori, diterima sebagai kebenaran dalam kerangka teori ini tanpa memerlukan pembuktian dan digunakan sebagai dasar pembuktian ketentuan lainnya) . Dalam kehidupan, aksioma adalah prinsip-prinsip yang dianut oleh seseorang, masyarakat, arah ilmiah, dan negara. Perwakilan agama menyebut aksioma sebagai dogma. Akibatnya, prinsip-prinsip kita, sistem pandangan apa pun, mulai dari tingkat tertentu, menjadi kontradiktif atau tidak lengkap secara internal. Untuk yakin akan kebenaran pernyataan tertentu, Anda harus melampaui sistem kepercayaan ini dan membangun sistem kepercayaan baru. Tapi itu juga tidak sempurna. Artinya, PROSES KOGNISI TIDAK TERBATAS. Dunia tidak dapat dipahami sepenuhnya sampai kita mencapai sumber aslinya.

“...jika kita menganggap kemampuan bernalar secara logis sebagai ciri utama pikiran manusia, atau setidaknya alat utamanya, maka teorema Gödel secara langsung menunjukkan terbatasnya kemampuan otak kita. Setuju bahwa itu sangat sulit bagi seseorang. dibesarkan untuk percaya pada kekuatan pemikiran yang tak terbatas tesis tentang batas kekuatannya... Banyak ahli percaya bahwa komputasi formal, proses “Aristotelian” yang mendasari berpikir logis, hanya merupakan bagian dari kesadaran manusia. Area lainnya, yang pada dasarnya “non-komputasi”, bertanggung jawab atas manifestasi seperti intuisi, wawasan kreatif, dan pemahaman. Dan jika bagian pertama dari pikiran berada di bawah batasan Gödelian, maka bagian kedua bebas dari kerangka tersebut... Fisikawan Roger Penrose melangkah lebih jauh. Dia menyarankan adanya beberapa efek kuantum yang bersifat non-komputasi yang memastikan implementasi tindakan kesadaran kreatif... Salah satu dari banyak konsekuensi hipotesis Penrose mungkin, khususnya, kesimpulan tentang ketidakmungkinan mendasar menciptakan buatan kecerdasan berdasarkan perangkat komputasi modern, bahkan jika kemunculan komputer kuantum akan membawa terobosan besar di bidang ini teknologi komputer. Faktanya adalah bahwa komputer mana pun hanya dapat memodelkan secara lebih rinci kerja aktivitas kesadaran manusia yang “komputasi” secara formal-logis, tetapi kemampuan intelek “non-komputasi” tidak dapat diakses olehnya.

Salah satu konsekuensi penting dari teorema Gödel adalah kesimpulan bahwa seseorang tidak boleh berpikir ekstrem. Dalam kerangka teori yang ada, akan selalu ada pernyataan yang tidak dapat dibuktikan atau disangkal. Atau dengan kata lain, untuk suatu pernyataan akan selalu ada pasangan yang membantahnya.

Kesimpulan selanjutnya. Kebaikan dan kejahatan hanyalah 2 sisi dari mata uang yang sama, tanpanya keduanya tidak akan ada. Dan hal ini didasarkan pada prinsip bahwa di alam semesta hanya ada satu sumber segala sesuatu: baik dan jahat, cinta dan benci, hidup dan mati.

Setiap pernyataan kelengkapan sistem adalah salah. Anda tidak bisa mengandalkan dogma, karena cepat atau lambat dogma itu akan terbantahkan.

Dalam arti ini, agama modern berada dalam situasi kritis: dogma-dogma gereja menentang perkembangan gagasan kita tentang dunia. Mereka mencoba memasukkan segala sesuatu ke dalam kerangka konsep yang kaku. Tapi ini mengarah pada fakta bahwa dari Monoteisme, dari satu-satunya sumber dari semua proses alam, mereka beralih ke paganisme, di mana ada kekuatan baik dan kekuatan jahat, ada dewa kebaikan di suatu tempat jauh di surga, dan ada iblis (dewa kejahatan), yang telah lama menguasai segala sesuatu yang ada di Bumi. Pendekatan ini mengarah pada perpecahan semua orang menjadi teman dan musuh, menjadi orang benar dan berdosa, menjadi orang beriman dan sesat, menjadi teman dan musuh.

Berikut adalah teks singkat lainnya yang secara populer mengungkapkan esensi dari teorema Gödel:
“Bagi saya, teorema ini mempunyai arti penting makna filosofis. Hanya ada dua pilihan:

a) Teorinya tidak lengkap, yaitu. dari segi teori, dimungkinkan untuk merumuskan suatu pertanyaan yang tidak dapat disimpulkan jawaban positif maupun negatif dari aksioma/postulat teori tersebut. Selain itu, jawaban atas semua pertanyaan tersebut dapat diberikan dalam kerangka teori yang lebih komprehensif, di mana teori lama akan menjadi kasus khusus. Namun teori baru ini akan memiliki “pertanyaan yang belum terjawab” dan seterusnya tanpa batas.

b) Lengkap, tetapi kontradiktif. Pertanyaan apa pun dapat dijawab, tetapi beberapa pertanyaan dapat dijawab secara positif dan negatif pada saat yang bersamaan.

Teori-teori ilmiah termasuk dalam tipe pertama. Mereka konsisten, tapi itu berarti mereka tidak mencakup semuanya. Tidak mungkin ada "final" teori ilmiah. Teori apa pun tidak lengkap dan tidak menjelaskan sesuatu, meskipun kita belum mengetahui apa sebenarnya. Seseorang hanya dapat menciptakan teori yang lebih komprehensif. Bagi saya pribadi, hal ini menjadi alasan untuk optimis, karena berarti kemajuan ilmu pengetahuan tidak akan pernah berhenti.

"Tuhan Yang Mahakuasa" termasuk dalam tipe kedua. Tuhan Yang Maha Kuasa adalah jawaban atas setiap pertanyaan. Dan ini secara otomatis berarti mengarah pada absurditas logis. Paradoks seperti “batu luar biasa” dapat ditemukan secara bertahap.

Secara umum pengetahuan ilmiah itu benar (konsisten), tetapi tidak menggambarkan segala sesuatu pada suatu waktu tertentu. Pada saat yang sama, tidak ada yang menghalangi kita untuk mendorong batas-batas yang diketahui hingga tak terhingga; semakin jauh, dan cepat atau lambat, segala hal yang tidak diketahui akan diketahui. Agama mengaku sebagai gambaran lengkap tentang dunia “saat ini”, namun pada saat yang sama secara otomatis tidak benar (absurd).”

Pada suatu waktu, ketika saya baru memulai kehidupan dewasa, saya sedang melakukan pemrograman. Dan ada prinsipnya: jika banyak koreksi yang dilakukan pada program, maka harus ditulis ulang lagi. Prinsip ini menurut saya sesuai dengan teorema Gödel. Jika suatu program menjadi lebih kompleks, maka program tersebut menjadi tidak konsisten. Dan itu tidak akan berfungsi dengan benar.

Contoh lain dari kehidupan. Kita hidup di era ketika para pejabat menyatakan bahwa prinsip utama kehidupan adalah hukum. Artinya, sistem hukum. Namun begitu undang-undang mulai menjadi lebih kompleks dan pembuatan peraturan mulai berkembang, undang-undang tersebut mulai saling bertentangan. Inilah yang kita lihat sekarang. Tidak mungkin tercipta sistem hukum yang mengatur seluruh aspek kehidupan. Dan di sisi lain, ini akan adil bagi semua orang. Karena keterbatasan pemahaman kita terhadap dunia akan selalu terungkap. Dan hukum manusia suatu saat akan mulai bertentangan dengan hukum alam semesta. Kami memahami banyak hal secara intuitif. Kita juga harus menilai tindakan orang lain secara intuitif. Cukuplah sebuah negara mempunyai konstitusi. Dan berdasarkan pasal-pasal konstitusi ini, mengatur hubungan-hubungan dalam masyarakat. Namun cepat atau lambat, konstitusi harus diubah.

Ujian Negara Bersatu adalah contoh lain dari kekeliruan gagasan kita tentang kemampuan manusia. Kami mencoba menguji kemampuan komputasi otak dalam sebuah ujian. Namun kemampuan intuitif tidak lagi dikembangkan di sekolah. Tapi manusia bukanlah biorobot. Mustahil menciptakan suatu sistem penilaian yang dapat mengidentifikasi segala kemungkinan yang melekat pada diri seseorang, dalam kesadarannya, dalam alam bawah sadarnya, dan dalam jiwanya.

Hampir 100 tahun yang lalu, Gödel membuat kemajuan luar biasa dalam memahami hukum alam semesta. Namun kami masih belum dapat memanfaatkan hal ini, mengingat teorema ini sebagai masalah matematika yang sangat terspesialisasi untuk sekelompok kecil orang yang berurusan dengan beberapa topik abstrak di lingkaran mereka. Bersama dengan teori kuantum dan dengan ajaran Kristus, teorema Gödel memberi kita kesempatan untuk keluar dari jeratan dogma-dogma palsu, untuk mengatasi krisis yang masih ada dalam pandangan dunia kita. Dan waktu yang tersisa semakin sedikit.

Teorema ketidaklengkapan Gödel

Uspensky V.A.

Mungkin teorema ketidaklengkapan Gödel benar-benar unik. Unik karena disebut ketika mereka ingin membuktikan “segala sesuatu di dunia” - mulai dari kehadiran dewa hingga ketiadaan kecerdasan. Saya selalu tertarik pada "pertanyaan utama" - manakah di antara mereka yang mengacu pada teorema ketidaklengkapan yang tidak hanya dapat merumuskannya, tetapi juga membuktikannya? saya menerbitkan artikel ini dengan alasan bahwa ia menetapkan rumusan teorema Gödel yang dapat diakses sepenuhnya. Saya menyarankan Anda membaca terlebih dahulu artikel Tullio Regge Kurt Gödel dan teoremanya yang terkenal

Kesimpulan tentang ketidakmungkinan kriteria kebenaran universal adalah konsekuensi langsung dari hasil yang diperoleh Tarski dengan menggabungkan teorema Gödel tentang ketidakpastian dengan teori kebenarannya sendiri, yang menurutnya tidak mungkin ada kriteria kebenaran universal bahkan untuk kriteria kebenaran yang relatif sempit. bidang teori bilangan, dan oleh karena itu untuk ilmu apa pun menggunakan aritmatika. Tentu saja, hasil ini berlaku secara fortiori terhadap konsep kebenaran dalam bidang pengetahuan non-matematika mana pun yang banyak menggunakan aritmatika.

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, Ketua Jurusan Logika Matematika dan Teori Algoritma Fakultas Mekanika dan Matematika (1966). Memberikan mata kuliah "Pengantar logika matematika", "Fungsi yang dapat dihitung", "Teorema Gödel tentang kelengkapan". Menyiapkan 25 calon dan 2 doktor ilmu

1. Pernyataan masalah

Teorema ketidaklengkapan, rumusan pastinya akan kami berikan di akhir bab ini, dan mungkin nanti (jika pembaca tertarik dengan hal ini) dan buktinya, kira-kira menyatakan sebagai berikut: kapan kondisi tertentu Dalam bahasa apa pun, ada pernyataan yang benar tetapi tidak dapat dibuktikan.

Ketika kita merumuskan teorema dengan cara ini, hampir setiap kata memerlukan penjelasan. Oleh karena itu kami akan mulai dengan menjelaskan arti kata-kata yang kami gunakan dalam rumusan ini.

1.1. Bahasa

Kami tidak akan memberikan definisi bahasa yang paling umum, kami lebih memilih untuk membatasi diri pada konsep-konsep bahasa yang akan kami perlukan nanti. Ada dua konsep seperti itu: “abjad suatu bahasa” dan “kumpulan pernyataan sebenarnya dari suatu bahasa”.

1.1.1. Alfabet

Yang kami maksud dengan alfabet adalah sekumpulan tanda-tanda dasar yang terbatas (yaitu, hal-hal yang tidak dapat dipecah menjadi bagian-bagian komponennya). Tanda-tanda ini disebut huruf alfabet. Yang kami maksud dengan kata alfabet adalah rangkaian huruf yang terbatas. Misalnya, kata-kata biasa dalam bahasa Inggris (termasuk nama diri) adalah kata-kata yang terdiri dari 54 huruf (26 huruf kecil, 26 huruf kapital, tanda hubung, dan tanda kutip). Contoh lain - bilangan bulat dalam notasi desimal adalah kata-kata alfabet 10 huruf, yang huruf-hurufnya merupakan tanda: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Untuk menunjuk huruf kita akan menggunakan huruf kapital biasa. Jika L adalah alfabet, lalu L? akan menunjukkan himpunan semua kata dalam alfabet L - kata yang dibentuk dari huruf-hurufnya. Kami berasumsi bahwa bahasa apa pun memiliki alfabetnya sendiri, sehingga semua ekspresi bahasa ini (yaitu nama berbagai objek, pernyataan mengenai objek ini, dll.) adalah kata-kata dari alfabet ini. Misalnya, tawaran apa pun dalam bahasa Inggris, serta teks apa pun yang ditulis dalam bahasa Inggris, dapat dianggap sebagai kata dari alfabet yang diperluas yang terdiri dari 54 huruf, yang juga mencakup tanda baca, spasi antar kata, tanda garis merah, dan, mungkin, beberapa tanda berguna lainnya. Dengan asumsi bahwa ekspresi bahasa tersebut adalah kata-kata dari alfabet tertentu, maka kami mengecualikan ekspresi “berlapis-lapis” seperti ???f(x)dx dari pertimbangan. Namun, batasan ini tidak terlalu signifikan, karena ekspresi apa pun, dengan menggunakan konvensi yang sesuai, dapat "diregangkan" ke dalam bentuk linier. Adakah himpunan M yang terdapat di L? disebut himpunan kata dari alfabet L. Jika kita sekadar mengatakan bahwa M adalah himpunan kata, maka yang kita maksudkan adalah kata dari alfabet tertentu. Sekarang asumsi tentang bahasa di atas dapat diutarakan ulang sebagai berikut: dalam bahasa apa pun, kumpulan ekspresi apa pun adalah kumpulan kata.

1.1.2. Banyak pernyataan yang benar

Kita berasumsi bahwa kita diberi subset T dari himpunan L? (di mana L adalah alfabet dari beberapa bahasa yang sedang kita pertimbangkan), yang disebut himpunan “pernyataan yang benar” (atau sekadar “kebenaran”). Pindah langsung ke subset T, kami menghilangkan langkah-langkah penalaran perantara berikut: pertama, kata-kata mana dari alfabet L yang merupakan ekspresi bahasa yang dibentuk dengan benar, yaitu, memiliki arti tertentu dalam interpretasi kami terhadap 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 rumus, mis. mungkin bergantung pada parameter (misalnya, x=3, x=y, 2=3, 2=2); ketiga, rumus mana yang merupakan rumus tertutup, yaitu. pernyataan yang tidak bergantung pada parameter (misalnya, 2=3, 2=2); dan terakhir, rumus tertutup mana yang merupakan pernyataan yang benar (misalnya, 2=2).

1.1.3. Pasangan bahasa yang mendasar

1.2. "Tidak dapat dibuktikan"

Yang dimaksud dengan “tidak dapat dibuktikan” adalah tidak adanya bukti.

1.3. Bukti

Meskipun istilah "pembuktian" mungkin salah satu yang paling penting dalam matematika (keluarga Bourbaki memulai buku mereka "Fundamentals of Mathematics" dengan kata-kata: "Sejak zaman Yunani kuno, mengatakan 'matematika' memiliki arti yang sama dengan katakan 'bukti'"), ia tidak memiliki definisi pastinya sendiri. Secara umum, konsep pembuktian dengan segala cabang semantiknya lebih termasuk dalam bidang psikologi daripada matematika. Namun, bukti hanyalah sebuah argumen yang menurut kita cukup meyakinkan untuk meyakinkan orang lain.

Setelah ditulis, buktinya menjadi sebuah kata dalam alfabet P, sama seperti teks bahasa Inggris lainnya adalah kata dalam alfabet L, contohnya diberikan di atas. Himpunan semua bukti membentuk himpunan bagian (dan himpunan bagian yang cukup luas) dari himpunan P?. Kami tidak akan mencoba untuk memberikan definisi yang tepat tentang konsep pembuktian yang “naif” dan “mutlak” ini secara bersamaan, atau - apa yang setara - untuk memberikan definisi dari subset P? yang bersesuaian. Sebaliknya, kami akan mempertimbangkan analogi formal dari konsep yang tidak jelas ini, yang di masa depan kami masih akan menggunakan istilah “bukti”. Analog ini memiliki dua ciri yang sangat penting yang membedakannya dari konsep intuitif (walaupun gagasan pembuktian intuitif masih mencerminkan ciri-ciri ini sampai batas tertentu). Pertama-tama, kita akui bahwa ada konsep pembuktian yang berbeda, yaitu, himpunan pembuktian yang berbeda di P? dapat diterima, dan bahkan lebih dari itu: kita sebenarnya akan mengakui bahwa alfabet pembuktian P itu sendiri dapat berubah. . Selanjutnya kita akan mensyaratkan bahwa untuk setiap konsep pembuktian tersebut ada metode yang efektif, dengan kata lain, suatu algoritma yang akan menentukan apakah kata yang diberikan bukti alfabet P atau tidak. Kami juga akan berasumsi bahwa ada algoritma yang selalu dapat menentukan pernyataan mana yang dibuktikan oleh bukti tertentu. (Dalam banyak situasi, pernyataan yang dibuktikan hanyalah pernyataan terakhir dalam rangkaian langkah pembuktian.)

Jadi, definisi akhir kami adalah sebagai berikut:

(1) Kita mempunyai alfabet L (alfabet bahasa) dan alfabet P (alfabet bukti).

(2) Diberikan himpunan P, yang merupakan himpunan bagian dari P?, dan unsur-unsurnya disebut “bukti”. Di masa depan, kita akan berasumsi bahwa kita juga memiliki algoritma yang memungkinkan kita untuk menentukan apakah kata sembarang dari alfabet P merupakan elemen dari himpunan P, yaitu bukti, atau bukan.

(3) Apakah kita juga mempunyai fungsi? (untuk mengetahui apa sebenarnya yang telah dibuktikan), ruang lingkupnya siapa? memenuhi kondisi P???P?, dan kisaran nilainya di P?. Kami berasumsi bahwa kami memiliki algoritma yang menghitung fungsi ini ( nilai yang tepat Kata-kata "suatu algoritma menghitung suatu fungsi" adalah sebagai berikut: nilai-nilai fungsi diperoleh dengan menggunakan algoritma ini - seperangkat aturan transformasi khusus). Kita akan mengatakan bahwa elemen p? P merupakan pembuktian kata?(p) dari alfabet L.

Tiga<Р, Р, ?>, kondisi yang memuaskan (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 acara khusus definisi yang diberikan dalam paragraf 1.3.2. Artinya, pembuktian biasanya didefinisikan sebagai rangkaian 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 dalam alfabet bahasa kita, maka kita dapat menulis bukti tersebut dalam bentuk kata yang disusun menggunakan modifikasi alfabet yang dihasilkan: rangkaian ekspresi menjadi kata C1*C2*...*Cn . Dalam hal ini, fungsi yang menentukan apa yang sebenarnya telah dibuktikan mempunyai arti pada bagian kata tersebut tepat setelah huruf terakhir * pada barisan tersebut. Algoritma yang keberadaannya diperlukan pada bagian 1.3.2. definisi, dapat dengan mudah dibangun setelah kita mendefinisikan secara tepat makna apa pun yang diterima dari kata "aksioma" dan "aturan inferensi".

1.4 Upaya merumuskan teorema ketidaklengkapan secara tepat

1.4.1. Percobaan pertama

“Dalam kondisi tertentu untuk pasangan dasar bahasa alfabet L dan sistem deduktif<Р, Р, ?>di atas L - selalu ada kata di T yang tidak memiliki bukti." Opsi ini masih tampak kabur. Secara khusus, kita dapat dengan mudah menemukan sejumlah sistem deduktif yang hanya memiliki sedikit kata yang dapat dibuktikan. Misalnya, dalam deduktif kosong sistem (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 suatu bahasa - dalam artian kita diberikan pasangan dasar bahasa tersebut. Sekarang kita akan mencari sistem deduktif atas L (secara intuitif, kita sedang 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 (yang dengannya 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 mempunyai bukti."

Namun pernyataan seperti itu jelas salah, karena yang perlu dilakukan hanyalah mengambil sistem deduktif dimana P = L, P = P? u?(p) = p untuk semua p dari P?; lalu setiap kata dari L? dapat dibuktikan secara sepele. Oleh karena itu, kita perlu menerima beberapa batasan pada sistem deduktif yang kita gunakan.

1.5. Konsistensi

Wajar jika kita menuntut bahwa hanya “pernyataan yang benar”, yaitu hanya kata-kata dari T yang dapat dibuktikan. Kami akan mengatakan bahwa sistem deduktif<Р, Р, ?>konsisten terhadap pasangan fundamental jika?(P)?T. Dalam semua diskusi berikutnya kita hanya akan tertarik pada sistem deduktif yang konsisten. Jika kita diberi suatu bahasa, maka akan sangat menggoda untuk menemukan sistem deduktif yang konsisten di mana setiap pernyataan yang benar akan mempunyai bukti. Versi teorema Gödel yang menarik perhatian kita menyatakan dengan tepat bahwa dalam kondisi tertentu mengenai pasangan fundamental, tidak mungkin menemukan sistem deduktif seperti itu.

1.6. Kelengkapan

Dikatakan sistem deduktif<Р,Р,?>lengkap sehubungan dengan pasangan fundamental, dengan ketentuan?(P)?T. Maka rumusan teorema ketidaklengkapan kita berbentuk sebagai berikut:

Dalam kondisi tertentu mengenai pasangan fundamental, tidak ada sistem deduktif seperti itu<Р,Р,?>atas L, yang akan lengkap dan relatif konsisten.

Bibliografi

Untuk mempersiapkan pekerjaan ini, bahan dari situs http://filosof.historic.ru digunakan

buktinya baru ditemukan tiga setengah abad setelah rumusan pertama (dan ini jauh dari kata dasar). Penting untuk membedakan antara kebenaran suatu pernyataan dan pembuktiannya. Tidak berarti bahwa tidak ada pernyataan yang benar namun tidak dapat dibuktikan (dan tidak sepenuhnya dapat diverifikasi).

Argumen intuitif kedua yang menentang TGN lebih halus. Katakanlah kita memiliki pernyataan yang tidak dapat dibuktikan (dalam kerangka deduktif ini). Apa yang menghalangi kita untuk menerimanya sebagai aksioma baru? Oleh karena itu, kami akan sedikit memperumit sistem pembuktian kami, namun hal ini tidak menakutkan. Argumen ini sepenuhnya benar jika terdapat sejumlah pernyataan yang tidak dapat dibuktikan. Dalam praktiknya, hal berikut dapat terjadi: setelah mendalilkan aksioma baru, Anda menemukan pernyataan baru yang tidak dapat dibuktikan. Jika Anda menerimanya sebagai aksioma lain, Anda akan menemukan aksioma ketiga. Dan seterusnya tanpa batas. Mereka mengatakan pengurangan itu akan tetap ada tidak lengkap. Kita juga dapat memaksa algoritma pembuktian untuk menyelesaikan dalam jumlah langkah yang terbatas dengan hasil tertentu untuk ucapan bahasa apa pun. Tetapi pada saat yang sama, dia akan mulai berbohong - mengarah pada kebenaran untuk pernyataan yang salah, atau berbohong - untuk orang yang setia. Dalam kasus seperti itu, mereka mengatakan pengurangan itu kontradiktif. Jadi, rumusan lain dari TGN berbunyi seperti ini: “Ada bahasa proposisional yang tidak mungkin dilakukan deduktif konsisten sepenuhnya” - itulah nama teorema tersebut.

Kadang-kadang disebut “teorema Gödel”, pernyataannya adalah bahwa teori apa pun mengandung masalah yang tidak dapat diselesaikan dalam kerangka teori itu sendiri dan memerlukan generalisasinya. Hal ini memang benar, meskipun rumusan ini cenderung mengaburkan permasalahan dibandingkan memperjelasnya.

Saya juga mencatat bahwa jika kita berbicara tentang fungsi-fungsi familiar yang memetakan sekumpulan bilangan real ke dalamnya, maka "non-komputabilitas" dari fungsi tersebut tidak akan mengejutkan siapa pun (jangan bingung antara "fungsi yang dapat dihitung" dan "bilangan yang dapat dihitung" ” - ini adalah hal yang berbeda). Setiap anak sekolah tahu bahwa, katakanlah, dalam kasus suatu fungsi, Anda harus sangat beruntung dengan argumennya agar proses penghitungan representasi desimal yang tepat dari nilai fungsi ini dapat diselesaikan dalam jumlah langkah yang terbatas. Namun kemungkinan besar Anda akan menghitungnya menggunakan deret tak hingga, dan penghitungan ini tidak akan pernah memberikan hasil pasti, meskipun bisa mendekati hasil yang Anda inginkan - hanya karena nilai sinus dari sebagian besar argumen tidak rasional. TGN hanya memberi tahu kita bahwa bahkan di antara fungsi yang argumennya berupa string dan nilainya nol atau satu, terdapat juga fungsi yang tidak dapat dihitung, meskipun strukturnya sangat berbeda.

Untuk keperluan lebih lanjut, kami akan menjelaskan “bahasa aritmatika formal”. Pertimbangkan kelas string teks dengan panjang terbatas, yang terdiri dari angka Arab, variabel (huruf alfabet Latin), dengan mengambil nilai-nilai alam, spasi, tanda operasi aritmatika, persamaan dan pertidaksamaan, bilangan (“ada”) dan (“untuk apa pun”) dan, mungkin, beberapa simbol lainnya (jumlah dan komposisi pastinya tidak penting bagi kami). Jelas bahwa tidak semua baris tersebut bermakna (misalnya, “ ” adalah omong kosong). Subset ekspresi bermakna dari kelas ini (yaitu, string yang benar atau salah dari sudut pandang aritmatika biasa) akan menjadi kumpulan pernyataan kita.

Contoh pernyataan aritmatika formal:

dll. Sekarang sebut saja “rumus dengan parameter bebas” (FSP) sebagai string yang menjadi pernyataan jika bilangan asli disubstitusikan ke dalamnya sebagai parameter ini. Contoh FSP (dengan parameter):

dll. Dengan kata lain, FSP setara dengan fungsi argumen natural dengan nilai Boolean.

Mari kita nyatakan himpunan semua FSP dengan huruf . Jelas bisa diurutkan (misalnya, pertama kita menulis rumus satu huruf yang diurutkan menurut abjad, lalu rumus dua huruf, dan seterusnya; tidak penting bagi kita alfabet mana yang akan diurutkan). Jadi, FSP apa pun sesuai dengan nomornya dalam daftar yang diurutkan, dan kami akan menyatakannya .

Sekarang mari kita beralih ke sketsa pembuktian TGN dengan rumusan sebagai berikut:

Untuk bahasa proposisional aritmatika formal tidak ada sistem deduktif konsisten yang lengkap.

Kita akan membuktikannya dengan kontradiksi.

Jadi, mari kita asumsikan bahwa sistem 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 substitusi nomornya sendiri pada FSP dalam daftar kita memberikan pernyataan yang salah.

Di sini kita sampai pada satu-satunya tempat di mana saya akan meminta pembaca untuk mempercayai kata-kata saya.

Jelas bahwa, berdasarkan asumsi yang dibuat di atas, FSP apa pun dapat dibandingkan dengan algoritma yang berisi bilangan asli pada masukan dan nilai Boolean pada keluaran. Kebalikannya kurang jelas:

Pembuktian lemma ini memerlukan, setidaknya, definisi konsep suatu algoritma yang formal, bukan intuitif. Namun, jika dipikir-pikir sedikit, hal itu cukup masuk akal. Faktanya, algoritma ditulis dalam bahasa algoritmik, di antaranya ada bahasa eksotik seperti, misalnya, Brainfuck, yang terdiri dari delapan kata berkarakter tunggal, yang bagaimanapun, algoritma apa pun dapat diimplementasikan. Akan aneh jika bahasa rumus aritmatika formal yang lebih kaya yang kami jelaskan ternyata lebih buruk - meskipun, tidak diragukan lagi, ini tidak terlalu cocok untuk pemrograman biasa.

Setelah melewati tempat licin ini, kami segera sampai di ujung.

Jadi, di atas kami menjelaskan algoritmanya. Menurut lemma yang saya minta Anda percayai, ada FSP yang setara. Ada nomor tertentu dalam daftar - katakanlah,. Mari kita bertanya pada diri sendiri, apa yang setara dengan? Biarkan ini menjadi KEBENARAN. Kemudian, menurut konstruksi algoritmanya (dan karena itu fungsinya ekuivalen dengannya), ini berarti hasil substitusi suatu bilangan ke dalam fungsi tersebut adalah FALSE. Kebalikannya diperiksa dengan cara yang sama: dari FALSE diikuti TRUE. Kita telah mencapai kontradiksi, artinya asumsi awal tidak tepat. Jadi, tidak ada sistem deduktif yang konsisten dan lengkap untuk aritmatika formal. Q.E.D.

Di sini pantas untuk mengingat Epimenides (lihat potret di judul), yang, seperti diketahui, menyatakan bahwa semua orang Kreta adalah pembohong, dan dia sendiri adalah orang Kreta. Dalam rumusan yang lebih ringkas, pernyataannya (disebut “paradoks pembohong”) dapat dinyatakan sebagai berikut: “Saya berbohong.” Pernyataan seperti inilah, yang dengan sendirinya menyatakan kepalsuan, yang kami gunakan sebagai bukti.

Sebagai kesimpulan, saya ingin mencatat bahwa TGN tidak mengklaim sesuatu yang mengejutkan. Pada akhirnya, semua orang sudah lama terbiasa dengan kenyataan bahwa tidak semua bilangan dapat direpresentasikan sebagai rasio dua bilangan bulat (ingat, pernyataan ini memiliki bukti yang sangat elegan yang berusia lebih dari dua ribu tahun?). Dan tidak semua bilangan merupakan akar polinomial dengan koefisien rasional. Dan sekarang ternyata tidak semua fungsi argumen natural dapat dihitung.

Sketsa pembuktian yang diberikan adalah untuk aritmatika formal, namun mudah untuk melihat bahwa TGN dapat diterapkan pada banyak bahasa proposisional lainnya. Tentu saja tidak semua bahasa seperti ini. Misalnya, mari kita definisikan suatu bahasa sebagai berikut:

"Ungkapan apa pun bahasa Cina adalah pernyataan yang benar jika dimuat dalam buku kutipan Kamerad Mao Zedong, dan salah jika tidak dimuat.”

Kemudian algoritma pembuktian yang lengkap dan konsisten (bisa disebut “deduktif dogmatis”) terlihat seperti ini:

“Bukalah buku kutipan Kamerad Mao Zedong sampai Anda menemukan pepatah yang Anda cari. Jika ditemukan maka benar, tetapi jika buku kutipannya habis dan pernyataannya tidak ditemukan maka salah.”

Apa yang menyelamatkan kita di sini adalah bahwa setiap buku kutipan jelas terbatas, sehingga proses “pembuktian” pasti akan berakhir. Dengan demikian, TGN tidak berlaku untuk bahasa pernyataan dogmatis. Tapi kami sedang membicarakannya bahasa yang kompleks, Kebenaran?

Untuk keperluan lebih lanjut, kami akan menjelaskan “bahasa aritmatika formal”. Pertimbangkan kelas string teks dengan panjang terbatas, yang terdiri dari angka Arab, variabel (huruf alfabet Latin) yang mengambil nilai alami, spasi, tanda aritmatika, persamaan dan pertidaksamaan, bilangan (“ada”) dan (“untuk apa pun”) dan , mungkin , beberapa simbol lain (jumlah dan komposisi pastinya tidak penting bagi kami). Jelas bahwa tidak semua baris tersebut bermakna (misalnya, “ ” adalah omong kosong). Subset ekspresi bermakna dari kelas ini (yaitu, string yang benar atau salah dari sudut pandang aritmatika biasa) akan menjadi kumpulan pernyataan kita.

Contoh pernyataan aritmatika formal:

dll. Dengan kata lain, FSP setara dengan fungsi argumen natural dengan nilai Boolean.

Sekarang mari kita beralih ke sketsa pembuktian TGN dengan rumusan sebagai berikut:

Untuk bahasa proposisional aritmatika formal tidak ada sistem deduktif konsisten yang lengkap.

Kita akan membuktikannya dengan kontradiksi.

Jadi, mari kita asumsikan bahwa sistem 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 substitusi nomornya sendiri pada FSP dalam daftar kita memberikan pernyataan yang salah.

Di sini kita sampai pada satu-satunya tempat di mana saya akan meminta pembaca untuk mempercayai kata-kata saya.

Jelas bahwa, berdasarkan asumsi yang dibuat di atas, FSP apa pun dapat dibandingkan dengan algoritma yang berisi bilangan asli pada masukan dan nilai Boolean pada keluaran. Kebalikannya kurang jelas:

Setelah melewati tempat licin ini, kami segera sampai di ujung.

“Ungkapan apa pun dalam bahasa Mandarin adalah pernyataan yang benar jika dimuat dalam buku kutipan Kamerad Mao Zedong, dan salah jika tidak dimuat.”

Kemudian algoritma pembuktian yang lengkap dan konsisten (bisa disebut “deduktif dogmatis”) terlihat seperti ini:

“Bukalah buku kutipan Kamerad Mao Zedong sampai Anda menemukan pepatah yang Anda cari. Jika ditemukan maka benar, tetapi jika buku kutipannya habis dan pernyataannya tidak ditemukan maka salah.”

Uspensky V.A.

Teorema ketidaklengkapan Gödel.1994.

Ilmu Komputer Teoritis 130, 1994, hlm.273-238.

Mungkin teorema ketidaklengkapan Gödel benar-benar unik. Unik karena disebut ketika mereka ingin membuktikan “segala sesuatu di dunia” - mulai dari kehadiran dewa hingga ketiadaan kecerdasan. Saya selalu tertarik pada "pertanyaan utama" - manakah di antara mereka yang mengacu pada teorema ketidaklengkapan yang tidak hanya dapat merumuskannya, tetapi juga membuktikannya? Saya menerbitkan artikel ini karena artikel ini menyajikan rumusan teorema Gödel yang dapat diakses sepenuhnya. Saya menyarankan Anda membaca terlebih dahulu artikel Tullio Regge Kurt Gödel dan teoremanya yang terkenal

Kesimpulan tentang ketidakmungkinan kriteria kebenaran universal adalah

akibat langsung dari hasil yang diperoleh Tarski dengan menggabungkan

Teorema ketidakpastian Gödel dengan teori kebenarannya sendiri, menurut

yang mana tidak ada kriteria kebenaran universal bahkan secara relatif

bidang teori bilangan yang sempit, dan oleh karena itu untuk ilmu apa pun yang menggunakannya

hitung. Tentu saja, hasil ini menerapkan fortiori pada konsep kebenaran

dalam bidang pengetahuan non-matematika apa pun yang mencakupnya secara luas

aritmatika digunakan.

Karl Popper

1. Pernyataan masalah

Teorema ketidaklengkapan, rumusan pastinya yang akan kami berikan di akhir bab ini, dan mungkin nanti (jika pembaca tertarik dengan hal ini) dan buktinya, kira-kira menyatakan 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 memerlukan penjelasan. Oleh karena itu kami akan mulai dengan menjelaskan arti kata-kata yang kami gunakan dalam rumusan ini.

1.1.1. Alfabet

Yang kami maksud dengan alfabet adalah sekumpulan tanda-tanda dasar yang terbatas (yaitu, hal-hal yang tidak dapat dipecah menjadi bagian-bagian komponennya). Tanda-tanda ini disebut huruf alfabet. Yang kami maksud dengan kata alfabet adalah rangkaian huruf yang terbatas. Misalnya, kata-kata biasa dalam bahasa Inggris (termasuk nama diri) adalah kata-kata yang terdiri dari 54 huruf (26 huruf kecil, 26 huruf kapital, tanda hubung, dan tanda kutip). Contoh lainnya adalah bilangan asli dalam notasi desimal adalah kata-kata yang terdiri dari 10 huruf, yang huruf-hurufnya merupakan tanda: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Untuk menyatakan huruf, kita akan menggunakan huruf kapital biasa. Jika L adalah alfabet, lalu L? akan menunjukkan himpunan semua kata dalam alfabet L - kata yang dibentuk dari huruf-hurufnya. Kami berasumsi bahwa bahasa apa pun memiliki alfabetnya sendiri, sehingga semua ekspresi bahasa ini (yaitu nama berbagai objek, pernyataan mengenai 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 dalam alfabet tambahan yang terdiri dari 54 huruf, yang juga mencakup tanda baca, spasi antar kata, tanda garis merah, dan mungkin beberapa karakter berguna lainnya. . Dengan asumsi bahwa ekspresi bahasa tersebut adalah kata-kata dari alfabet tertentu, maka kami mengecualikan ekspresi “berlapis-lapis” seperti ???f(x)dx dari pertimbangan. Namun, batasan ini tidak terlalu signifikan, karena ekspresi apa pun, dengan menggunakan konvensi yang sesuai, dapat "diregangkan" ke dalam bentuk linier. Adakah himpunan M yang terdapat di L? disebut himpunan kata dari alfabet L. Jika kita sekadar mengatakan bahwa M adalah himpunan kata, maka yang kita maksudkan adalah kata dari alfabet tertentu. Sekarang asumsi tentang bahasa di atas dapat diutarakan ulang sebagai berikut: dalam bahasa apa pun, kumpulan ekspresi apa pun adalah kumpulan kata.

1.1.2. Banyak pernyataan yang benar

1.1.3. Pasangan bahasa yang mendasar

1.2. "Tidak dapat dibuktikan"

Yang dimaksud dengan “tidak dapat dibuktikan” adalah tidak adanya bukti.

1.3. Bukti

Setelah ditulis, buktinya menjadi sebuah kata dalam alfabet P, sama seperti teks bahasa Inggris lainnya adalah kata dalam alfabet L, contohnya diberikan di atas. Himpunan semua bukti membentuk himpunan bagian (dan himpunan bagian yang cukup luas) dari himpunan P?. Kami tidak akan mencoba untuk memberikan definisi yang tepat tentang konsep pembuktian yang “naif” dan “mutlak” ini secara bersamaan, atau - apa yang setara - untuk memberikan definisi dari subset P? yang bersesuaian. Sebaliknya, kami akan mempertimbangkan analogi formal dari konsep yang tidak jelas ini, yang di masa depan kami masih akan menggunakan istilah “bukti”. Analog ini memiliki dua ciri yang sangat penting yang membedakannya dari konsep intuitif (walaupun gagasan pembuktian intuitif masih mencerminkan ciri-ciri ini sampai batas tertentu). Pertama-tama, kita akui bahwa ada konsep pembuktian yang berbeda, yaitu, himpunan pembuktian yang berbeda di P? dapat diterima, dan bahkan lebih dari itu: kita sebenarnya akan mengakui bahwa alfabet pembuktian P itu sendiri dapat berubah. . Kita selanjutnya akan mensyaratkan bahwa untuk setiap konsep pembuktian tersebut terdapat metode yang efisien, dengan kata lain, suatu algoritma, yang tentu akan menentukan apakah suatu kata dalam alfabet P merupakan suatu pembuktian atau tidak. Kami juga akan berasumsi bahwa ada algoritma yang selalu dapat menentukan pernyataan mana yang dibuktikan oleh bukti tertentu. (Dalam banyak situasi, pernyataan yang dibuktikan hanyalah pernyataan terakhir dalam rangkaian langkah pembuktian.)

Jadi, definisi akhir kami adalah sebagai berikut:

(1) Kita mempunyai alfabet L (alfabet bahasa) dan alfabet P (alfabet bukti).

(3) Apakah kita juga mempunyai fungsi? (untuk mengetahui apa sebenarnya yang telah dibuktikan), ruang lingkupnya siapa? memenuhi kondisi P???P?, dan kisaran nilainya di P?. Kami berasumsi bahwa kami memiliki algoritma yang menghitung fungsi ini (arti sebenarnya dari kata "algoritma menghitung suatu fungsi" adalah: nilai fungsi diperoleh dengan menggunakan algoritma ini - seperangkat aturan transformasi khusus). Kita akan mengatakan bahwa elemen p? P merupakan pembuktian kata?(p) dari alfabet L.

Kondisi yang memenuhi tiga kali lipat (1)-(3) disebut sistem deduktif atas alfabet L.

Bagi pembaca yang familiar 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, pembuktian biasanya didefinisikan sebagai rangkaian 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 dalam alfabet bahasa kita, maka kita dapat menulis bukti tersebut dalam bentuk kata yang disusun menggunakan modifikasi alfabet yang dihasilkan: rangkaian ekspresi menjadi kata C1*C2*...*Cn . Dalam hal ini, fungsi yang menentukan apa yang sebenarnya telah dibuktikan mempunyai arti pada bagian kata tersebut tepat setelah huruf terakhir * pada barisan tersebut. Algoritma yang keberadaannya diperlukan pada bagian 1.3.2. definisi dapat dengan mudah dibuat setelah kita mendefinisikannya dengan tepat nilai-nilai yang diterima kata "aksioma" dan "aturan inferensi".

1.4 Upaya merumuskan teorema ketidaklengkapan secara tepat

1.4.1. Percobaan pertama

“Dalam kondisi tertentu untuk pasangan dasar bahasa alfabet L dan sistem deduktif atas L, selalu ada kata dalam T yang tidak memiliki bukti.” Pilihan ini masih terlihat samar-samar. Secara khusus, kita dapat dengan mudah menghasilkan sejumlah sistem deduktif yang hanya mempunyai sedikit kata yang dapat dibuktikan. Misalnya, dalam sistem deduktif kosong (dimana P = ?) tidak ada kata sama sekali yang mempunyai bukti.

1.4.2. Percobaan kedua

"Dalam kondisi tertentu mengenai pasangan fundamental, tidak ada sistem deduktif di mana setiap kata dari T mempunyai bukti."

1.5. Konsistensi

Wajar jika kita menuntut 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 diskusi berikutnya kita hanya akan tertarik pada sistem deduktif yang konsisten. Jika kita diberi suatu bahasa, maka akan sangat menggoda untuk menemukan sistem deduktif yang konsisten di mana setiap pernyataan yang benar akan mempunyai bukti. Versi teorema Gödel yang menarik perhatian kita menyatakan dengan tepat bahwa dalam kondisi tertentu mengenai pasangan fundamental, tidak mungkin menemukan sistem deduktif seperti itu.

1.6. Kelengkapan

Dikatakan sistem deduktif lengkap terhadap pasangan fundamentalnya, dengan syarat?(P)?T. Maka rumusan teorema ketidaklengkapan kita berbentuk sebagai berikut:

Dalam kondisi tertentu mengenai pasangan fundamental, tidak ada sistem deduktif atas L yang lengkap dan relatif konsisten.

Membagikan: