Teorem ketidaklengkapan Gödel mempunyai makna falsafah. Pengakuan seorang ahli logik yang hebat

Teorem ketidaklengkapan Godel

Uspensky V.A.

Mungkin teorem ketidaklengkapan Gödel adalah benar-benar unik. Unik kerana mereka merujuk kepadanya apabila mereka ingin membuktikan "segala-galanya di dunia" - dari kehadiran tuhan kepada ketiadaan akal. Saya sentiasa berminat dengan lebih "soalan utama" - dan siapa di antara mereka yang merujuk kepada teorem ketidaklengkapan bukan sahaja dapat merumuskannya, tetapi juga membuktikannya? saya pos artikel ini atas sebab ia membentangkan rumusan teorem Gödel yang sangat mudah diakses. Saya syorkan anda terlebih dahulu membaca artikel oleh Tullio Regge Kurt Gödel dan teoremnya yang terkenal

Kesimpulan tentang kemustahilan kriteria kebenaran universal adalah akibat langsung daripada hasil yang diperolehi oleh Tarski dengan menggabungkan teorem ketidakpastian Gödel dengan teori kebenarannya sendiri, yang menurutnya tidak boleh ada kriteria kebenaran universal walaupun untuk kawasan yang agak sempit. teori nombor, dan oleh itu untuk mana-mana sains menggunakan aritmetik. Sememangnya, keputusan ini menggunakan fortiori kepada konsep kebenaran dalam mana-mana bidang pengetahuan bukan matematik di mana aritmetik digunakan secara meluas.

Karl Popper

Uspensky Vladimir Andreevich dilahirkan pada 27 November 1930 di Moscow. Lulus dari Fakulti Mekanik dan Matematik Universiti Negeri Moscow (1952). Doktor Sains Fizikal dan Matematik (1964). Profesor, Ketua Jabatan Logik Matematik dan Teori Algoritma Fakulti Mekanik dan Matematik (1966). Membaca kursus kuliah "Pengantar Logik Matematik", "Fungsi Boleh Dikira", "Teorem Kesempurnaan Gödel". Menyediakan 25 calon dan 2 doktor sains

1. Pernyataan masalah

Teorem ketidaklengkapan, rumusan tepat yang akan kami berikan pada akhir bab ini, dan mungkin kemudian (jika pembaca berminat dengan ini) dan bukti, menyatakan kira-kira yang berikut: dalam keadaan tertentu dalam mana-mana bahasa ada benar, tetapi kenyataan yang tidak dapat dibuktikan.

Apabila kita merumuskan teorem dengan cara ini, hampir setiap perkataan memerlukan penjelasan. Oleh itu, kita akan mulakan dengan menerangkan maksud perkataan yang kita gunakan dalam rumusan ini.

1.1. Bahasa

Kami tidak akan memberikan definisi bahasa yang paling umum, lebih suka mengehadkan diri kami kepada konsep bahasa yang kami perlukan nanti. Terdapat dua konsep sedemikian: "abjad bahasa" dan "himpunan pernyataan sebenar bahasa".

1.1.1. Abjad

Mengikut abjad, kami bermaksud set terhingga tanda asas (iaitu, perkara yang tidak boleh dipecahkan kepada bahagian komponen). Watak-watak ini dipanggil huruf abjad. Dengan perkataan abjad yang kami maksudkan urutan akhir surat. Sebagai contoh, perkataan biasa dalam bahasa Inggeris (termasuk nama khas) ialah perkataan abjad 54 huruf (26 huruf kecil, 26 huruf besar, tanda sempang dan apostrof). Contoh lain ialah nombor asli dalam tatatanda perpuluhan ialah perkataan daripada abjad 10 huruf, yang hurufnya adalah tanda: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Untuk menandakan abjad, kita akan menggunakan huruf besar biasa. Jika L ialah abjad, maka L? akan menandakan set semua perkataan abjad L, - perkataan yang terbentuk daripada hurufnya. Kami akan menganggap bahawa mana-mana bahasa mempunyai abjadnya sendiri, supaya semua ungkapan bahasa ini (iaitu - nama pelbagai objek, pernyataan tentang objek ini, dll.) adalah perkataan abjad ini. Sebagai contoh, sebarang cadangan daripada bahasa Inggeris, serta mana-mana teks yang ditulis dalam bahasa Inggeris, boleh dianggap sebagai perkataan abjad 54 huruf yang dilanjutkan, yang juga termasuk tanda baca, ruang antara kata, tanda garis merah dan mungkin beberapa aksara berguna yang lain. Dengan mengandaikan bahawa ungkapan bahasa ialah perkataan bagi beberapa abjad, maka kami mengecualikan daripada pertimbangan "berbilang lapisan" ungkapan seperti ???f(x)dx. Walau bagaimanapun, had ini tidak terlalu ketara, kerana mana-mana ungkapan sedemikian, menggunakan konvensyen yang sesuai, boleh "diregangkan" ke dalam bentuk linear. Mana-mana set M yang terkandung dalam L? dipanggil set perkataan abjad L. Jika kita hanya mengatakan bahawa M ialah set perkataan, maka kita bermaksud bahawa ia adalah perkataan dari beberapa abjad. Sekarang andaian bahasa di atas boleh diutarakan semula seperti berikut: dalam mana-mana bahasa, sebarang set ungkapan ialah set perkataan.

1.1.2. Banyak dakwaan benar

Kami menganggap bahawa kami diberi subset T set L? (di mana L ialah abjad beberapa bahasa yang sedang kita pertimbangkan), yang dipanggil set "pernyataan benar" (atau ringkasnya "kebenaran"). Melewati terus ke subset T, kami meninggalkan langkah-langkah perantaraan penaakulan berikut: pertama, perkataan abjad L yang manakah merupakan ungkapan bahasa yang dibentuk dengan baik, iaitu, mempunyai nilai tertentu dalam tafsiran kami tentang bahasa ini (contohnya, 2+3, x+3, x=y, x=3, 2=3, 2=2 ialah ungkapan yang terbentuk dengan baik, manakala ungkapan seperti +=x bukan); kedua, ungkapan manakah yang merupakan formula, i.e. mungkin bergantung pada parameter (cth, x=3, x=y, 2=3, 2=2); ketiga, formula yang manakah merupakan formula tertutup, i.e. pernyataan yang tidak bergantung pada parameter (contohnya, 2=3, 2=2); dan akhirnya, formula tertutup yang manakah merupakan pernyataan benar (contohnya, 2=2).

1.1.3. Pasangan bahasa asas

1.2. "Tidak boleh dibuktikan"

"Tidak boleh dibuktikan" bermaksud tidak mempunyai bukti.

1.3. Bukti

Walaupun fakta bahawa istilah "bukti" mungkin salah satu yang paling penting dalam matematik (Bourbaki memulakan buku mereka "Asas Matematik" dengan kata-kata: "Sejak zaman Yunani kuno, mengatakan "matematik" bermaksud sama dengan mengatakan "bukti""), dia tidak mempunyai definisi yang tepat. Secara umum, konsep pembuktian dengan semua cabang semantiknya adalah milik bidang psikologi dan bukannya matematik. Tetapi walau bagaimanapun, bukti hanyalah hujah yang kita sendiri dapati cukup meyakinkan untuk meyakinkan orang lain.

Apabila ditulis, bukti menjadi perkataan dalam beberapa abjad P, sama seperti mana-mana teks bahasa Inggeris ialah perkataan abjad L, contoh yang diberikan di atas. Set semua bukti membentuk subset (dan agak besar subset) set P?. Kami tidak akan cuba memberikan definisi yang tepat tentang konsep pembuktian "naif" dan "mutlak" ini, atau - yang setara - untuk mentakrifkan subset yang sepadan bagi P?. Sebaliknya, kami akan mempertimbangkan analog formal konsep kabur ini, yang mana kami masih akan menggunakan istilah "bukti" dalam perkara berikut. Analog ini mempunyai dua ciri yang sangat penting yang membezakannya daripada konsep intuitif (walaupun idea intuitif bukti masih mencerminkan ciri-ciri ini sedikit sebanyak). Pertama sekali, kita menganggap bahawa terdapat konsep pembuktian yang berbeza, iaitu subset pembuktian yang berbeza dalam P? dibenarkan, malah lebih daripada itu: kita akan, sebenarnya, menganggap bahawa abjad pembuktian P itu sendiri boleh berubah. . Dalam perkara berikut, kami akan menghendaki bahawa bagi setiap konsep pembuktian sedemikian terdapat kaedah yang cekap, dengan kata lain, algoritma yang semestinya akan menentukan sama ada perkataan yang diberikan abjad P bukti atau tidak. Kami juga menganggap bahawa terdapat algoritma yang sentiasa boleh menentukan pernyataan mana yang membuktikan diberi bukti. (Dalam banyak situasi, pernyataan yang dibuktikan hanyalah pernyataan terakhir dalam urutan langkah yang membentuk bukti.)

Oleh itu, kata-kata akhir definisi kami adalah seperti berikut:

(1) Kami mempunyai abjad L (abjad bahasa) dan abjad P (abjad pembuktian).

(2) Kita diberi set P yang merupakan subset P? dan unsur-unsurnya dipanggil "bukti". Pada masa hadapan, kami akan menganggap bahawa kami juga mempunyai algoritma yang membolehkan kami menentukan sama ada perkataan arbitrari abjad P adalah unsur set P, iaitu bukti atau tidak.

(3) Juga kita mempunyai fungsi? (untuk mencari apa sebenarnya yang telah dibuktikan), domain siapa? memenuhi syarat P???P?, dan julat siapakah dalam P?. Kami menganggap bahawa kami mempunyai algoritma yang mengira fungsi ini (maksud tepat perkataan "algoritma mengira fungsi" adalah seperti berikut: nilai fungsi diperoleh menggunakan algoritma ini - satu set peraturan transformasi khas). Kami akan mengatakan bahawa unsur p? P ialah bukti perkataan?(p) abjad L.

Troika<Р, Р, ?>, keadaan yang memuaskan (1)-(3) dipanggil sistem deduktif ke atas abjad L.

Bagi pembaca yang biasa dengan cara biasa mentakrifkan "bukti" dari segi "aksiom" dan "peraturan inferens", kami kini akan menerangkan bagaimana kaedah ini boleh dianggap sebagai kes khas definisi yang diberikan dalam bahagian 1.3.2. Maksudnya, pembuktian biasanya ditakrifkan sebagai urutan ungkapan bahasa tersebut, yang setiap satunya adalah aksiom atau sebelumnya diperoleh daripada pernyataan sedia ada menggunakan salah satu peraturan inferens. Jika kita menambah perkataan baru * pada abjad bahasa kita, maka kita boleh menulis bukti seperti perkataan yang digubah menggunakan abjad yang terhasil: urutan ungkapan menjadi perkataan C1*C2*...*Cn. Dalam kes ini, fungsi yang menentukan perkara yang telah dibuktikan mempunyai nilainya di bahagian perkataan ini serta-merta selepas huruf terakhir * dalam urutan. Algoritma yang kewujudannya diperlukan dalam Bahagian 1.3.2. takrifan, boleh dibina dengan mudah apabila kita telah mentakrifkan dengan tepat mana-mana makna yang diterima bagi perkataan "aksiom" dan "peraturan inferens".

1.4 Percubaan untuk merumus dengan tepat teorem ketidaklengkapan

1.4.1. Percubaan pertama

"Di bawah syarat tertentu untuk pasangan asas bahasa abjad L dan sistem deduktif<Р, Р, ?>di atas L, sentiasa ada perkataan dalam T yang tidak mempunyai bukti. Pilihan ini masih kelihatan samar-samar. Khususnya, kita boleh dengan mudah menghasilkan seberapa banyak sistem deduktif yang kita suka yang mempunyai sangat sedikit perkataan yang boleh dibuktikan. ?) tiada perkataan sama sekali itu akan mempunyai bukti.

1.4.2. Percubaan kedua

Ada lagi, lebih pendekatan semula jadi. Katakan kita diberi bahasa - dalam erti kata kita diberi pasangan asas bahasa ini. Sekarang kita akan mencari sistem deduktif ke atas L (secara intuitif, kita sedang mencari teknik pembuktian) yang dengannya kita boleh membuktikan bagaimana lebih banyak perkataan daripada T, dalam had semua perkataan daripada teorem T. Gödel menerangkan situasi di mana sistem deduktif sedemikian (dengan caranya setiap perkataan dalam T boleh dibuktikan) tidak wujud. Oleh itu, kami ingin merumuskan pernyataan berikut:

"Di bawah syarat-syarat tertentu mengenai pasangan asas, tidak ada sistem deduktif sedemikian di mana setiap perkataan daripada T akan mempunyai bukti."

Walau bagaimanapun, pernyataan sedemikian jelas palsu, kerana hanya perlu mengambil sistem deduktif di mana P = L, P = P? dan?(p) = p untuk semua p dalam P?; maka setiap perkataan dari L? boleh dibuktikan secara remeh. Oleh itu, kita perlu menerima beberapa had pada sistem deduktif yang kita gunakan.

1.5. Konsisten

Adalah wajar untuk menghendaki bahawa hanya "pernyataan yang benar", iaitu, hanya perkataan dari T, boleh dibuktikan. Kita akan mengatakan bahawa sistem deduktif<Р, Р, ?>adalah konsisten berkenaan dengan pasangan asas jika?(P)?T. Dalam semua penaakulan seterusnya, kami hanya akan berminat dengan sistem deduktif yang konsisten tersebut. Jika kita diberi bahasa, maka ia akan menjadi sangat menarik untuk mencari sistem deduktif yang konsisten di mana setiap pernyataan yang benar akan mempunyai bukti. Varian teorem Gödel yang menarik minat kita dengan tepat menyatakan bahawa dalam keadaan tertentu berkenaan dengan pasangan asas, adalah mustahil untuk mencari sistem deduktif sedemikian.

1.6. kesempurnaan

Dikatakan bahawa sistem deduktif<Р,Р,?>adalah lengkap berkenaan dengan pasangan asas, dengan syarat?(P)?T. Kemudian perumusan teorem ketidaklengkapan kami mengambil bentuk berikut:

Di bawah syarat tertentu mengenai pasangan asas, tidak ada sistem deduktif sedemikian<Р,Р,?>lebih L yang akan lengkap dan agak konsisten.

Bibliografi

Untuk penyediaan kerja ini, bahan dari tapak http://filosof.historic.ru telah digunakan.

Salah satu yang paling teorem yang diketahui logik matematik bertuah dan malang pada masa yang sama. Dalam hal ini dia seperti teori khas Relativiti Einstein. Di satu pihak, hampir semua orang telah mendengar sesuatu tentang mereka. Sebaliknya, dalam tafsiran popular, teori Einstein, seperti yang anda tahu, "mengatakan segala sesuatu di dunia adalah relatif". Dan teorem ketidaklengkapan Gödel (selepas ini hanya TGN), dalam rumusan rakyat yang hampir sama bebas, "membuktikan bahawa ada perkara yang tidak dapat difahami oleh akal manusia". Oleh itu, sesetengah cuba menyesuaikannya sebagai hujah menentang materialisme, sementara yang lain, sebaliknya, membuktikan dengan bantuannya bahawa tidak ada tuhan. Sungguh melucukan bukan sahaja kedua-dua belah pihak tidak boleh betul pada masa yang sama, tetapi juga tidak seorang pun atau yang lain mengganggu untuk memikirkan apa, sebenarnya, teorem ini katakan.

Jadi apa? Di bawah ini saya akan cuba "di jari" untuk bercakap mengenainya. Eksposisi saya, sudah tentu, tidak ketat dan intuitif, tetapi saya akan meminta ahli matematik untuk tidak menilai saya dengan tegas. Ada kemungkinan bahawa untuk bukan ahli matematik (yang, sebenarnya, saya juga tergolong), akan ada sesuatu yang baru dan berguna dalam apa yang diceritakan di bawah.

Logik matematik sememangnya sains yang agak rumit, dan yang paling penting, tidak begitu biasa. Ia memerlukan gerakan yang berhati-hati dan ketat, di mana ia adalah penting untuk tidak mengelirukan yang benar-benar terbukti dengan fakta bahawa "ia sudah jelas." Walau bagaimanapun, saya berharap untuk memahami "garis besar pembuktian TGN" berikut, pembaca hanya memerlukan pengetahuan tentang matematik sekolah / sains komputer, kemahiran pemikiran logik dan 15-20 minit masa.

Memudahkan sedikit, TGN mendakwa bahawa ia sudah mencukupi bahasa yang sukar terdapat kenyataan yang tidak berasas. Tetapi dalam frasa ini, hampir setiap perkataan memerlukan penjelasan.

Mari kita mulakan dengan cuba memikirkan apa itu bukti. Mari kita ambil beberapa masalah sekolah dalam aritmetik. Sebagai contoh, biarkan ia diperlukan untuk membuktikan ketepatan formula tidak rumit berikut: "" (Saya mengingatkan anda bahawa simbol dibaca "untuk mana-mana" dan dipanggil "pengkuantiti sejagat"). Ia boleh dibuktikan dengan mengubah secara identik, katakan, seperti ini:

Peralihan dari satu formula ke formula yang lain berlaku mengikut beberapa peraturan yang diketahui. Peralihan dari formula ke-4 kepada formula ke-5 berlaku, katakan, kerana setiap nombor adalah sama dengan dirinya sendiri - itulah aksiom aritmetik. Dan keseluruhan prosedur untuk membuktikan, dengan itu, menterjemahkan formula ke dalam nilai boolean BENAR. Hasilnya boleh jadi PALSU - jika kita menafikan beberapa formula. Dalam kes ini, kami akan membuktikan penafiannya. Adalah mungkin untuk membayangkan program (dan program sedemikian sebenarnya ditulis) yang akan membuktikan cadangan tersebut (dan lebih kompleks) tanpa campur tangan manusia.

Mari kita nyatakan perkara yang sama secara formal. Katakan kita mempunyai set yang terdiri daripada rentetan aksara beberapa abjad, dan terdapat peraturan yang menggunakan subset daripada apa yang dipanggil kenyataan- iaitu frasa yang bermakna dari segi tatabahasa, setiap satunya adalah benar atau salah. Kita boleh mengatakan bahawa terdapat fungsi yang sepadan dengan pernyataan daripada salah satu daripada dua nilai: TRUE atau FALSE (iaitu, memetakannya kepada set Boolean dua elemen).

Mari kita panggil pasangan sedemikian - satu set pernyataan dan fungsi dari - "bahasa pernyataan". Perhatikan bahawa dalam pengertian sehari-hari konsep bahasa agak lebih luas. Sebagai contoh, frasa Rusia "Nah, mari sini!" adalah tidak benar dan tidak palsu, iaitu dari sudut logik matematik, ia bukanlah satu pernyataan.

Untuk apa yang berikut, kita memerlukan tanggapan algoritma. Saya tidak akan memberikan takrif formalnya di sini - ini akan membawa kita jauh ke tepi. Saya akan menghadkan diri saya kepada perkara tidak formal: "algoritma"- urutan arahan yang tidak jelas ini ("program"), yang per nombor terhingga langkah-langkah menukar data input kepada output. Huruf condong pada asasnya penting - jika program digantung pada beberapa data awal, maka ia tidak menerangkan algoritma. Untuk kesederhanaan dan dalam aplikasi kes kami, pembaca boleh menganggap bahawa algoritma ialah program yang ditulis dalam mana-mana bahasa pengaturcaraan yang diketahuinya, yang, untuk sebarang data input dari kelas tertentu, dijamin untuk menyelesaikan kerjanya dengan hasil Boolean.

Mari kita tanya diri kita sendiri: adakah terdapat "algoritma pembuktian" untuk setiap fungsi (atau, ringkasnya, "deduktif") bersamaan dengan fungsi ini, iaitu, menterjemah setiap pernyataan ke dalam nilai boolean yang sama dengannya? Lebih ringkas, soalan yang sama boleh dirumuskan seperti berikut: adakah setiap fungsi di atas satu set proposisi boleh dikira? Seperti yang anda sudah boleh meneka, ia mengikuti dari kesahihan TGN bahawa tidak, tidak ada - terdapat fungsi tidak boleh dikira jenis ini. Dengan kata lain, tidak setiap kenyataan yang benar dapat dibuktikan.

Mungkin kenyataan ini akan menyebabkan anda protes dalaman. Ini disebabkan oleh beberapa keadaan. Pertama, apabila kita diajar matematik sekolah, maka kadangkala terdapat tanggapan palsu tentang identiti yang hampir lengkap bagi frasa "teorem adalah benar" dan "ada kemungkinan untuk membuktikan atau mengesahkan teorem". Tetapi jika anda fikirkan, ia sama sekali tidak jelas. Sesetengah teorem dibuktikan dengan agak mudah (contohnya, dengan penghitungan sebilangan kecil pilihan), dan ada yang sangat sukar. Pertimbangkan, sebagai contoh, Teorem Terakhir Fermat yang terkenal:

bukti yang ditemui hanya tiga setengah abad selepas perumusan pertama (dan ia jauh dari asas). Adalah perlu untuk membezakan antara kebenaran sesuatu kenyataan dan kebolehbuktiannya. Ia tidak mengikuti dari mana-mana sahaja bahawa tidak ada kenyataan yang benar, tetapi tidak boleh dibuktikan (dan tidak boleh disahkan sepenuhnya).

Hujah intuitif kedua terhadap TGN adalah lebih halus. Katakan kita mempunyai beberapa pernyataan yang tidak dapat dibuktikan (dalam rangka kerja deduktif ini). Apakah yang menghalang kita daripada menerimanya sebagai aksiom baharu? Oleh itu, kami akan merumitkan sedikit sistem pembuktian kami, tetapi ini tidak mengerikan. Hujah ini betul-betul betul jika terdapat bilangan dalil yang tidak dapat dibuktikan. Dalam amalan, perkara berikut mungkin berlaku - selepas membuat postulat aksiom baharu, anda akan terjumpa kenyataan baharu yang tidak boleh dibuktikan. Ambil ia sebagai aksiom lain - anda akan tersandung pada yang ketiga. Dan seterusnya ad infinitum. Mereka berkata deductica akan kekal tidak lengkap. Kami juga boleh mengambil langkah tegas supaya algoritma pembuktian berakhir selepas beberapa langkah yang terhad dengan beberapa keputusan untuk sebarang pernyataan bahasa. Tetapi pada masa yang sama, dia akan mula berbohong - membawa kepada kebenaran untuk kenyataan yang salah, atau pembohongan - untuk orang yang beriman. Dalam kes sedemikian dikatakan bahawa deduktif bercanggah. Oleh itu, satu lagi rumusan TGN berbunyi seperti ini: "Terdapat bahasa proposisi yang mustahil untuk deduktik konsisten yang lengkap" - maka nama teorem itu.

Kadang-kadang dipanggil "teorem Gödel" ialah pernyataan bahawa mana-mana teori mengandungi masalah yang tidak dapat diselesaikan dalam kerangka teori itu sendiri dan memerlukan generalisasinya. Dalam erti kata ini adalah benar, walaupun rumusan sedemikian mengaburkan isu itu dan bukannya menjelaskannya.

Saya juga ambil perhatian bahawa jika kita bercakap tentang fungsi biasa yang memaparkan set nombor nyata ke dalamnya, maka "tidak boleh dikira" fungsi itu tidak akan mengejutkan sesiapa sahaja (jangan mengelirukan "fungsi boleh dikira" dan "nombor boleh dikira" - ini adalah perkara yang berbeza). Mana-mana murid sekolah tahu bahawa, katakan, dalam kes fungsi, anda mesti sangat bertuah dengan hujah supaya proses mengira perwakilan perpuluhan tepat bagi nilai fungsi ini berakhir dengan bilangan langkah yang terhad. Dan kemungkinan besar anda akan mengiranya menggunakan siri tak terhingga, dan pengiraan ini tidak akan pernah membawa kepada hasil yang tepat, walaupun ia boleh mendekatinya seperti yang anda suka - semata-mata kerana nilai sinus kebanyakan hujah adalah tidak rasional. TGN hanya memberitahu kita bahawa walaupun di antara fungsi yang hujahnya adalah rentetan dan nilainya adalah sifar atau satu, fungsi tidak boleh dikira, walaupun disusun dalam cara yang sama sekali berbeza, juga wujud.

Untuk perkara berikut, kami akan menerangkan "bahasa aritmetik formal". Pertimbangkan kelas rentetan teks dengan panjang terhingga, yang terdiri daripada angka Arab, pembolehubah (huruf abjad Latin), mengambil nilai semula jadi, ruang, watak operasi aritmetik, kesamaan dan ketidaksamaan, pengkuantiti (“wujud”) dan (“untuk mana-mana”) dan, mungkin, beberapa simbol lain (nombor dan komposisi tepatnya tidak penting bagi kami). Adalah jelas bahawa tidak semua baris sedemikian bermakna (contohnya, "" adalah karut). Subset ungkapan bermakna daripada kelas ini (iaitu, rentetan yang benar atau salah dari segi aritmetik biasa) akan menjadi set pernyataan kami.

Contoh pernyataan aritmetik formal:

dan lain-lain. Sekarang mari kita panggil "formula dengan parameter percuma" (FSP) rentetan yang menjadi pernyataan jika kita menggantikannya sebagai parameter ini nombor asli. Contoh FSP (dengan parameter):

dan lain-lain. Dalam erti kata lain, FSP adalah bersamaan dengan fungsi hujah semula jadi dengan nilai Boolean.

Nyatakan set semua FSP dengan huruf . Adalah jelas bahawa ia boleh dipesan (contohnya, kita mula-mula menulis formula satu huruf yang disusun mengikut abjad, diikuti dengan formula dua huruf, dsb.; mengikut abjad mana susunan akan berlaku bukanlah asas kepada kita). Oleh itu, mana-mana FSP sepadan dengan nombornya dalam senarai tersusun, dan kami akan menandakannya .

Mari kita beralih kepada lakaran bukti TGN dalam rumusan berikut:

Untuk bahasa proposisi aritmetik formal, tiada potongan konsisten yang lengkap.

Kami akan membuktikan dengan percanggahan.

Jadi mari kita anggap bahawa deduktif sedemikian wujud. Mari kita terangkan algoritma tambahan berikut yang memberikan nilai boolean kepada nombor asli seperti berikut:

Ringkasnya, algoritma menghasilkan nilai TRUE jika dan hanya jika hasil penggantian ke dalam FSP nombornya sendiri dalam senarai kami memberikan pernyataan palsu.

Di sini kita datang ke satu-satunya tempat di mana saya akan meminta pembaca untuk mengambil kata-kata saya untuk itu.

Jelas sekali, di bawah andaian di atas, mana-mana FSP daripada boleh dikaitkan dengan algoritma yang mengandungi nombor asli pada input dan nilai Boolean pada output. Kurang jelas adalah sebaliknya:

Bukti lemma ini memerlukan sekurang-kurangnya definisi formal, bukan intuitif, tentang tanggapan algoritma. Walau bagaimanapun, jika anda fikirkan sedikit, ia adalah agak munasabah. Sesungguhnya, algoritma ditulis dalam bahasa algoritma, di antaranya terdapat yang eksotik seperti, contohnya, Brainfuck , yang terdiri daripada lapan perkataan satu aksara, di mana, bagaimanapun, sebarang algoritma boleh dilaksanakan. Adalah pelik jika bahasa formula aritmetik formal yang lebih kaya yang telah kami huraikan akan menjadi lebih miskin - walaupun, tidak syak lagi, ia tidak begitu sesuai untuk pengaturcaraan biasa.

Selepas melepasi tempat licin ini, kami cepat sampai ke penghujung.

Jadi, kami telah menerangkan algoritma di atas. Menurut lemma yang saya minta anda percaya, wujud FSP yang setara. Ia mempunyai beberapa nombor dalam senarai - katakan . Mari kita tanya diri kita, apa gunanya? Biarlah ianya BENAR. Kemudian, mengikut pembinaan algoritma (dan oleh itu fungsi yang setara dengannya), ini bermakna hasil penggantian nombor ke dalam fungsi adalah SALAH. Sebaliknya disemak dengan cara yang sama: daripada FALSE mengikuti TRUE. Kami telah sampai pada percanggahan, yang bermaksud bahawa andaian asal adalah salah. Oleh itu, untuk aritmetik formal, tiada potongan konsisten yang lengkap. Q.E.D.

Di sini adalah wajar untuk mengingati Epimenides (lihat potret dalam tajuk), yang, seperti yang anda tahu, mengisytiharkan bahawa semua orang Kreta adalah pembohong, kerana dirinya sendiri seorang Kreta. Dalam rumusan yang lebih ringkas, kenyataannya (dikenali sebagai "paradoks pembohong") boleh dirumuskan sebagai: "Saya berbohong." Pernyataan sedemikian, yang dengan sendirinya menyatakan kepalsuannya, yang kami gunakan untuk pembuktiannya.

Sebagai kesimpulan, saya ingin ambil perhatian bahawa TGN tidak menuntut apa-apa yang sangat mengejutkan. Lagipun, semua orang telah lama terbiasa dengan fakta bahawa tidak semua nombor boleh diwakili sebagai nisbah dua integer (ingat, kenyataan ini mempunyai bukti yang sangat elegan yang berusia lebih daripada dua ribu tahun?). Dan punca polinomial dengan pekali rasional juga bukan semua nombor. Dan kini ternyata tidak semua fungsi hujah semula jadi boleh dikira.

Lakaran bukti yang diberikan adalah untuk aritmetik formal, tetapi tidak sukar untuk melihat bahawa THN terpakai kepada banyak bahasa proposisi yang lain juga. Sudah tentu, tidak semua bahasa seperti itu. Sebagai contoh, mari kita tentukan bahasa seperti ini:

"Apa-apa frasa cina adalah kenyataan yang benar jika ia terkandung dalam buku petikan Komrad Mao Tse Tung, dan tidak betul jika ia tidak terkandung.

Kemudian algoritma pembuktian lengkap dan konsisten yang sepadan (ia boleh dipanggil "deduktif dogmatik") kelihatan seperti ini:

“Selak buku petikan Komrad Mao Tse Tung sehingga anda menemui kenyataan yang anda cari. Jika didapati, maka ia adalah benar, dan jika buku petikan itu habis, dan kenyataan itu tidak dijumpai, maka ia adalah palsu.

Di sini kita diselamatkan oleh fakta bahawa mana-mana petikan jelas terhingga, jadi proses "membuktikan" pasti akan berakhir. Oleh itu, TGN tidak boleh digunakan untuk bahasa pernyataan dogmatik. Tetapi kita bercakap tentang bahasa yang kompleks, bukan?

Teorem ketidaklengkapan Kurt Gödel adalah titik perubahan dalam matematik abad ke-20. Dan dalam manuskripnya, yang diterbitkan selepas kematiannya, bukti logik tentang kewujudan Tuhan telah dipelihara. Pada Bacaan Krismas yang lalu, laporan menarik mengenai warisan yang kurang dikenali ini telah dibuat oleh Profesor Madya Seminari Teologi Tobolsk, Calon Teologi, Paderi Dimitri Kiryanov. "NS" diminta menjelaskan idea utama saintis itu.

Teorem Ketidaklengkapan Gödel: Satu Lubang dalam Matematik

- Bolehkah anda menerangkan secara popular teorem ketidaklengkapan Gödel? Tukang gunting rambut hanya mencukur mereka yang tidak mencukur sendiri. Adakah tukang gunting mencukur dirinya sendiri? Adakah paradoks terkenal ini ada kaitan dengan mereka?

Tesis utama bukti logik kewujudan Tuhan, yang dikemukakan oleh Kurt Gödel: "Tuhan wujud dalam pemikiran. Tetapi kewujudan dalam realiti lebih besar daripada kewujudan dalam pemikiran sahaja. Oleh itu, Tuhan mesti wujud." Dalam foto: pengarang teorem ketidaklengkapan Kurt Godel dengan rakannya, pengarang teori relativiti Albert Einstein. Preston. Amerika. 1950

- Ya, sudah tentu ada. Sebelum Gödel, terdapat masalah aksiomatisasi matematik dan masalah ayat paradoks sedemikian yang boleh ditulis secara rasmi dalam mana-mana bahasa. Contohnya: "Pernyataan ini palsu." Apakah kebenaran kenyataan ini? Jika ia benar, maka ia adalah palsu, jika ia palsu, maka ia adalah benar; mengakibatkan paradoks linguistik. Gödel menyiasat aritmetik dan menunjukkan dalam teoremnya bahawa ketekalannya tidak dapat dibuktikan daripada prinsip-prinsipnya yang jelas: aksiom penambahan, penolakan, pembahagian, pendaraban, dan sebagainya. Kami memerlukan beberapa andaian tambahan untuk membenarkannya. Ia adalah pada sangat teori yang paling mudah, tetapi bagaimana pula dengan yang lebih kompleks (persamaan fizik, dll.)! Untuk mewajarkan beberapa sistem penaakulan, kami sentiasa terpaksa menggunakan beberapa penaakulan tambahan, yang tidak wajar dalam rangka kerja sistem.

Pertama sekali, ini menunjukkan batasan tuntutan minda manusia dalam pengetahuan realiti. Iaitu, kita tidak boleh mengatakan bahawa kita akan membina beberapa jenis teori komprehensif tentang alam semesta yang akan menjelaskan segala-galanya - teori sedemikian tidak boleh saintifik.

Apakah perasaan ahli matematik sekarang tentang teorem Gödel? Tiada siapa yang cuba untuk menyangkal mereka, entah bagaimana boleh pergi?

“Ia seperti cuba untuk menyangkal teorem Pythagoras. Teorem mempunyai bukti logik yang ketat. Pada masa yang sama, percubaan sedang dibuat untuk mencari had ke atas kebolehgunaan teorem Gödel. Tetapi kebanyakan kontroversi berkisar tentang implikasi falsafah teorem Gödel.

Sejauh manakah bukti Gödel tentang kewujudan Tuhan? Adakah ia selesai?

- Ia telah diusahakan secara terperinci, walaupun saintis itu sendiri tidak berani menerbitkannya sehingga kematiannya. Gödel membangunkan ontologi (metafizik. — "NS") hujah yang pertama kali dicadangkan oleh Anselm of Canterbury. Dalam bentuk yang ringkas, hujah ini boleh diungkapkan seperti berikut: “Tuhan, menurut definisi, adalah Dia yang lebih besar daripada-Nya yang tiada apa yang dapat dibayangkan. Tuhan wujud dalam pemikiran. Tetapi kewujudan dalam realiti adalah lebih besar daripada kewujudan dalam pemikiran sahaja. Oleh itu, Tuhan mesti ada." Hujah Anselm kemudiannya dikembangkan oleh René Descartes dan Gottfried Wilhelm Leibniz. Jadi, menurut Descartes, untuk memikirkan Makhluk Sempurna yang Lebih Tinggi, yang kekurangan kewujudan, bermakna jatuh ke dalam percanggahan logik. Dalam konteks idea-idea ini, Gödel membangunkan versi buktinya sendiri; ia benar-benar sesuai dengan dua halaman. Malangnya, pembentangan hujahnya adalah mustahil tanpa memperkenalkan logik modal yang sangat kompleks ke dalam asas.

Sudah tentu, ketidaksempurnaan logik kesimpulan Godel tidak memaksa seseorang untuk menjadi orang percaya di bawah tekanan kekuatan bukti. Kita tidak seharusnya bersikap naif dan percaya bahawa kita boleh meyakinkan sesiapa sahaja dengan munasabah orang yang berfikir percaya kepada Tuhan melalui hujah ontologi atau bukti lain. Iman lahir apabila seseorang berhadapan dengan kehadiran yang nyata dari Realiti Tuhan yang transenden yang tertinggi. Tetapi terdapat sekurang-kurangnya seorang yang hujah ontologi membawa kepada kepercayaan agama, dan itu adalah penulis Clive Staples Lewis, yang sendiri mengakuinya.

Masa depan yang jauh adalah masa lalu yang jauh

Apakah perasaan rakan seangkatan Gödel tentangnya? Adakah dia berkawan dengan salah seorang saintis yang hebat?

Pembantu Einstein di Princeton memberi keterangan bahawa satu-satunya orang dengan siapa dia berkawan tahun lepas hidup ialah Kurt Gödel. Mereka berbeza dalam hampir semua perkara - Einstein pandai bergaul, ceria, dan Gödel sangat serius, benar-benar kesepian dan tidak percaya. Tetapi mereka telah kualiti keseluruhan: kedua-duanya pergi lurus dan ikhlas kepada persoalan utama sains dan falsafah. Walaupun persahabatannya dengan Einstein, Gödel mempunyai pandangan khusus tentang agama. Dia menolak idea Tuhan sebagai makhluk yang tidak peribadi, seperti Tuhan untuk Einstein. Pada kesempatan ini Gödel berkata: “Agama Einstein terlalu abstrak, seperti Spinoza dan falsafah India. Tuhan Spinoza adalah kurang daripada seseorang; Tuhanku lebih daripada seorang; kerana Tuhan boleh memainkan peranan seseorang.” Mungkin ada roh yang tidak mempunyai badan, tetapi boleh berkomunikasi dengan kita dan mempengaruhi dunia.”

Bagaimanakah Gödel berakhir di Amerika? Melarikan diri dari Nazi?

- Ya, dia datang ke Amerika pada tahun 1940 dari Jerman, walaupun pada hakikatnya Nazi mengiktirafnya sebagai Aryan dan saintis yang hebat, membebaskannya daripada perkhidmatan ketenteraan. Dia dan isterinya Adele melalui Rusia melalui Keretapi Trans-Siberia. Dia tidak meninggalkan kenangan tentang perjalanan ini. Adele hanya ingat ketakutan yang berterusan pada waktu malam, bahawa mereka akan berhenti dan kembali. Selepas lapan tahun tinggal di Amerika, Gödel menjadi warganegara AS. Seperti semua pemohon kewarganegaraan, dia terpaksa menjawab soalan mengenai Perlembagaan AS. Sebagai seorang yang teliti, dia membuat persediaan untuk peperiksaan ini dengan sangat berhati-hati. Akhirnya, dia berkata bahawa dia telah menemui percanggahan dalam Perlembagaan: "Saya menemui kemungkinan yang sah secara logik di mana Amerika Syarikat boleh menjadi diktator." Rakan-rakannya mengakui bahawa, tanpa mengira merit logik hujah Gödel, kemungkinan ini adalah bersifat hipotesis semata-mata, dan memberi amaran terhadap perbualan panjang mengenai subjek dalam peperiksaan.

Adakah Gödel dan Einstein menggunakan idea masing-masing dalam kerja saintifik?

— Pada tahun 1949, Gödel menyatakan idea kosmologinya dalam esei matematik, yang menurut Albert Einstein, merupakan sumbangan penting kepada teori umum relativiti. Gödel percaya bahawa masa - "entiti misteri dan pada masa yang sama bertentangan diri yang membentuk asas dunia dan kewujudan kita sendiri" - akhirnya akan menjadi ilusi terhebat. Ia "suatu hari nanti" akan berhenti wujud, dan satu lagi bentuk makhluk akan datang, yang boleh dipanggil keabadian. Idea masa ini membawa ahli logik yang hebat kepada kesimpulan yang tidak dijangka. Dia menulis: “Saya yakin tentang kehidupan akhirat, tanpa mengira teologi. Jika dunia dibina dengan bijak, maka pasti ada akhirat."

"Masa adalah entiti yang bercanggah dengan diri sendiri." Bunyi pelik; ia mempunyai beberapa makna fizikal?

Gödel menunjukkan bahawa dalam kerangka persamaan Einstein adalah mungkin untuk membina model kosmologi dengan masa tertutup, di mana masa lalu yang jauh dan masa depan yang jauh bertepatan. Dalam model ini, ia menjadi secara teori perjalanan yang mungkin dalam masa. Bunyinya pelik, tetapi ia boleh diungkapkan secara matematik - itulah maksudnya. Model ini mungkin mempunyai implikasi percubaan atau tidak. Ia adalah binaan teori yang mungkin berguna atau mungkin tidak dalam membina model kosmologi baharu. Fizik teori moden, khususnya kosmologi kuantum, mempunyai struktur matematik yang kompleks sehingga sangat sukar untuk memberikan struktur ini pemahaman falsafah yang tidak jelas. Selain itu, beberapa pembinaan teorinya masih tidak dapat disahkan secara eksperimen atas sebab mudah pengesahannya memerlukan pengesanan zarah tenaga yang sangat tinggi. Ingat bagaimana orang ramai terkejut tentang pelancaran Large Hadron Collider: dana media massa sentiasa menakutkan orang dengan pendekatan akhir dunia. Malah, serius eksperimen saintifik untuk menguji model kosmologi kuantum dan apa yang dipanggil "teori penyatuan besar". Sekiranya mungkin untuk mengesan zarah Higgs yang dipanggil, maka ini akan menjadi langkah seterusnya dalam pemahaman kita tentang peringkat awal kewujudan alam semesta kita. Tetapi sehingga terdapat data eksperimen, model bersaing kosmologi kuantum terus menjadi model matematik sahaja.

Iman dan intuisi

“…Tuhanku lebih daripada seorang manusia; kerana Tuhan boleh memainkan peranan seseorang…” Adakah iman Gödel masih jauh dari pengakuan Ortodoks?

— Sangat sedikit kenyataan Gödel tentang imannya telah dipelihara, ia dikumpulkan sedikit demi sedikit. Walaupun fakta bahawa Gödel membuat draf pertama versi hujahnya sendiri seawal tahun 1941, sehingga tahun 1970, kerana takut akan cemuhan rakan-rakannya, dia tidak bercakap mengenainya. Pada Februari 1970, merasakan kematiannya semakin hampir, dia membenarkan pembantunya menyalin versi buktinya. Selepas kematian Gödel pada tahun 1978, versi hujah ontologi yang sedikit berbeza ditemui dalam kertas kerjanya. Isteri Kurt Gödel, Adele, berkata dua hari selepas kematian suaminya bahawa Gödel, "walaupun dia tidak menghadiri gereja, beragama dan membaca Alkitab di atas katil setiap pagi Ahad."

Apabila kita bercakap tentang saintis seperti Gödel, Einstein atau, katakan, Galileo atau Newton, adalah penting untuk menekankan bahawa mereka bukan ateis. Mereka melihat bahawa di sebalik Alam Semesta ada Akal, yang pasti Kuasa tinggi. Bagi ramai saintis, kepercayaan terhadap kewujudan Kecerdasan Tertinggi adalah salah satu akibat daripada refleksi saintifik mereka, dan refleksi ini tidak selalu membawa kepada kemunculan hubungan agama yang mendalam antara manusia dan Tuhan. Berkenaan dengan Gödel, seseorang boleh mengatakan bahawa dia merasakan keperluan untuk hubungan ini, kerana dia menekankan bahawa dia seorang teis, bahawa dia menganggap Tuhan sebagai seorang manusia. Tetapi, sudah tentu, imannya tidak boleh dipanggil ortodoks. Dia, boleh dikatakan, seorang "Lutheran rumah."

- Anda boleh memberi contoh sejarah: Bagaimanakah ahli sains yang berbeza percaya kepada Tuhan? Berikut adalah genetik Francis Collins, menurut pengakuannya, kajian struktur DNA membawa kepada iman kepada Tuhan ...

“Dengan sendirinya, pengetahuan semula jadi tentang Tuhan tidak mencukupi untuk pengetahuan tentang Tuhan. Ia tidak mencukupi untuk menemui Tuhan dengan mengkaji alam semula jadi - adalah penting untuk belajar mengenali-Nya melalui Wahyu yang Tuhan berikan kepada manusia. Kedatangan seseorang kepada iman, sama ada dia seorang saintis atau tidak, sentiasa bergantung kepada sesuatu yang melampaui hujah logik atau saintifik semata-mata. Francis Collins menulis bahawa dia datang kepada agama pada usia 27 tahun selepas pertikaian intelektual yang panjang dengan dirinya dan di bawah pengaruh Clive Staples Lewis. Dua orang berada dalam situasi sejarah yang sama, di bawah keadaan awal yang sama: seorang menjadi mukmin, seorang lagi ateis. Kajian DNA sahaja membawa kepada kepercayaan kewujudan Tuhan. Kajian lain dan tidak datang kepadanya. Dua orang melihat gambar itu: seorang menganggapnya cantik, dan yang lain berkata: "Begitu-begitu, gambar biasa!" Satu mempunyai rasa, intuisi, dan yang lain tidak. Profesor Ortodoks St. Tikhon universiti kemanusiaan Vladimir Nikolaevich Katasonov, Doktor Falsafah, seorang ahli matematik dengan pendidikan pertama, berkata: "Tidak ada bukti dalam matematik yang mungkin tanpa intuisi: seorang ahli matematik mula-mula melihat gambar, dan kemudian merumuskan bukti."

Persoalan tentang keimanan seseorang sentiasa menjadi persoalan yang melangkaui penaakulan logik semata-mata. Bagaimana untuk menerangkan apa yang membawa anda kepada iman? Lelaki itu menjawab: Saya pergi ke kuil, berfikir, membaca ini dan itu, melihat keharmonian alam semesta; tetapi yang paling penting, saat yang paling luar biasa, di mana seseorang tiba-tiba menyedari bahawa dia telah menemui kehadiran Tuhan, tidak dapat diungkapkan. Ia sentiasa menjadi rahsia.

- Anda boleh mengenal pasti masalah yang tidak dapat diselesaikan sains moden?

— Walau bagaimanapun, sains adalah perusahaan yang cukup yakin, bebas dan mantap untuk bercakap dengan begitu tajam. Ia adalah alat yang baik dan sangat berguna di tangan manusia. Sejak zaman Francis Bacon, ilmu sememangnya menjadi kuasa yang telah mengubah dunia. Sains berkembang mengikut undang-undang dalamannya: saintis berusaha untuk memahami undang-undang alam semesta, dan tidak ada keraguan bahawa pencarian ini akan membawa kepada kejayaan. Tetapi pada masa yang sama adalah perlu untuk menyedari had sains. Seseorang tidak seharusnya mengelirukan sains dengan persoalan ideologi yang boleh dibangkitkan berkaitan dengan sains. Isu Utama hari ini dikaitkan tidak begitu banyak dengan kaedah saintifik seperti dengan orientasi nilai. Sains pada abad ke-20 yang panjang dilihat oleh manusia sebagai kebaikan mutlak yang menyumbang kepada kemajuan umat manusia; dan kita melihat bahawa abad kedua puluh telah menjadi yang paling kejam dari segi korban manusia. Dan kemudian ada persoalan nilai. kemajuan sains, pengetahuan secara umum. Nilai etika tidak mengikut sains itu sendiri. Seorang saintis yang cemerlang boleh mencipta senjata untuk memusnahkan semua manusia, dan di sini timbul persoalan tanggungjawab moral seorang saintis, yang tidak dapat dijawab oleh sains. Sains tidak dapat menunjukkan kepada manusia makna dan tujuan kewujudannya. Sains tidak akan dapat menjawab persoalan mengapa kita berada di sini? Mengapakah alam semesta wujud? Soalan-soalan ini diselesaikan pada tahap pengetahuan yang berbeza, seperti falsafah dan agama.

— Selain daripada teorem Gödel, adakah bukti lain bahawa kaedah saintifik mempunyai hadnya? Adakah saintis sendiri mengenali ini?

- Sudah pada permulaan abad ke-20, ahli falsafah Bergson dan Husserl menunjuk kepada nilai relatif pengetahuan sains alam semula jadi. Ia kini telah menjadi kepercayaan hampir universal di kalangan ahli falsafah sains bahawa teori saintifik mewakili model hipotesis untuk menerangkan fenomena. Salah seorang pencipta mekanik kuantum Erwin Schrödinger berkata demikian zarah asas hanyalah imej, tetapi kita boleh melakukannya tanpa mereka. Menurut ahli falsafah dan ahli logik Karl Popper, teori saintifik adalah seperti jaring di mana kita cuba menangkap dunia, ia bukan seperti gambar. teori saintifik berada dalam pembangunan dan perubahan yang berterusan. Pencipta mekanik kuantum, seperti Pauli, Bohr, Heisenberg bercakap tentang had kaedah saintifik. Pauli menulis: “...Fizik dan jiwa boleh dianggap sebagai aspek tambahan realiti yang sama" - dan menumpukan pada ketidakupayaan peringkat yang lebih tinggi berada di bawah. Pelbagai penjelasan merangkumi hanya satu aspek perkara setiap kali, tetapi teori yang komprehensif tidak akan dapat dicapai.

Keindahan dan keharmonian alam semesta membayangkan kemungkinan pengetahuannya kaedah saintifik. Pada masa yang sama, orang Kristian sentiasa memahami ketidakfahaman misteri di sebalik alam semesta material ini. Alam semesta tidak mempunyai asas sendiri dan menunjuk kepada sumber makhluk yang sempurna - Tuhan.

Salah satu teorem logik matematik yang paling terkenal, bertuah dan malang pada masa yang sama. Dalam hal ini ia serupa dengan teori relativiti khas Einstein. Di satu pihak, hampir semua orang telah mendengar sesuatu tentang mereka. Sebaliknya, dalam tafsiran popular, teori Einstein, seperti yang anda tahu, "mengatakan segala sesuatu di dunia adalah relatif". Dan teorem ketidaklengkapan Gödel (selepas ini hanya TGN), dalam rumusan rakyat yang hampir sama bebas, "membuktikan bahawa ada perkara yang tidak dapat difahami oleh akal manusia". Oleh itu, sesetengah cuba menyesuaikannya sebagai hujah menentang materialisme, sementara yang lain, sebaliknya, membuktikan dengan bantuannya bahawa tidak ada tuhan. Sungguh melucukan bukan sahaja kedua-dua belah pihak tidak boleh betul pada masa yang sama, tetapi juga tidak seorang pun atau yang lain mengganggu untuk memikirkan apa, sebenarnya, teorem ini katakan.

Logik matematik sememangnya sains yang agak rumit, dan yang paling penting, tidak begitu biasa. Ia memerlukan gerakan yang berhati-hati dan ketat, di mana ia adalah penting untuk tidak mengelirukan yang benar-benar terbukti dengan fakta bahawa "ia sudah jelas." Walau bagaimanapun, saya berharap untuk memahami "garis besar pembuktian TGN" berikut, pembaca hanya memerlukan pengetahuan matematik sekolah / sains komputer, kemahiran berfikir logik dan masa 15-20 minit.

Memudahkan sedikit, TGN menegaskan bahawa dalam bahasa yang cukup kompleks terdapat cadangan yang tidak dapat dibuktikan. Tetapi dalam frasa ini, hampir setiap perkataan memerlukan penjelasan.

Peralihan dari satu formula ke formula lain berlaku mengikut peraturan tertentu yang terkenal. Peralihan dari formula ke-4 kepada formula ke-5 berlaku, katakan, kerana setiap nombor adalah sama dengan dirinya sendiri - itulah aksiom aritmetik. Dan keseluruhan prosedur untuk membuktikan, dengan itu, menterjemahkan formula ke dalam nilai boolean BENAR. Hasilnya boleh jadi PALSU - jika kita menafikan beberapa formula. Dalam kes ini, kami akan membuktikan penafiannya. Adalah mungkin untuk membayangkan program (dan program sedemikian sebenarnya ditulis) yang akan membuktikan cadangan tersebut (dan lebih kompleks) tanpa campur tangan manusia.

Untuk apa yang berikut, kita memerlukan tanggapan algoritma. Saya tidak akan memberikan takrif formalnya di sini - ini akan membawa kita jauh ke tepi. Saya akan menghadkan diri saya kepada perkara tidak formal: "algoritma"- urutan arahan yang tidak jelas ini ("program"), yang dalam bilangan langkah yang terhad menukar data input kepada output. Huruf condong pada asasnya penting - jika program digantung pada beberapa data awal, maka ia tidak menerangkan algoritma. Untuk kesederhanaan dan dalam aplikasi kes kami, pembaca boleh menganggap bahawa algoritma ialah program yang ditulis dalam mana-mana bahasa pengaturcaraan yang diketahuinya, yang, untuk sebarang data input dari kelas tertentu, dijamin untuk menyelesaikan kerjanya dengan hasil Boolean.

Mungkin kenyataan ini akan menyebabkan anda protes dalaman. Ini disebabkan oleh beberapa keadaan. Pertama, apabila kita diajar matematik sekolah, kadang-kadang terdapat tanggapan yang salah bahawa frasa "teorem adalah benar" dan "mungkin untuk membuktikan atau mengesahkan teorem" adalah hampir sama. Tetapi jika anda fikirkan, ia sama sekali tidak jelas. Sesetengah teorem dibuktikan dengan agak mudah (contohnya, dengan penghitungan sebilangan kecil pilihan), dan ada yang sangat sukar. Pertimbangkan, sebagai contoh, Teorem Terakhir Fermat yang terkenal:

Saya juga ambil perhatian bahawa jika kita bercakap tentang fungsi biasa yang memetakan set nombor nyata ke dalamnya, maka "tidak boleh dikira" fungsi itu tidak akan mengejutkan sesiapa pun (hanya jangan mengelirukan "fungsi boleh dikira" dan "nombor boleh dikira" - ini adalah perkara yang berbeza). Mana-mana murid sekolah tahu bahawa, katakan, dalam kes fungsi, anda mesti sangat bertuah dengan hujah supaya proses mengira perwakilan perpuluhan tepat bagi nilai fungsi ini berakhir dengan bilangan langkah yang terhad. Dan kemungkinan besar anda akan mengiranya menggunakan siri tak terhingga, dan pengiraan ini tidak akan membawa kepada hasil yang tepat, walaupun ia boleh datang sehampir yang anda suka - hanya kerana nilai sinus kebanyakan hujah adalah tidak rasional. TGN hanya memberitahu kita bahawa walaupun di antara fungsi yang hujahnya adalah rentetan dan nilainya adalah sifar atau satu, fungsi tidak boleh dikira, walaupun disusun dalam cara yang sama sekali berbeza, juga wujud.

Untuk perkara berikut, kami akan menerangkan "bahasa aritmetik formal". Pertimbangkan kelas rentetan teks dengan panjang terhingga, yang terdiri daripada angka Arab, pembolehubah (huruf abjad Latin) yang mengambil nilai semula jadi, ruang, tanda operasi aritmetik, kesamaan dan ketaksamaan, pengkuantiti ("wujud") dan ("untuk sebarang" ) dan, mungkin, beberapa simbol lain (nombor dan komposisi tepatnya tidak penting bagi kami). Adalah jelas bahawa tidak semua baris sedemikian bermakna (contohnya, "" adalah karut). Subset ungkapan bermakna daripada kelas ini (iaitu, rentetan yang benar atau salah dari segi aritmetik biasa) akan menjadi set pernyataan kami.

Contoh pernyataan aritmetik formal:

dan lain-lain. Sekarang mari kita panggil "formula dengan parameter percuma" (FSP) rentetan yang menjadi pernyataan jika nombor asli digantikan ke dalamnya sebagai parameter ini. Contoh FSP (dengan parameter):

dan lain-lain. Dalam erti kata lain, FSP adalah bersamaan dengan fungsi hujah semula jadi dengan nilai Boolean.

Mari kita beralih kepada lakaran bukti TGN dalam rumusan berikut:

Untuk bahasa proposisi aritmetik formal, tiada potongan konsisten yang lengkap.

Kami akan membuktikan dengan percanggahan.

Jadi mari kita anggap bahawa deduktif sedemikian wujud. Mari kita terangkan algoritma tambahan berikut yang memberikan nilai boolean kepada nombor asli seperti berikut:

Ringkasnya, algoritma menghasilkan nilai TRUE jika dan hanya jika hasil penggantian ke dalam FSP nombornya sendiri dalam senarai kami memberikan pernyataan palsu.

Di sini kita datang ke satu-satunya tempat di mana saya akan meminta pembaca untuk mengambil kata-kata saya untuk itu.

Jelas sekali, di bawah andaian di atas, mana-mana FSP daripada boleh dikaitkan dengan algoritma yang mengandungi nombor asli pada input dan nilai Boolean pada output. Kurang jelas adalah sebaliknya:

Selepas melepasi tempat licin ini, kami cepat sampai ke penghujung.

Lakaran bukti yang diberikan adalah untuk aritmetik formal, tetapi tidak sukar untuk melihat bahawa THN juga digunakan untuk banyak bahasa proposisi yang lain. Sudah tentu, tidak semua bahasa seperti itu. Sebagai contoh, mari kita tentukan bahasa seperti ini:

"Sebarang frasa dalam bahasa Cina adalah pernyataan yang benar jika ia terkandung dalam buku petikan Komrad Mao Tse Tung, dan tidak betul jika ia tidak terkandung."

Kemudian algoritma pembuktian lengkap dan konsisten yang sepadan (ia boleh dipanggil "deduktif dogmatik") kelihatan seperti ini:

“Selak buku petikan Komrad Mao Tse Tung sehingga anda menemui kenyataan yang anda cari. Jika didapati, maka ia adalah benar, dan jika buku petikan itu habis, dan kenyataan itu tidak dijumpai, maka ia adalah palsu.

Tag: Tambah tag

Mana-mana sistem aksiom matematik, bermula dari tahap kerumitan tertentu, adalah sama ada secara dalaman tidak konsisten atau tidak lengkap.

Pada tahun 1900, Persidangan Ahli Matematik Sedunia telah diadakan di Paris, di mana David Hilbert (1862-1943) membentangkan dalam bentuk abstrak 23 yang paling penting, pada pendapatnya, masalah yang dirumuskan olehnya, yang akan diselesaikan oleh saintis teori. abad kedua puluh yang akan datang. Nombor dua dalam senarainya adalah salah satu daripadanya tugasan mudah, jawapan yang kelihatan jelas sehingga anda menggali sedikit lebih dalam. bercakap bahasa moden, itulah persoalannya: adakah matematik mencukupi dengan sendirinya? Masalah kedua Hilbert adalah untuk membuktikan dengan teliti bahawa sistem itu aksiom- pernyataan asas yang diambil dalam matematik sebagai asas tanpa bukti - adalah sempurna dan lengkap, iaitu, ia membolehkan anda menerangkan secara matematik semua yang wujud. Adalah perlu untuk membuktikan bahawa adalah mungkin untuk menetapkan sistem aksiom sedemikian yang, pertama, mereka akan saling konsisten, dan kedua, seseorang boleh membuat kesimpulan daripada mereka mengenai kebenaran atau kepalsuan mana-mana pernyataan.

Mari kita ambil contoh dari geometri sekolah. Standard Planimetri Euclidean(geometri pada satah) adalah mungkin untuk membuktikan tanpa syarat bahawa pernyataan "jumlah sudut segitiga ialah 180°" adalah benar, dan pernyataan "jumlah sudut segitiga ialah 137°" adalah palsu. Secara asasnya, dalam geometri Euclidean, sebarang pernyataan adalah salah atau benar, dan yang ketiga tidak diberikan. Dan pada permulaan abad kedua puluh, ahli matematik secara naif percaya bahawa keadaan yang sama harus diperhatikan dalam mana-mana sistem yang konsisten secara logik.

Dan kemudian pada tahun 1931, beberapa ahli matematik berkaca mata Wina, Kurt Godel mengambil dan menerbitkan artikel pendek yang hanya membalikkan seluruh dunia yang dipanggil "logik matematik". Selepas mukadimah matematik dan teori yang panjang dan kompleks, beliau benar-benar mewujudkan perkara berikut. Mari kita ambil mana-mana pernyataan seperti: "Andaian #247 secara logiknya tidak boleh dibuktikan dalam sistem aksiom ini" dan panggilnya "pernyataan A". Jadi Gödel hanya membuktikan harta yang menakjubkan berikut mana-mana sistem aksiom:

"Jika pernyataan A boleh dibuktikan, maka pernyataan bukan A boleh dibuktikan."

Dalam erti kata lain, jika boleh untuk membuktikan kesahihan pernyataan "Andaian 247 bukan boleh dibuktikan", maka adalah mungkin untuk membuktikan kesahihan pernyataan "Andaian 247 terbukti". Iaitu, kembali kepada perumusan masalah Hilbert kedua, jika sistem aksiom lengkap (iaitu, sebarang pernyataan di dalamnya boleh dibuktikan), maka ia tidak konsisten.

Satu-satunya jalan keluar dari situasi ini ialah menerima sistem aksiom yang tidak lengkap. Iaitu, seseorang itu perlu bersabar dengan hakikat bahawa dalam konteks mana-mana sistem logik kita akan ditinggalkan dengan pernyataan "jenis A" yang diketahui benar atau salah - dan kita hanya boleh menilai kebenarannya luar rangka kerja aksiomatik yang telah kami pakai. Jika tidak ada pernyataan sedemikian, maka aksiomatik kami adalah bercanggah, dan dalam rangka kerjanya pasti akan ada formulasi yang boleh dibuktikan dan disangkal.

Jadi perkataan pertama, atau lemah Teorem ketidaklengkapan Gödel: "Mana-mana sistem formal aksiom mengandungi andaian yang tidak dapat diselesaikan." Tetapi Gödel tidak berhenti di situ, merumus dan membuktikan kedua, atau kuat Teorem ketidaklengkapan Godel: “Kesempurnaan logik (atau ketidaklengkapan) mana-mana sistem aksiom tidak boleh dibuktikan dalam rangka kerja sistem ini. Untuk membuktikan atau menyangkalnya, aksiom tambahan (penguatan sistem) diperlukan."

Adalah lebih selamat untuk berfikir bahawa teorem Godel adalah abstrak dan tidak membimbangkan kita, tetapi hanya bidang logik matematik yang luhur, tetapi sebenarnya ternyata ia berkaitan secara langsung dengan struktur otak manusia. ahli matematik Inggeris dan ahli fizik Roger Penrose (b. 1931) menunjukkan bahawa teorem Gödel boleh digunakan untuk membuktikan perbezaan asas antara otak manusia dan komputer. Maksud hujah beliau mudah sahaja. Komputer beroperasi secara logik dan tidak dapat menentukan sama ada pernyataan A adalah benar atau palsu jika ia melampaui skop aksiomatik, dan pernyataan sedemikian, menurut teorem Gödel, pasti wujud. Seseorang, berhadapan dengan pernyataan A yang tidak dapat dibuktikan secara logik dan tidak dapat disangkal, sentiasa dapat menentukan kebenaran atau kepalsuannya - berdasarkan pengalaman seharian. Sekurang-kurangnya dalam ini otak manusia mengatasi komputer yang dibelenggu dengan bersih litar logik. Otak manusia mampu memahami kedalaman penuh kebenaran yang terkandung dalam teorem Gödel, tetapi komputer tidak boleh. Oleh itu, otak manusia hanyalah sebuah komputer. Dia mampu untuk membuat keputusan, dan ujian Turing akan lulus.

Saya tertanya-tanya sama ada Hilbert tahu sejauh mana soalannya akan membawa kita?

Kurt Godel, 1906-78

Austria, kemudian ahli matematik Amerika. Dilahirkan di Brünn (Brünn, kini Brno, Republik Czech). Dia lulus dari Universiti Vienna, di mana dia kekal sebagai guru di Jabatan Matematik (sejak 1930 - seorang profesor). Pada tahun 1931 beliau menerbitkan teorem yang kemudiannya menerima namanya. Sebagai seorang yang tidak berpolitik semata-mata, dia sangat sukar terselamat daripada pembunuhan rakannya dan pekerja jabatan oleh pelajar Nazi dan jatuh ke dalam kemurungan yang mendalam, yang berulang menghantuinya sehingga akhir hayatnya. Pada tahun 1930-an, dia berhijrah ke Amerika Syarikat, tetapi kembali ke Austria asalnya dan berkahwin. Pada tahun 1940, pada kemuncak perang, dia terpaksa melarikan diri ke Amerika dalam transit melalui USSR dan Jepun. Bekerja sebentar di Princeton Institute penyelidikan lanjutan. Malangnya, jiwa saintis tidak dapat menahannya, dan dia mati kelaparan di klinik psikiatri, enggan makan, kerana dia yakin bahawa mereka berniat untuk meracuninya.