Apakah Edward Nelson menerima teorema ketidaklengkapan?
Edward Nelson menganjurkan versi lemah aritmatika (disebut aritmatika predikatif) yang tidak dapat membuktikan totalitas eksponensial. Karena teorinya memperluas aritmatika Robinson, teorema ketidaklengkapan berlaku untuk itu. Tetapi jika teorema ketidaklengkapan terbukti dalam teori yang lebih kuat dari yang dia terima, dia mungkin bisa menolaknya. Jadi pertanyaan saya adalah pertama, apakah Nelson meragukan salah satu teorema ketidaklengkapan? Dan kedua, dapatkah teorema ketidaklengkapan dibuktikan dalam sistem aritmatika yang lemah yang tidak membuktikan totalitas eksponensial?
Hal terdekat yang dapat saya temukan untuk sebuah jawaban adalah kutipan dari bukunya Predicative Arithmetic, di mana dia mengatakan pada halaman 81 "setidaknya satu dari dua pilar logika matematika finiter ini, Teorema Konsistensi Hilbert-Ackermann dan Teorema Kedua Gödel, membuat banding ke konsep impredikatif. "
Jawaban
Teorema ketidaklengkapan kedua Gödel tidak memerlukan eksponen atau "konsep impredikatif". Sistem tempat Nelson bekerja adalah fragmen aritmatika yang dapat ditafsirkan pada potongan yang dapat ditentukan$Q$; salah satu fragmen tersebut adalah aritmatika terbatas$I\Delta_0+\Omega_1$ (Tampaknya inilah yang disebut Nelson $Q_4$dalam buku aritmatika Predikatif ). Teori$I\Delta_0+\Omega_1$ (dan bahkan fragmen lemah dengan induksi yang lebih terbatas, seperti $PV_1$) sangat mampu membuktikan teorema ketidaklengkapan kedua (untuk teori dengan himpunan aksioma waktu-polinom, yang bukan merupakan kendala nyata).
( EDIT: Saya telah menulis ulang jawaban ini secara substansial berdasarkan apa yang telah saya pelajari dari Emil Jeřábek dan dari membaca beberapa referensi yang relevan dengan lebih cermat.)
Seperti yang dikatakan Emil Jeřábek, jawaban singkat untuk pertanyaan kedua Anda adalah ya, tetapi ada beberapa hal yang perlu diperhatikan.
Pertama-tama, mungkin tidak segera jelas bahkan bagaimana menyatakan teorema ketidaklengkapan Gödel dalam sistem yang lemah, apalagi membuktikannya, karena pernyataan biasa mengukur lebih dari set aksioma yang dapat dihitung. Seperangkat aksioma yang aksioma dapat diputuskan hanya dengan perhitungan yang sangat mahal akan sulit untuk dibicarakan secara bermakna dalam sistem yang sangat lemah. Kita dapat menghindari masalah ini dengan membatasi perhatian pada himpunan aksioma yang "jinak", karena hal itu mencakup semua himpunan aksioma yang merupakan kepentingan praktis dalam dasar matematika. Bahkan dengan pembatasan ini, terdapat kesulitan teknis dengan mengkuantifikasi himpunan aksioma, tetapi kita juga dapat mengelak dari hal itu dengan membicarakan skema teorema ketidaklengkapan ; yaitu, untuk setiap kumpulan aksioma yang menarik, kami menuliskan rumus aritmatika (terikat) untuk mengekspresikan aksioma, dan kami memiliki contoh terpisah dari skema teorema ketidaklengkapan untuk setiap rumus tersebut.
Kesulitan kedua adalah bahwa untuk sistem yang sangat lemah, muncul pertanyaan apakah teorema ketidaklengkapan berarti apa yang kita inginkan. Misalnya, Bezboruah dan Shepherdson membuktikan teorema ketidaklengkapan kedua Gödel untuk Q , di mana Q adalah aritmatika Robinson. Tetapi Q sangat lemah sehingga ia bahkan tidak dapat memformalkan properti dasar sintaks dengan benar, sehingga fakta bahwa Q tidak membuktikan Con ( Q ) tidak berarti banyak.
Namun, di sisi positifnya, eksponen tidak diperlukan untuk aritmetisasi sintaks. Misalnya, dalam gelar Ph.D. Skripsi Aritmatika Terikat , Samuel Buss melakukan aritmetisasi sintaksis secara detail menggunakan sistem lemah yang disebut$S^1_2$, dan membuktikan versi teorema ketidaklengkapan kedua Gödel untuk $S^1_2$. (Memang, buku Nelson sendiri menunjukkan bagaimana menghitung sintaks dasar menggunakan sistem "aritmatika predikatif" miliknya sendiri.)
Bukti Buss masih belum cukup menjawab pertanyaan Anda seperti yang diajukan, karena Anda tidak hanya ingin tahu apakah teorema ketidaklengkapan berlaku untuk sistem yang lemah; Anda bertanya apakah bukti teorema ketidaklengkapan dapat diformalkan dalam sistem yang tidak membuktikan bahwa eksponen adalah fungsi total. Poin ini membingungkan saya untuk sementara waktu karena bukti Buss sebenarnya menarik bagi teorema cut-elimination Gentzen, yang tidak dapat dibuktikan dalam aritmatika terbatas. Namun, seperti yang ditunjukkan oleh Emil Jeřábek, ini karena Buss membuktikan versi yang lebih kuat dari teorema ketidaklengkapan kedua daripada biasanya. Jika kita mempertimbangkan teorema ketidaklengkapan yang biasa maka seorang ahli dapat melihat "dengan pemeriksaan" bahwa bukti tersebut tidak melebihi kemampuan aritmatika terbatas.
Saya masih belum melihat pernyataan eksplisit dalam literatur bahwa teorema ketidaklengkapan dapat dibuktikan dalam aritmatika terbatas; ini sepertinya adalah "cerita rakyat". Ini adalah hasil di area yang disebut matematika terbalik terbatas . Satu buku yang secara eksplisit mengejar program matematika terbalik yang dibatasi adalah Logical Foundations of Proof Complexity oleh Stephen Cook dan Phuong Nguyen, tetapi mereka tidak membuktikan teorema ketidaklengkapan. Buku lain yang membahas teorema ketidaklengkapan untuk sistem yang lemah adalah Metamathematics of First-Order Arithmetic oleh Pavel Pudlák dan Petr Hájek, tetapi saya juga tidak dapat menemukan pernyataan eksplisit di sana.
( EDIT: Saya bertanya di milis Foundations of Mathematics untuk referensi yang diterbitkan, dan Richard Heck menunjuk saya ke Pada skema induksi untuk rumus aritmatika terbatas oleh AJ Wilkie dan JB Paris, Ann. Pure Appl. Logic 35 (1987), 261–302. Makalah ini memberikan bukti yang cukup rinci bahwa teorema ketidaklengkapan dapat dibuktikan berdasarkan sistem$I\Delta_0 + \Omega_1$ untuk aritmatika terbatas.)
Sekarang untuk beberapa komentar tentang pertanyaan pertama Anda. Penting untuk disadari bahwa tidak selalu mudah untuk memastikan dengan tepat apa yang diyakini Nelson, bahkan ketika dia masih hidup. Bahkan sistem aritmatika yang lemah mengakui angka yang besar secara sembarangan, tetapi Nelson mengatakan hal-hal yang menunjukkan bahwa dia curiga terhadap angka yang sebenarnya tidak dapat dituliskan dalam satu kesatuan. Menindaklanjuti komentar dalam bukunya Predicative Arithmetic tentang bilangan$80^{5000}$, Saya pernah bertanya kepada Nelson tentang nomor tersebut$80\cdot 80 \cdots 80$ di mana kami menulis secara eksplisit $5000$ salinan $80$. Dia skeptis bahwa ini adalah angka yang sebenarnya, meskipun faktanya tidak ada eksponen yang terlibat. Dalam keadaan seperti itu, saya bahkan tidak yakin apakah Nelson mempercayai hal itu$\sqrt{2}$tidak rasional dalam arti yang sama seperti Anda dan saya percaya itu. Jika Nelson dan saya akan membahas bukti tersebut bersama-sama, maka tentu saja dia akan setuju bahwa setiap langkah dari bukti itu secara formal benar, tetapi apa kesimpulan dari bukti tersebut “katakan”? Anda dan saya pikir itu mengatakan sesuatu tentang bilangan alami besar yang sewenang-wenang tetapi Nelson mungkin tidak. Dan jika dia tidak melakukannya, mengapa dia bahkan harus percaya bahwa ketepatan urutan pendek manipulasi formal harus memberi tahu kita tentang (misalnya) apakah komputer mencari bilangan bulat positif$a$ dan $b$ seperti yang $a^2 = 2b^2$akan berhasil atau gagal? Singkatnya, menurut saya tidak ada gunanya mencoba memahami dengan tepat apa yang diyakini atau diragukan Nelson secara pribadi, karena dia tidak memberikan penjelasan yang cukup rinci dan koheren tentang keyakinan tersebut.
Ada diskusi menarik tentang “predikativisme” Nelson dalam makalah Interpretability di Robinson's Q , oleh Fernando Ferreira dan Gilda Ferreira. Apa Nelson tampaknya berdebat di predikatif aritmatika adalah bahwa kita tidak harus menganggap pernyataan matematis yang berarti kecuali dapat ditafsirkan dalam Q . Ferreira dan Ferreira menunjukkan bahwa telah ditunjukkan (oleh Wilkie) totalitas eksponen tidak dapat diinterpretasikan dalam Q , sedangkan negasi dari totalitas eksponen dapat ditafsirkan dalam Q (yang terakhir adalah hasil dari Solovay). Ini tampaknya membenarkan pandangan Nelson bahwa eksponensiasi menghadirkan "penghalang yang tidak bisa dilewati" bagi ahli predikatif yang berkomitmen. Di sisi lain, Ferreira dan Ferreira juga mengemukakan argumen bahwa pandangan Nelson menderita "ketidakstabilan" tertentu, karena misalnya tidak ditutup dalam pengambilan konjungsi. Saya merujuk pembaca ke makalah mereka untuk diskusi yang lebih detail. Dalam hal apapun, akan terlihat bahwa kondisi yang diperlukan untuk Nelson menerima teorema ketidaklengkapan akan bahwa mereka diinterpretasi di Q . Saya kira ini benar, tetapi sekali lagi saya tidak tahu tentang referensi eksplisit.
Pertanyaan kedua Anda telah dijawab dengan baik oleh Emil Jerabek, menurut saya. Membaca beberapa komentar, saya merasa saya harus menulis yang berikut tentang pertanyaan pertama Anda:
Dari berbicara dengan Ed Nelson dan kepada orang-orang yang mengenalnya dengan baik, saya dapat mengatakan bahwa Ed Nelson telah lama diyakinkan bahwa fungsi eksponensial entah bagaimana mengarah pada inkonsistensi (dan karenanya PA tidak konsisten). Dia telah menulis tentang hal ini panjang lebar dan telah menunjukkan beberapa motivasi untuk pandangan ini, seperti karakterisasi kompleksitas fungsi Bellantoni-Cook dan tulisannya tentang predikatif.
Motivasi Ed Nelson yang lebih dalam untuk pandangannya tampaknya adalah sebagai berikut: dia merasa bahwa konstruksi titik tetap (seperti enumerasi semua fungsi rekursif parsial atau teorema ketidaklengkapan Goedel) dapat 'diinternalisasi' atau 'dibuat total' untuk menghasilkan kontradiksi seperti '0 = 1'. Kontradiksi seperti itu hanya mungkin terjadi dengan fungsi eksponensial. Pada tingkat yang paling mendasar, Ed Nelson tidak percaya bahwa gagasan set infinite selesai secara formal konsisten.