Brouwer menolak formalisme, namun mengakui kegunaan potensial untuk merumuskan prinsip-prinsip logika umum yang mengekspresikan konstruksi intuisi yang benar, seperti modus ponens . Sistem formal untuk intuisi proposisional dan predikat logika dan aritmatika dikembangkan oleh Heyting [1930], Gentzen [1935] dan Kleene [1952]. Gödel [1933] membuktikan kesamaan teori intuisi dan klasik. Kripke [1965] memberikan semantik yang dengannya logika intuisi benar dan lengkap.
1. Penolakan Tertium Non Datur
Logika intuisiistik dapat secara ringkas digambarkan sebagai logika klasik tanpa hukum Aristoteles yang tidak diikutkan dalam bahasa tengah (LEM): ( A ∨ ¬ A ) atau hukum klasik eliminasi negasi ganda (¬ ¬ A → A ), namun dengan hukum kontradiksi ( A → B ) → (( A → ¬ B ) → ¬ A ) dan ex falso quodlibet : (¬ A → ( A → B )). Brouwer [1908] mengamati bahwa LEM diabstraksikan dari situasi yang terbatas, kemudian diperluas tanpa pembenaran terhadap pernyataan tentang koleksi tak terbatas. Sebagai contoh, misalkan x , y berkisar bilangan natural 0, 1, 2, ... dan B ( x ) menyingkat properti yang dinyatakan oleh klaim berikut dimana variabel x bebas: ada y yang lebih besar dari x sehingga keduanya y dan y + 2 adalah bilangan prima, yaitu,
∃ y ( y > x & Prime ( y ) & Prime ( y +2))
Kemudian kita tidak memiliki metode umum untuk menentukan apakah B ( x ) benar atau salah untuk x yang sewenang-wenang, jadi ∀ x ( B ( x ) ∨ ¬ B ( x )) tidak dapat dinyatakan dalam keadaan pengetahuan kita saat ini. Dan jika A menyingkat pernyataan ∀ x B ( x ), maka ( A ∨ ¬ A ) tidak dapat ditegaskan karena tidak ada A atau (¬ A ) yang belum terbukti.
Orang mungkin keberatan bahwa contoh-contoh ini bergantung pada fakta bahwa dugaan Twin Primes belum diselesaikan. Sejumlah contoh "contoh palsu" Brouwer bergantung pada masalah (seperti Teorema Terakhir Fermat) yang telah dipecahkan. Tetapi kepada Brouwer, LEM umum setara dengan asumsi apriori bahwa setiap masalah matematika memiliki sebuah solusi - sebuah asumsi yang ditolaknya, mengantisipasi teorema ketidaklengkapan Gödel pada seperempat abad.
Penolakan LEM memiliki konsekuensi luas. Di tangan satunya,
- Intuitionistically, Reductio ad absurdum hanya membuktikan pernyataan negatif , karena ¬ ¬ A → A tidak berlaku pada umumnya. (Jika ya, LEM akan mengikuti mode ponens dari yang bisa dibuktikan secara intuisi ( A ∨ ¬ A ).)
- Tidak setiap formula proposisional memiliki bentuk normal yang tidak beraturan atau konjungtif yang intuisi.
- Tidak semua formula predikat memiliki bentuk preneks yang intuisi secara ekuivalen.
- Sementara ∀ x ¬ ¬ ( A ( x ) ∨ ¬ A ( x )) adalah teorema logika predikat intuisi, ¬ ¬ ∀ x ( A ( x ) ∨ ¬ A ( x )) tidak.
- Logika intuisi intuitif secara otomatis tidak lengkap. Ekstensi aksiomatik yang tak terbatas dari logika proposisional dan predikat intuisi sangat terkandung dalam logika klasik.
- Setiap bukti intuisi tentang pernyataan tertutup dari bentuk A ∨ B dapat diubah secara efektif menjadi bukti intuitif dari A atau bukti intuisi B , dan juga untuk pernyataan tertutup eksistensial.
- Logika klasik diacak secara finitatif di fragmen negatif logika intuisi.
- Rumus aritmatika memiliki bentuk normal intuisi yang relatif sederhana.
- Intuisiistik aritmatika secara konsisten dapat diperluas oleh aksioma (seperti Tesis Gereja) yang bertentangan dengan aritmatika klasik, yang memungkinkan pembelajaran formal matematika rekursif.
- Analisis intuisiistik kontroversial Brouwer, yang bertentangan dengan LEM, dapat diformalkan dan ditunjukkan secara konsisten berkaitan dengan subordori klasik dan intuisi yang benar.
Logika intuisi yang diformalkan secara alami didorong oleh penjelasan Brouwer-Heyting-Kolmogorov tentang kebenaran intuisi yang sebenarnya, yang digariskan di Bagian 3.1 dari masuknya intuisiisme dalam filsafat matematika dan dibahas secara ekstensif dalam masuknya pengembangan logika intuisi . Independensi konstruktif operasi logis &, ∨, →, ¬, ∀, ∃ kontras dengan situasi klasik, di mana misalnya, ( A ∨ B ) setara dengan ¬ (¬ A & ¬ B ), dan ∃ x A ( x ) setara dengan ¬ ∀ x ¬ A ( x ). Dari sudut pandang BHK, sebuah kalimat dari bentuk ( A ∨ B ) menegaskan bahwa baik bukti A , atau bukti B , telah dibangun; sementara ¬ (¬ A & ¬ B ) menegaskan bahwa algoritma telah dibangun yang secara efektif akan mengubah setiap konstruksi yang membuktikan ¬ A dan ¬ B masing-masing, menjadi bukti kontradiksi yang diketahui.
Berikut ini adalah formalisme gaya Hilbert H , dari Kleene [1952], untuk logika prediktor urutan intuisi orisinil IQC . Bahasa L memiliki huruf prediktif P , Q (.), ... dari semua aras dan variabel individual a , b , c , ... (dengan atau tanpa subskrip 1,2, ...), serta simbol &, ∨, →, ¬ , ∀, ∃ untuk penghubung logis dan kuantifier, dan tanda kurung (,). Rumus utama dari L adalah ungkapan seperti P , Q ( a ), R ( a , b , a ) di mana P , Q (.), R (...) adalah huruf predikat 0-ary, 1-ary dan 3-ary masing; Artinya, hasil pengisian setiap huruf kosong dalam sebuah huruf predikat oleh simbol variabel individual adalah formula utama. Rumus L (yang terbentuk dengan baik) didefinisikan secara induktif sebagai berikut.
- Setiap formula utama adalah formula .
- Jika A dan B adalah formula , maka ( A & B ), ( A ∨ B ), ( A → B ) dan ¬ A.
- Jika A adalah formula dan x adalah sebuah variabel, maka ∀ x A dan ∃ x A adalah formula .
Ada tiga aturan inferensi:
- Modus Ponens : Dari A dan ( A → B ), simpulkan B.
- ∀-Pendahuluan : Dari ( C → A ( x )), di mana x adalah variabel yang tidak terjadi bebas di C , simpulkan ( C → ∀ x A ( x )).
- ∃-Eliminasi : Dari ( A ( x ) → C ), di mana x adalah variabel yang tidak terjadi bebas di C , simpulkan (∃ x A ( x ) → C ).
- A → ( B → A ).
- ( A → B ) → (( A → ( B → C )) → ( A → C )).
- A → ( B → A & B ).
- A & B → A.
- A & B → B.
- A → A ∨ B.
- B → A ∨ B.
- ( A → C ) → (( B → C ) → ( A ∨ B → C )).
- ( A → B ) → (( A → ¬ B ) → ¬ A ).
- ¬ A → ( A → B ).
- ∀ x A ( x ) → A ( t ).
- A ( t ) → ∃ x A ( x ).
Intuitionistic propositional logic IPC adalah subial yang menghasilkan ketika bahasa dibatasi pada formula yang dibuat dari huruf proposisi P , Q , R , ... menggunakan penghubung proposisional,, ∨, → dan ¬, dan hanya postulat proposisional yang digunakan. Jadi dua aturan terakhir inferensi dan dua aksioma aksi terakhir tidak ada dalam teori proposisional.
Jika, dalam daftar skema aksioma yang diberikan untuk logika predikat proposisi atau orde pertama intuisi, hukum yang mengekspresikan quodlibet sequasing eks falso :
¬ A → ( A → B ).
digantikan oleh hukum klasik eliminasi negasi ganda:
¬ ¬ A → A.
(atau, ekuivalen, jika hukum pengantar negasi intuisi
( A → B ) → (( A → ¬ B ) → ¬ A )
digantikan oleh LEM), sebuah sistem formal untuk logika proporsional klasik CPC atau hasil prediksi klasik CQC . Karena hukum kontradiksi adalah teorema klasik, logika intuisi masuk akal dalam logika klasik. Dalam arti tertentu, logika klasik juga terkandung dalam logika intuisi; lihat Bagian 4.1 di bawah ini.
Penting untuk dicatat bahwa sementara LEM dan hukum negasi ganda setara dengan skema , implikasinya (¬ ¬ A → A ) → ( A ∨ ¬ A ) bukanlah skema teorema IPC . Untuk teori T berdasarkan logika intuisi, jika E adalah formula sewenang-wenang dari L ( T ) maka menurut definisinya
- E dapat dipecahkan dalam T jika dan hanya jika T membuktikan ( E ∨ ¬ E ).
- E stabil di T jika dan hanya jika T membuktikan (¬ ¬ E → E ).
- E dapat diuji dalam T jika dan hanya jika T membuktikan (¬ E ¬ ¬ ¬ E ).
Decidability menyiratkan stabilitas, tapi tidak sebaliknya. Konjungsi stabilitas dan kemampuan testis sama dengan decidability. Dengan teorema logis Brouwer yang pertama kali diterbitkan ¬ ¬ ¬ A → ¬ A , setiap formula berbentuk ¬ A stabil; tetapi dalam formula utama IPC dan IQC dan negasinya tidak dapat dipecahkan, seperti yang ditunjukkan pada Bagian 5.1 di bawah ini.
Sistem Hilbert-gaya H berguna untuk investigasi metamoral logika intuisi, namun penggolongan deduksi deduksi paksa dan preferensinya untuk aksioma di atas peraturan menjadikannya instrumen yang canggung untuk membangun kemampuan derivatif. Sistem deduksi alami I untuk hasil predikat intuisi intuitif dari sistem deduktif D , yang disajikan dalam Bagian 3 dari entri mengenai logika klasik dalam Ensiklopedia ini, dengan menghilangkan simbol dan aturan untuk identitas, dan mengganti aturan klasik (DNE) dari negasi ganda Penghapusan oleh aturan penghapusan negasi intuisi
(INE) Jika F mengandung A dan F berarti ¬ A , maka F mengandung B.
Sementara identitas tentu saja dapat ditambahkan ke logika intuisi, untuk aplikasi (misalnya, aritmatika) simbol persamaan umumnya diperlakukan sebagai predikat predikat yang memuaskan aksioma nonlogis (misalnya definisi primitif rekursif penambahan dan perkalian) selain refleksivitas, simetri dan transitivitas. Identitas bisa ditolak, intuisi dan klasik, tapi persamaan ekstensional intuisi tidak selalu bisa ditolak; lihat pembahasan aksioma kontinuitas Brouwer di Bagian 3 tentang masuknya intuisiisme dalam filsafat matematika . Kunci untuk membuktikan bahwa H adalah sama dengan saya adalah modus ponens dan kebalikannya
Teorema Deduksi : Jika B diturunkan dari A dan kemungkinan formula lainnya F , dengan semua variabel bebas dalam A yang dipertahankan konstan dalam derivasi (yaitu, tanpa menggunakan peraturan absensi kedua atau ketiga pada variabel x yang bebas dari A , kecuali jika Asumsi A tidak terjadi dalam derivasi sebelum kesimpulan yang dimaksud), maka ( A → B ) diturunkan dari F.
Hasil mendasar ini, yang secara kasar mengekspresikan peraturan (→ I ) dari I , dapat dibuktikan untuk H dengan induksi pada definisi derivasi. Aturan lain yang saya pegang untuk H dasarnya dengan modus ponens , yang sesuai dengan (→ E ) di I. Untuk mengilustrasikan kegunaan dari Teorema Pengurangan, pertimbangkan skema teorema (yang tampaknya sepele) ( A → A ) dari IPC . Bukti yang benar dalam H membutuhkan lima baris:
1. A → ( A → A )
2. ( A → ( A → A )) → (( A → (( A → A ) → A )) → ( A → A ))
3. ( A → (( A → A ) → A )) → ( A → A )
4. A → (( A → A ) → A )
5. A → A
dimana 1, 2 dan 4 adalah aksioma dan 3, 5 berasal dari garis-garis awal dengan modus ponens . Namun, A diturunkan dari A (sebagai asumsi) dalam satu langkah yang jelas, sehingga Teorema Pengurangan memungkinkan kita untuk menyimpulkan bahwa bukti ( A → A ) ada. (Sebenarnya, bukti resmi ( A → A ) yang baru disajikan adalah bagian dari bukti konstruktif Teorema Pengurangan!)
Penting untuk dicatat bahwa, dalam definisi derivasi dari asumsi dalam H , rumus asumsi diperlakukan seolah-olah semua variabel bebasnya diukur secara universal, sehingga ∀ x A ( x ) diturunkan dari hipotesis A ( x ) . Namun, variabel x akan bervariasi (tidak dipertahankan konstan) dalam derivasi tersebut, dengan menggunakan aturan ∀-pendahuluan; dan Teorema Pengurangan tidak dapat digunakan untuk menyimpulkan (salah) bahwa A ( x ) → ∀ x A ( x ) (dan karenanya, dengan ∃-eliminasi, ∃ x A ( x ) → ∀ x A ( x )) dapat dibuktikan di H. Sebagai contoh penggunaan yang benar dari Teorema Deduksi untuk logika predikat, pertimbangkan implikasinya ∃ x A ( x ) → ¬∀ x ¬ A ( x ). Untuk menunjukkan hal ini dapat dibuktikan dalam IQC , pertama-tama kita memperoleh ¬∀ x ¬ A ( x ) dari A ( x ) dengan semua variabel bebas yang dipegang konstan:
1. ∀ x ¬ A ( x ) → ¬ A ( x )
2. A ( x ) → (∀ x ¬ A ( x ) → A ( x ))
3. A ( x ) (asumsi)
4. ∀ x ¬ A ( x ) → A ( x )
5. (∀ x ¬ A ( x ) → A ( x )) → ((∀ x ¬ A ( x ) → ¬ A ( x )) → ¬∀ x ¬ A ( x ))
6. (∀ x ¬ A ( x ) → ¬ A ( x )) → ¬∀ x ¬ A ( x )
7. ¬∀ x ¬ A ( x )
Di sini 1, 2 dan 5 adalah aksioma; 4 berasal dari 2 dan 3 dengan modus ponens ; dan 6 dan 7 berasal dari garis awal dengan modus ponens ; jadi tidak ada variabel yang bervariasi. Teorema Pengurangan mengatakan bahwa ada bukti P dalam IQC ( A ( x ) → ¬∀x¬ A ( x )), dan satu penerapan eliminasi ∃ mengubah P menjadi bukti ∃ x A ( x ) → ¬ ∀ x ¬ A ( x ). Kebalikannya tidak dapat dibuktikan dalam IQC , seperti yang ditunjukkan pada Bagian 5.1 di bawah ini.
3. Teori Intuisiistik (Heyting Arithmetic)
Intuitionistic (Heyting) arithmetic HA dan klasik (Peano) aritmatika PA berbagi bahasa orde pertama yang sama dan aksioma non-logis yang sama; hanya logika yang berbeda. Selain penghubung logis, kuantifier dan tanda kurung dan variabel individu a , b , c , ... (dengan metavariabel x , y , z seperti biasa), bahasa L ( HA ) aritmatika memiliki simbol predikat biner =, konstanta individu 0, fungsi konstan konstan S , dan konstanta konstanta jauh lebih banyak atau tak terbatas banyak untuk fungsi rekursif primitif termasuk penambahan dan perkalian; Pilihan yang tepat adalah soal selera dan kenyamanan. Syarat dibuat dari variabel dan 0 menggunakan konstanta fungsi; Secara khusus, setiap bilangan natural n dinyatakan dalam bahasa dengan angka n yang diperoleh dengan menerapkan S n kali sampai 0 (misalnya, S ( S (0)) adalah angka untuk 2). Formula utama berbentuk ( s = t ) dimana s , t adalah istilah, dan formula senyawa diperoleh dari ini seperti biasa.
Aksioma logis dan aturan HA adalah orde intuisi intuitif prediktor logika IQC . Aksioma nonlogis mencakup sifat refleksif, simetris dan transitif dari persamaan persamaan definitif rekursif primitif untuk setiap fungsi konstan, aksioma yang mencirikan 0 sebagai bilangan paling alami dan S sebagai fungsi satu-satu:
∀ x ¬ ( S ( x ) = 0),
∀ x ∀ y ( S ( x ) = S ( y ) → x = y ),
aksioma ekuivalensi ekstensional untuk S:
∀ x ∀ y ( x = y → S ( x ) = S ( y )),
dan skema universal dari matematis induksi, untuk formula acak A ( x ):
A (0) & ∀ x ( A ( x ) → A ( S ( x ))) → ∀ x A ( x ).
Aksioma ekuivalen ekstensional untuk semua konstanta fungsi lainnya diturunkan oleh induksi matematis dari aksioma kesetaraan untuk S dan aksioma fungsi rekursif primitif.
Hubungan orde natural x < y dapat didefinisikan dalam HA dengan ∃ z ( S ( z ) + x = y ), atau dengan formula bebas kuantifier jika simbol dan menentukan aksioma untuk pengurangan potongan hadir dalam formalisme. HA membuktikan hukum komparatif
∀ x ∀ y ( x < y ∨ x = y ∨ y < x )
dan bentuk intuisi dari prinsip paling sedikit, untuk formula sewenang-wenang A ( x ):
∀ x [∀ y ( y < x → A ( y ) ∨ ¬ A ( y )) → ∃ y ( y < x & A ( y ) & ∀ z ( z < y → ¬ A ( z ))) ∨ ∀ y ( y < x → ¬ A ( y ))].
Hipotesis ini diperlukan karena tidak semua formula aritmatika dapat dipecahkan dalam HA . Namun, ∀ x ∀ y ( x = y ∨ ¬ ( x = y )) dapat dibuktikan secara langsung oleh induksi matematis, dan sebagainya.
Formula utama (dan karenanya semua formula bebas kuantifier ) dapat ditolak dan stabil dalam HA .
Jika A ( x ) dapat dipecahkan dalam HA , maka dengan induksi pada x, maka ∀ y ( y < x → A ( y )) dan ∃ y ( y < x & A ( y )). Karenanya
Rumus dimana semua quantifier dibatasi dan stabil dalam HA .
Pengumpulan Δ 0 dari rumus aritmatika di mana semua quantifier dibatasi adalah tingkat terendah dari hierarki aritmatika klasik berdasarkan pada pola alternasi quantifier dalam formula prenex. Dalam HA tidak setiap formula memiliki bentuk preneks, namun Burr [2004] menemukan hirarki aritmatika intuisi sederhana yang sesuai tingkatnya berdasarkan tingkat ke klasik. Untuk tujuan dua definisi berikutnya saja, ∀ x menunjukkan sebuah blok dari jumlah bilangan universal yang finitely banyak, dan sama halnya ∃ x menunjukkan sebuah blok dari jumlah bilangan primitif yang banyak. Dengan konvensi ini, kelas Burr Φ n dan Ψ n didefinisikan oleh
- Φ 0 = Ψ 0 = Δ 0 ,
- Φ 1 adalah kelas dari semua formula dari bentuk ∀ x A ( x ) di mana A ( x ) berada di Ψ 0 . Untuk n ≥ 2 , Φ n adalah kelas dari semua formula dari bentuk ∀ x [ A ( x ) → ∃ y B ( x, y )] di mana A ( x ) berada dalam Φ n-1 dan B ( x, y ) ada di Φ n-2 ,
- Ψ 1 adalah kelas dari semua formula dari bentuk ∃ x A ( x ) di mana A ( x ) berada di Φ 0 . Untuk n ≥ 2 , Ψ n adalah kelas dari semua formula dari bentuk A → B dimana A berada di Φ n dan B ada di Φ n-1 .
Kelas preneks klasik yang sesuai didefinisikan lebih sederhana:
- Π 0 = Σ 0 = Δ 0 ,
- Π n + 1 adalah kelas dari semua formula dari bentuk ∀ x A ( x ) di mana A ( x ) berada dalam Σ n ,
- Σ n + 1 adalah kelas dari semua formula dari bentuk ∃ x A ( x ) di mana A ( x ) berada dalam Π n .
Peano arithmetic PA berasal dari Heyting arithmetic HA dengan menambahkan LEM atau (¬ ¬ A → A ) ke daftar aksioma logis, yaitu dengan menggunakan logika klasik dan bukan intuisi. Hasil berikut terus berlanjut bahkan dalam fragmen HA dan PA dengan skema induksi yang dibatasi pada formula Δ 0 .
Teorema Burr :
- Setiap rumus aritmatika dapat dibuktikan setara dengan HA pada formula di salah satu kelas Φ n.
- Setiap formula dalam Φ n terbukti setara dengan PA dengan formula di Π n , dan sebaliknya.
- Setiap formula dalam Ψ n terbukti setara dengan PA dengan formula di Σ n , dan sebaliknya.
HA dan PA adalah bukti teoritis yang setara, seperti yang akan ditunjukkan pada Bagian 4. Masing-masing mampu (numeralwise) mengekspresikan predikat bukti sendiri. Dengan Teorema Ketidakkonsistenan Gödel yang terkenal, jika HA konsisten, maka HA maupun PA tidak dapat membuktikan konsistensinya sendiri.
4. Teori Bukti Dasar
4.1 Menerjemahkan klasik ke dalam logika intuisi
Fakta mendasar tentang logika intuisi adalah bahwa ia memiliki kekuatan konsistensi yang sama seperti logika klasik. Untuk logika proposisional ini pertama kali dibuktikan oleh Glivenko [1929].
Teorema Glivenko : Rumus proposisional yang sewenang-wenang A dapat dibuktikan secara klasik, jika dan hanya jika ¬ A dapat dibuktikan secara intuisi.
Teorema Glivenko tidak mencakup logika predikat, walaupun formula predikat yang sewenang-wenang A dapat dibuktikan secara klasik jika dan hanya jika ¬ ¬ A dapat dibuktikan dalam logika predikat intuisi dan skema "double negation shift"
(DNS) ∀ x ¬¬ B ( x ) → ¬ ¬ ∀ x B ( x ).
Terjemahan negatif klasik yang lebih canggih menjadi teori intuisi, yang secara independen diberikan kepada Gödel dan Gentzen, diasosiasikan dengan setiap formula A dari bahasa L formula lain g ( A ) (tanpa ∨ atau ∃), sehingga
(I) Predikat predikat klasik membuktikan A ↔ g ( A ).
(II) Intuitionistic predicate logic membuktikan g ( A ) ↔ ¬ ¬ g ( A ).
(III) Jika logika predikat klasik membuktikan A , maka logika predikat intuisi membuktikan g ( A ).
Buktinya jelas dari definisi induktif g ( A ) berikut (dengan menggunakan implikasi langsung Gentzen, bukan Gödel dalam hal ¬ dan &):
- g ( P ) adalah ¬ ¬ P , jika P prima.
- g ( A & B ) adalah ( g ( A ) & g ( B )).
- g ( A ∨ B ) adalah ¬ (¬ g ( A ) & ¬ g ( B )).
- g ( A → B ) adalah ( g ( A ) → g ( B )).
- g (¬ A ) adalah ¬ g ( A ).
- g (∀ x A ( x )) adalah ∀ x g ( A ( x )).
- g (∃ x A ( x )) adalah ¬∀ x ¬ g ( A ( x )).
Untuk setiap rumus A , g ( A ) dapat dibuktikan secara intuisi jika dan hanya jika A dapat dibuktikan secara klasik. Secara khusus, jika ( B & ¬ B ) dapat dibuktikan secara klasik untuk beberapa formula B , maka ( g ( B ) & ¬ g ( B )) (yang adalah g ( B & ¬ B )) pada gilirannya dapat dibuktikan secara intuisi. Karenanya
(IV) Logika prediktif klasik dan intuisi bersifat equiconsistent.
Terjemahan negatif klasik menjadi teori bilangan intuisi bahkan lebih sederhana, karena formula utama aritmatika intuisi sangat stabil. Jadi g ( s = t ) dapat diambil menjadi ( s = t ), dan klausa lainnya tidak berubah. Terjemahan negatif dari setiap contoh induksi matematika adalah contoh lain dari induksi matematis, dan aksioma nonlogis aritmatika lainnya adalah terjemahan negatif mereka sendiri, jadi
(I) , (II) , (III) dan (IV) berlaku juga untuk teori bilangan.
Gödel [1933e] menafsirkan hasil ini karena menunjukkan bahwa logika intuisi dan aritmatika lebih kaya daripada logika klasik dan aritmatika, karena teori intuisiistik membedakan formula yang setara secara klasik, dan memiliki kekuatan konsistensi yang sama dengan teori klasik.
Upaya langsung untuk memperluas interpretasi negatif terhadap analisis gagal karena terjemahan negatif dari aksioma pilihan yang dapat dihitung bukanlah teorema analisis intuisi. Namun, ini konsisten dengan analisis intuisi, termasuk prinsip kontinuitas kontinuitas Brouwer, dengan versi fungsional dari realisasi rekursi Kleene (Bagian 5.2 di bawah).
4.2 Aturan logika dan aritmatika intuisi yang dapat diterima
Gödel [1932] mengamati bahwa logika proporsional intuisiistik memiliki sifat disjungsi :
(DP) Jika ( A ∨ B ) adalah sebuah teorema, maka A adalah sebuah teorema atau B adalah sebuah teorema.
Gentzen [1935] mendirikan properti disjungsi untuk formula formula intuisi intuisi yang tertutup. Dari sini, jika logika intuisi konsisten, maka ( P ∨ ¬ P ) bukanlah teorema jika P prima. Kleene [1945, 1952] membuktikan bahwa teori bilangan orde pertama intuisi juga memiliki properti eksistensi (cf. Friedman [1975]):
(ED) Jika ∃ x A ( x ) adalah teorema tertutup, maka untuk beberapa istilah tertutup t , A ( t ) adalah sebuah teorema.
Sifat disjungsi dan eksistensi adalah kasus khusus dari fenomena umum yang khas teori nonclassical. Aturan teori yang dapat diterima adalah aturan di mana teori ditutup. Sebagai contoh, Harrop [1960] mengamati bahwa peraturan tersebut
Jika (¬ A → ( B ∨ C )) adalah sebuah teorema, maka (¬ A → B ) ∨ (¬ A → C )
Diakses untuk logika proporsional proporsional IPC karena jika A , B dan C adalah formula apa pun sehingga (¬ A → ( B ∨ C )) dapat dibuktikan di IPC , maka (¬ A → B ) ∨ (¬ A → C ) adalah terbukti di IPC . Aturan Harrop tidak diturunkan dalam IPC karena (¬ A → ( B ∨ C )) → (¬ A → B ) ∨ (¬ A → C ) tidak dapat dibuktikan secara intuisi. Contoh lain yang penting dari aturan IPC yang dapat diterima adalah peraturan Mints ':
Jika (( A → B ) → A ∨ C ) adalah teorema, maka (( A → B ) → A ) ∨ (( A → B ) → C ).
Interpretasi tabel kebenaran dua nilai dari logika proporsional klasik BPK menimbulkan sebuah bukti sederhana bahwa setiap aturan BPK yang dapat diterima dapat diturunkan: jika tidak, beberapa tugas ke A , B , dll akan membuat hipotesis benar dan kesimpulannya salah, dan oleh mengganti misalnya ( P → P ) untuk huruf-huruf yang diberi nama "benar" dan ( P & ¬ P ) untuk yang ditugaskan "salah" akan memiliki hipotesis yang dapat dibuktikan dan kesimpulan yang tidak dapat dibuktikan. Kenyataan bahwa situasi intuisi lebih menarik menyebabkan banyak pertanyaan alami, beberapa di antaranya baru saja dijawab.
Dengan menggeneralisasi Aturan Mints ', Visser dan de Jongh mengidentifikasi urutan enumeratif secara berulang dari peraturan yang dapat diterima secara berturut-turut ("peraturan Visser") yang, mereka duga, membentuk dasar untuk aturan IPC yang dapat diterima dalam arti bahwa setiap aturan yang dapat diterima dapat diturunkan dari properti disjungsi dan salah satu aturan berurutan. Membangun karya Ghilardi [1999], Iemhoff [2001] berhasil membuktikan dugaan mereka. Rybakov [1997] membuktikan bahwa kumpulan semua aturan IPC yang dapat diterima dapat ditolak namun tidak memiliki dasar yang terbatas. Visser [2002] menunjukkan bahwa peraturannya juga merupakan aturan proposisional yang dapat diterima dari HA , dan HA diperluas oleh Prinsip Markov MP (didefinisikan dalam Bagian 5.2 di bawah). Baru-baru ini, Jerabek [2008] menemukan dasar yang berbeda untuk aturan IPC yang dapat diterima dengan properti yang tidak memiliki dasar aturan yang lain.
Jauh lebih sedikit yang diketahui tentang aturan logika predikat intuisi yang dapat diterima. IQC murni, tanpa konstanta individu atau predikat, memiliki aturan yang dapat diterima berikut yang luar biasa untuk A ( x ) tanpa variabel bebas namun x :
Jika ∃ x A ( x ) adalah sebuah teorema, maka ∀ x A ( x ).
Tidak semua aturan predikat IQC yang dapat diterima dapat diterima untuk semua sistem formal berdasarkan IQC ; Misalnya, HA ternyata melanggar peraturan yang baru saja dinyatakan. Visser membuktikan pada [1999] bahwa properti sebagai aturan predikat yang sah dari HA adalah Π 2 lengkap, dan pada [2002] bahwa HA & plus; MP memiliki aturan predikat yang sama seperti HA . Plisko [1992] membuktikan bahwa logika predikat HA + MP (himpunan kalimat dalam bahasa IQC semua contoh substitusi seragamnya dalam bahasa aritmatika dapat dibuktikan dalam HA + MP) adalah Π 2 lengkap; Visser [2006] memperpanjang hasil ini ke beberapa kombinasi HA yang konsisten secara konstruktif yang tidak terkandung di dalam PA .
Meskipun mereka belum sepenuhnya diklasifikasikan, aturan logika predikat intuisi yang dapat diterima diketahui mencakup Aturan Markov untuk predikat yang dapat ditolak:
Jika ∀ x ( A ( x ) ∨ ¬ A ( x )) & ¬∀ x ¬ A ( x ) adalah sebuah teorema, maka ∃ x A ( x )
dan Aturan Kemandirian berikut ini (jika y diasumsikan tidak terjadi bebas dalam A ( x )):
Jika ∀ x ( A ( x ) ∨ ¬ A ( x )) & (∀ x A ( x ) → ∃ y B ( y )) adalah sebuah teorema, maka ∃ y (∀ x A ( x ) → B ( y )).
Kedua aturan tersebut juga dapat diterima untuk HA . Implikasi yang sesuai (MP dan IP masing-masing), yang tidak dapat dibuktikan secara intuisi, diverifikasi oleh interpretasi "Dialektika" Gödel tentang HA (lihat Bagian 6.3 di bawah). Begitu juga implikasinya (CT) yang sesuai dengan salah satu aturan yang paling menarik yang dapat diterima dari Heyting arithmetic, mari kita menyebutnya Church-Kleene Rule :
Jika ∀ x ∃ y A ( x , y ) adalah teorema tertutup dari HA maka ada beberapa n sedemikian sehingga, terbukti dalam HA , fungsi rekursif parsial dengan bilangan Gödel n adalah total dan memetakan masing-masing x ke y yang memuaskan A ( x , y ) (dan terlebih lagi A ( x , y ) dapat dibuktikan, di mana x adalah angka untuk bilangan natural x dan y adalah angka untuk y ).
Menggabungkan Aturan Markov dengan terjemahan negatif memberi hasil bahwa aritmatika klasik dan intuisiistik membuktikan formula yang sama dari bentuk ∀ x ∃ y A ( x , y ) di mana A ( x , y ) bebas dari pengkuantifikasi. Secara umum, jika A ( x , y ) dapat dibuktikan secara pasti dalam HA dan jika ∀ x ∃ y A ( x , y ) adalah teorema tertutup PA aritmatika klasik , kesimpulan Aturan Gereja-Kleene berlaku bahkan dalam aritmatika intuisi . Karena jika HA membuktikan ∀ x ∀ y ( A ( x, y ) ∨ ¬ A ( x, y )) maka oleh Church-Kleene Rule, fungsi karakteristik A ( x, y ) memiliki bilangan Gödel m , terbukti dalam HA ; jadi HA membuktikan ∀ x ∃ y A ( x, y ) ↔ ∀ x ∃ y ∃ z B ( m , x, y, z ) di mana B bebas dari quantifier, dan pengenal eksistensial yang berdekatan dapat dikontrak dalam HA . Ini berarti bahwa HA dan PA memiliki fungsi rekursif yang sama.
Berikut adalah bukti bahwa aturan "If ∀ x ( A ∨ B ( x )) adalah sebuah teorema, jadi A ∨ ∀ x B ( x )" (di mana x tidak bebas dalam A ) tidak dapat diterima untuk HA , jika HA konsisten. Penomoran Gödel memberi rumus kuantitatif bebas G ( x ) yang (numeralwise) mengekspresikan predikat " x adalah kode bukti dalam HA dari (0 = 1)." Dengan logika intuisi dengan determinabilitas formula aritmatika bebas kuantitatif, HA membuktikan ∀ x (∃ y G ( y ) ∨ ¬ G ( x )). Namun, jika HA membuktikan ∃ y G ( y ) ∨ ∀ x ¬ G ( x ) maka oleh properti disjungsi, HA harus membuktikan ∃ y G ( y ) atau ∀ x ¬ G ( x ). Kasus pertama tidak mungkin dilakukan, oleh keberadaan properti dengan asumsi konsistensi dan fakta bahwa HA membuktikan semua kalimat bebas-pengenal yang benar. Tapi kasus kedua juga tidak mungkin, oleh teorema ketidaklengkapan Gödel yang kedua, karena ∀ x ¬ G ( x ) mengekspresikan konsistensi HA .
5. Semantik Dasar
5.1 Semantik semantik untuk logika intuisi
Sistem intuitionistik telah mengilhami berbagai interpretasi, termasuk tabel Beth, model topologi Rasiowa dan Sikorski, formula-as-type, perwujudan rekursif Kleene, garis miring Kleene dan Aczel, dan model berdasarkan sheafs dan topoi. Semantik dunia semiloka Kripke [1965] mungkin, yang dengannya logika predikat intuisi sangat lengkap dan konsisten, paling menyerupai teori model klasik.
Struktur Kripke K untuk L terdiri dari himpunan sebagian node K dan fungsi domain D yang ditugaskan ke setiap simpul k di K yang dihuni D ( k ), sehingga jika k ≤ k ', maka D ( k ) ⊆ D ( k '). Selain itu K memiliki hubungan paksa yang ditentukan sebagai berikut.
Untuk setiap node k biarkan L ( k ) menjadi bahasa yang memanjang L dengan konstanta baru untuk semua elemen D ( k ). Untuk setiap simpul k dan masing-masing surat predikat 0-an (masing-masing huruf proposisi) P , tentukan f ( P , k ) = true atau leave f ( P , k ) undefined, sesuai dengan persyaratan bahwa jika k ≤ k 'dan f ( P , k ) = true maka f ( P , k ') = true juga. Katakan itu
k memaksa P jika dan hanya jika f ( P , k ) = true .
Untuk setiap simpul k dan masing-masing ( n + 1 ) huruf predikat Q (...), tetapkan set (mungkin kosong) T ( Q , k ) dari ( n + 1 ) - elemen elemen D ( k ) pada sebuah cara yang jika k ≤ k 'maka T ( Q , k ) ⊆ T ( Q , k '). Katakan itu
k kekuatan Q ( d 0 , ..., d n ) jika dan hanya jika ( d o , ..., d n ) ∈ T (Q, k ).
Sekarang definisikan memaksa untuk kalimat majemuk L ( k ) secara induktif sebagai berikut:
- k kekuatan ( A & B ) jika k memaksa A dan k memaksa B.
- k force ( A ∨ B ) jika k memaksa A atau k force B.
- k kekuatan ( A → B ) jika, untuk setiap k '≥ k , jika k ' memaksa A maka k ' kekuatan B.
- k kekuatan ¬ A jika tanpa k '≥ k tidak k ' gaya A.
- k kekuatan ∀ x A ( x ) jika untuk setiap k '≥ k dan setiap d ∈ D ( k '), k ' kekuatan A ( d ).
- k kekuatan ∃ x A ( x ) jika untuk beberapa d ∈ D ( k ), k memaksa A ( d ).
- karena tidak ada kalimat A dan tidak k k memaksa A dan A.
- jika k ≤ k 'dan k memaksa A maka k ' kekuatan A.
Model Kripke untuk bahasa dengan persamaan dapat menafsirkan = pada setiap simpul dengan relasi ekuivalen sewenang-wenang, tergantung pada monotonisitasnya. Untuk aplikasi aritmatika intuisi, model normal (di mana persamaan diinterpretasikan oleh identitas pada setiap simpul) cukup karena persamaan angka alam dapat ditolak.
Semantik semantik proporsional sangat sederhana, karena formula proposisi yang sewenang-wenang dapat dibuktikan secara intuisi jika dan hanya jika dipaksakan oleh akar setiap model Kripke yang kerangkanya (himpunan K dari simpul bersama dengan sebagian pemesanannya) adalah pohon yang terbatas dengan yang paling sedikit elemen ( akar ). Sebagai contoh, model Kripke dengan K = { k , k ', k ' '}, k < k ' dan k < k '', dan dengan P true only at k ', menunjukkan bahwa baik P ∨ ¬P dan ¬P ∨ ¬ ¬ tidak dapat dibuktikan di IPC .
Setiap simpul terminal atau daun model Kripke adalah model klasik, karena daun memaksa setiap formula atau negasinya. Hanya huruf proposisi yang terjadi dalam formula E , dan hanya simpul k 'sedemikian sehingga k ≤ k ', relevan untuk menentukan apakah atau tidak k gaya E. Pertimbangan tersebut memungkinkan kita untuk berasosiasi secara efektif dengan setiap formula E dari L ( IPC ) sebuah kelas terbatas dari struktur Kripke yang terbatas yang akan mencakup countododel ke E jika ada. Karena kelas semua teorema IPC bersifat rekursif, kami menyimpulkan itu
IPC secara efektif dapat ditolak. Ada prosedur rekursif yang menentukan, untuk setiap formula proposisi E , E atau tidak adalah teorema IPC , diakhiri dengan bukti E atau countermodel Kripke.
Desidability IPC pertama kali diperoleh oleh Gentzen pada tahun 1933 sebagai akibat langsung dari Hauptsatz- nya. Ketidakpastian IQC mengikuti undecidability CQC dengan interpretasi negatif.
Skema logis non-intuisi yang familiar sesuai dengan sifat struktural model Kripke, misalnya
DNS berlaku di setiap model Kripke dengan bingkai terbatas.
( A → B ) ∨ ( B → A ) berlaku pada setiap model Kripke dengan bingkai yang dipesan secara linier. Sebaliknya, setiap formula proposisional yang tidak diturunkan dalam IPC + ( A → B ) ∨ ( B → A ) memiliki countermodel Kripke dengan bingkai yang dipesan secara linier.
Jika x tidak bebas pada A maka (∀ x (A∨ B ( x )) → ( A ∨ ∀ x B ( x ))) berlaku di setiap model Kripke K dengan domain konstan (sehingga D ( k ) = D k ') untuk semua k , k ' di K ). Hal yang sama berlaku untuk anggota parlemen.
Model Kripke adalah alat yang ampuh untuk membangun sifat sistem formal intuisi; lih. Troelstra dan van Dalen [1988], Smorynski [1973], de Jongh dan Smorynski [1976], Ghilardi [1999] dan Iemhoff [2001], [2005]. Mengikuti Gödel, Kreisel [1962] berpendapat bahwa Kripke-kelengkapan logika intuisi mengandung Prinsip Markov. Dengan memodifikasi definisi model Kripke untuk memungkinkan "titik balik yang meledak" yang memaksa setiap kalimat, Veldman [1976] menemukan bukti kelengkapan intuisi yang menghindari penggunaan informal MP.
5,2 Realizability semantik untuk Heyting aritmatika
Salah satu cara untuk menerapkan penjelasan BHK tentang kebenaran intuisi untuk aritmatika adalah mengasosiasikan dengan setiap kalimat E HA beberapa koleksi kode numerik untuk algoritma yang dapat membangun kebenaran konstruktif dari E. Setelah Kleene [1945], sebuah angka e menyadari sebuah kalimat E dari bahasa aritmatika dengan induksi pada bentuk logis E :
- e realizes ( r = t ), jika ( r = t ) benar.
- e menyadari ( A & B ), jika kode e pasangan (f, g) sehingga f menyadari A dan g menyadari B.
- e alizes ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨............................
- e menyadari A → B , jika, jika f menyadari A , maka fungsi rekursif parsial e didefinisikan pada f dan nilainya menyadari B.
- e menyadari ¬ A , jika tidak ada yang menyadari A.
- e menyadari ∀ x A ( x ), jika, untuk setiap n , fungsi rekursif parsial e didefinisikan pada n dan nilainya mewujudkan A ( n ).
- e menyadari ∃ x A ( x ), jika kode e pasangan (n, g) dan g mewujudkan A ( n ).
Rumus sewenang-wenang dapat direalisasikan jika beberapa orang menyadari penutupan universalnya. Amati bahwa tidak kedua A dan A dapat direalisasikan, untuk rumus A. Hasil dasarnya adalah
Teorema Nelson [1947]. Jika A diturunkan dalam HA dari rumus yang dapat direalisasikan F , maka A dapat direalisasikan.
Beberapa prinsip nonintuitionistik dapat ditunjukkan untuk dapat direalisasikan. Misalnya, Prinsip Markov (untuk formula yang dapat ditolak) dapat diungkapkan oleh skema
( X ) ∀ x A ( x ) → ∃ x A ( x ).
Meskipun tidak dapat dibuktikan dalam HA , MP dapat direalisasikan dengan argumen yang menggunakan Prinsip Markov secara informal. Tapi realizability adalah interpretasi nonclassical yang fundamental. Dalam HA adalah mungkin untuk mengekspresikan sebuah aksioma CT pilihan rekursif (untuk "Tesis Gereja"), yang bertentangan dengan LEM namun secara konstruktif dapat direalisasikan. Oleh karena itu, Teorema Nelson, HA + MP + CT konsisten.
Kleene menggunakan varian angka realizabilitas untuk membuktikan bahwa HA memenuhi Aturan Gereja-Kleene; Argumen yang sama berlaku untuk HA dengan MP dan / atau CT. Di Kleene dan Vesley [1965] dan Kleene [1969], berfungsi menggantikan angka sebagai objek mewujudkan, membangun konsistensi analisis intuisi formal yang diformalkan dan penutupannya di bawah versi kedua dari Aturan Gereja-Kleene.
De Jongh [1970] menggabungkan realizabilitas dengan pemodelan Kripke untuk menunjukkan bahwa logika predikat intuisi secara aritmatik lengkap untuk HA . Jika, untuk setiap huruf predikat n- tempat P (...), formula f ( P ) L ( HA ) dengan n variabel bebas diberikan, dan jika rumus f ( A ) dari L ( HA ) berasal dari rumus A dari L dengan mengganti setiap formula utama P ( x 1 , ..., x n ) dengan f ( P ) ( x 1 , ..., x n ), maka f ( A ) disebut contoh substitusi aritmatika dari A. Penugasan seragam formula eksistensial sederhana terhadap predikat surat cukup untuk membuktikannya
Teorema De Jongh. Jika kalimat A dari bahasa L tidak dapat dibuktikan dalam IQC , maka beberapa substitusi aritmetika A tidak dapat dibuktikan dalam HA .
Misalnya, jika P ( x , y ) menyatakan " x mengkodekan sebuah bukti dalam HA dari rumus dengan kode y ," maka ∀ y (∃ x P ( x , y ) ∨ ¬∃ x P ( x , y )) adalah tidak dapat direalisasikan, maka tidak dapat dibuktikan dalam HA , dan begitu pula negasi gandanya. (Sebagai bukti, Teorema Teorema de Jongh untuk IPC tidak memerlukan realizability; cf. Smorynski [1973]. Sebagai contoh, bentuk Rosser dari Teorema Ketidakkonsistenan Gödel memberikan kalimat C dari L ( HA ) sehingga PA tidak membuktikan C atau C , Jadi oleh properti disjungsi HA tidak dapat membuktikan ( C ∨ ¬ C ).)
Tanpa mengklaim bahwa angka-realizability bertepatan dengan kebenaran arithmetical intuisi, Nelson mengamati bahwa untuk setiap formula A dari L ( HA ) predikat " y menyadari A " dapat dinyatakan dalam HA dengan formula lain (disingkat " y re A "), dan Skema A ↔ ∃ y ( y re A ) konsisten dengan HA . Troelstra [1973] menunjukkan bahwa HA + ( A ↔ ∃ y ( y re A )) setara dengan HA + ECT, di mana ECT adalah bentuk CT yang diperkuat. Dalam HA + MP + ECT, yang oleh Troelstra dianggap sebagai formalisasi matematika rekursif Rusia (lihat bagian 3.2 dari entri mengenai matematika konstruktif ), setiap formula dari bentuk ( y re A ) memiliki bentuk preneks "klasik" ekuivalen A '( Y ) yang terdiri dari subformula bebas kuantifier yang diawali dengan mengubah "klasik" pengukur dari bentuk ¬ ¬ ¬ x dan ∀ z ¬¬, dan jadi ∃ y A ' ( y ) adalah sejenis bentuk preneks A.
6. Topik Tambahan dan Bacaan Lebih Lanjut
6.1 Logika subintuisiistik dan superintuitionistik
Saat ini ada beberapa entri lain dalam ensiklopedia ini yang memperlakukan logika intuisi dalam berbagai konteks, namun perlakuan umum terhadap logika menengah tampaknya kurang dilakukan sehingga yang singkat disertakan di sini. Logika proposisional subintuisiistik dapat diperoleh dari IPC dengan membatasi bahasa, atau melemahkan logika, atau keduanya. Contoh ekstrem pertama adalah RN , logika intuisi dengan variabel proposisi tunggal P , yang dinamai menurut penemunya Rieger dan Nishimura [1960]. RN dicirikan oleh kisi Rieger-Nishimura dari formula tak berhingga yang tak terhingga banyaknya sehingga setiap formula yang hanya variabel proposisinya adalah P adalah ekuivalen dengan logika intuisi terhadap beberapa F n . Versi Nishimura adalah
- F ∞ = P → P.
- F 0 = P & ¬ P.
- F 1 = P.
- F 2 = ¬ P.
- F 2n + 3 = F 2n + 1 ∨ F 2n + 2 .
- F 2n + 4 = F 2n + 3 → F 2n + 1 .
Dalam RN tidak F 2n + 1 atau F 2n + 2 menyiratkan yang lain; namun F 2n menyiratkan F 2n + 1 , dan F 2n + 1 menyiratkan masing-masing F 2n + 3 dan F 2n + 4 .
Fragmen IPC yang hilang satu atau lebih penghubung logis membatasi bahasa dan kebetulan logika, karena penghubung intuisi dan, ∨, →, ¬ secara logis independen terhadap IPC . Rose [1953] membuktikan bahwa fragmen implisit (tanpa →) lengkap sehubungan dengan realisasi, dalam arti bahwa jika setiap contoh substitusi aritmetika dari formula proposisi E tidak → adalah (bilangan) - dapat diartikan maka E adalah teorema IPC . Hasil ini kontras dengan
Teorema Rose [1953]. IPC tidak lengkap sehubungan dengan realizability. Misalkan F adalah formula proposisional
(¬ ¬ D → D) → (¬ ¬ D ∨ ¬ D)) → (¬ ¬ D ∨ ¬ D)
dimana D adalah (¬ P ∨ ¬ Q ) dan P, Q prima. Setiap contoh substitusi aritmatika F dapat direalisasikan (menggunakan logika klasik), namun F tidak dapat dibuktikan dalam IPC .
Dengan demikian, IPC secara aritmatik tidak lengkap untuk HA + ECT (lihat Bagian 5.2).
Logika proposisional menengah adalah kumpulan formula proposisional yang konsisten yang berisi semua aksioma IPC dan ditutup dengan modus huruf pon dan substitusi formula sewenang-wenang untuk surat-surat proposisi. Setiap logika proposisional menengah terkandung dalam BPK . Beberapa logika proposisional menengah tertentu, yang ditandai dengan menambahkan satu atau beberapa skema aksioma yang benar secara klasik namun tidak dapat dibuktikan secara intuisi untuk IPC, telah dipelajari secara ekstensif.
Salah satu logika proporsional menengah yang paling sederhana adalah logika Gödel-Dummett LC , yang diperoleh dengan menambahkan ke IPC skema ( A → B ) ∨ ( B → A ) yang berlaku untuk semua dan hanya kerangka Kripke di mana urutan parsial dari node bersifat linier Gödel [1932] menggunakan rangkaian tak berhingga dari logika menengah yang berturut-turut lebih kuat untuk menunjukkan bahwa IPC tidak memiliki interpretasi tabel kebenaran yang terbatas. Untuk setiap bilangan bulat positif n , misalkan G n adalah LC ditambah skema ( A 1 → A 2 ) ∨ ... ∨ ( A 1 & ... & A n → A n + 1 ). Kemudian G n berlaku untuk semua dan hanya frame Kripke yang secara linier tidak lebih dari n node.
The Kreisel-Putnam logika KP , diperoleh dengan menambahkan ke IPC skema (¬ A → B ∨ C ) → ((¬ A → B ) ∨ (¬ A → C )), memiliki sifat disjungsi namun tidak memuaskan semua Visser aturan. Logika menengah yang diperoleh dengan menambahkan skema ( D ¬ ¬ D )) → (¬ ¬ D ∨ ¬ D ), sesuai dengan contoh pengganti Rose, untuk IPC juga memiliki properti disjungsi. Iemhoff [2005] membuktikan bahwa IPC adalah satu-satunya logika proporsional menengah dengan properti disjungsi yang ditutup di bawah semua aturan Visser. Iemhoff dan Metcalfe [2009] mengembangkan kalkulus formal untuk generalisasi admissibility untuk IPC dan beberapa logika menengah.
Logika proposisional perantara L dikatakan memiliki properti bingkai terbatas jika ada kelas bingkai terbatas dimana formula Kripke-berlaku persis seperti teorema L. Banyak logika antara, termasuk LC (kelas bingkai linier terbatas) dan KP , memiliki properti ini. De Jongh, Verbrugge dan Visser [2009] membuktikan bahwa setiap logika perantara L dengan properti bingkai terbatas adalah logika proposisional HA (L) , yaitu kelas dari semua formula dalam bahasa IPC yang semuanya merupakan contoh substitusi aritmatikanya. dibuktikan dalam perpanjangan logis dari HA oleh L.
Beberapa logika predikat menengah , memperluas IQC dan ditutup di bawah substitusi, adalah IQC & plus; DNS (Bagian 4.1), IQC & plus; MP (lihat Bagian 5.2), IQC & plus; MP & plus; IP (lihat Bagian 6.2), dan logika intuisi dari domain konstan CD diperoleh dengan menambahkan ke IQC skema ∀ x (A∨ B ( x )) → ( A ∨ ∀ x B ( x )) untuk semua formula A, B ( x ) dengan x tidak terjadi bebas dalam A. Mints, Olkhovikov dan Urquhart [2012, Sumber Daya Internet Lainnya] menunjukkan bahwa CD tidak memiliki properti interpolasi, menolak bukti yang diterbitkan sebelumnya oleh penulis lain.
6.2 Topik lanjutan
Pengaruh Brouwer terhadap Gödel signifikan, meski Gödel tidak pernah menjadi seorang intuisi. Terjemahan logika logika proporsional Gödel ke logika modal S4 dijelaskan di Bagian 2.5 dari entri di Gödel dan catatan pengantar Troelstra untuk terjemahan [1933f] dalam Volume I karya terkumpul Gödel. Lihat juga Mint [2012]. Model Kripke untuk logika modal mendahului logika intuisi.
Sebuah alternatif untuk semantik realizability untuk aritmatika intuisi adalah interpretasi Gödel [1958] "Dialectica", yang berasosiasi dengan setiap formula B dari L ( HA ) formula bebas kuantitatif B D dalam bahasa aritmatika intuisi dari semua jenis yang terbatas. Interpretasi "Dialectica" dari B , sebut saja B D , adalah ∃ Y ∀ x B D ( Y , x ). Jika B adalah teorema tertutup HA , maka B D ( F , x ) dapat dibuktikan untuk beberapa istilah F dalam teori Gödel T fungsi "primitif rekursif" tipe yang lebih tinggi. Terjemahan dari B ke B D memerlukan aksioma pilihan (pada semua tipe terbatas), MP dan IP, jadi tidak terlalu konstruktif; Namun, fungsi teoritis bilangan yang dapat diekspresikan dengan istilah F dari T adalah fungsi HA yang tepat dan tepat (dan PA ). Penafsiran diperluas untuk dianalisis oleh Spector [1962]; lih. Howard [1973]. Eksposisi yang jelas, dan referensi tambahan, dapat ditemukan dalam pengantar Troelstra terhadap terjemahan bahasa Inggris di Gödel [1990] dari artikel Dialectica yang asli, dan di Avigad dan Feferman [1998].
Sementara HA adalah bagian aritmatika klasik yang tepat, sikap intuisi terhadap objek matematika menghasilkan teori bilangan real (bandingkan bagian 3.4-3.7 tentang masuknya intuisiisme dalam filsafat matematika ) yang berbeda dari yang klasik. Fungsi Kleene-interpretasi realizability, dikembangkan untuk membuktikan konsistensi modifikasinya FIM terhadap teori intuisi tentang urutan ("analisis intuisi"), mengubah interpretasi formula aritmatika; Misalnya, ¬ ¬∀ x ( A ( x ) ∨ ¬ A ( x )) adalah fungsi yang dapat direalisasikan untuk setiap rumus aritmatika A ( x ). Dalam bahasa analisis, Prinsip Markov dan terjemahan negatif dari aksioma pilihan yang dapat dihitung adalah di antara banyak prinsip non-intuisi yang dapat disadari (oleh argumen klasik) dan karenanya sesuai dengan FIM ; lih. Kleene [1965], Vesley [1972] dan Moschovakis [2003].
Semantik konkret dan abstrak untuk berbagai sistem formal telah dikembangkan dan dipelajari oleh ahli logika dan ilmuwan komputer; lih. Troelstra [1998] dan van Oosten [2002] dan [2008]. Variasi pengertian dasar sangat berguna untuk membangun konsistensi relatif dan independensi relatif dari aksioma nonlogis dalam teori yang didasarkan pada logika intuisi; beberapa contohnya adalah Moschovakis [1971], Lifschitz [1979], dan konsep realisasi teori himpunan konstruktif dan intuisi yang dikembangkan oleh Rathjen [2006, 2012] dan Chen [2012]. Gagasan realisasi abstrak awal mencakup garis miring Kleene [1962, 1963] dan Aczel [1968], dan Läuchli [1970]. Kohlenbach, Avigad dan lainnya telah mengembangkan interpretasi realizability untuk bagian matematika klasik.
Logika pembenaran Artemov adalah interpretasi alternatif dari penjelasan BHK tentang penghubung dan pengukur intuisi, dengan bukti (ideal) yang memainkan peran untuk mewujudkan objek. Lihat juga Artemov dan Iemhoff [2007].
Bidang penelitian lain dalam logika intuisi mengkhawatirkan contoh "variabel subjek kontroversial" Brouwer yang sangat kontroversial terhadap prinsip analisis klasik (seperti Prinsip Markov) yang tidak dapat disangkal berdasarkan teori FIM Kleene dan Vesley [1965]. Dengan melemahkan bentuk Kleene tentang pilihan terus-menerus Brouwer, dan menambahkan sebuah aksioma yang dia sebut Skema Kripke (KP), Myhill berhasil memformalkan argumen subjek yang menciptakan. KP tidak konsisten dengan FIM , namun Vesley [1970] menemukan sebuah prinsip alternatif ( Skema Vesley (VS)) yang dapat ditambahkan secara konsisten ke FIM dan menyiratkan semua contoh di balik mana Brouwer memerlukan subjek yang menciptakan. Krol dan Scowcroft memberikan bukti konsistensi topological untuk analisis intuisiistik dengan Skema Kripke dan kontinuitas yang lemah.
6.3 Bacaan yang disarankan
Entri di LEJ Brouwer membahas filosofi Brouwer dan matematika, dengan kronologi hidupnya dan daftar publikasi yang dipilih termasuk terjemahan dan sumber sekunder. Cara terbaik untuk belajar lebih banyak adalah membaca beberapa dokumen asli. Terjemahan Inggris dari disertasi doktor Brouwer dan makalah lainnya yang aslinya berbahasa Belanda, beserta sejumlah artikel berbahasa Jerman, dapat ditemukan di LEJ Brouwer: Collected Works [1975], disunting oleh Heyting. Buku sumber penting Benacerraf dan Putnam berisi Brouwer [1912] (dalam terjemahan bahasa Inggris), Brouwer [1949] dan Dummett [1975]. Mancosu's [1998] menyediakan terjemahan bahasa Inggris dari banyak artikel mendasar oleh Brouwer, Heyting, Glivenko dan Kolmogorov, dengan bahan pengantar yang menerangi oleh W. van Stigt yang [1990] adalah sumber berharga lainnya.
Edisi ketiga [1971] karya klasik Heyting [1956] adalah pengantar menarik tentang filsafat intuisi, logika dan praktik matematika. Sebagai bagian dari proyek editing dan penerbitan Broachler 's Nachlass yang hebat , van Dalen [1981] memberikan pandangan menyeluruh tentang filosofi intuisi Brouwer sendiri. Terjemahan bahasa Inggris, di van Heijenoort [1969], dari Brouwer [1927] (dengan pengenalan yang bagus dari Parsons) masih merupakan referensi yang sangat diperlukan untuk teori kontinum Brouwer. Veldman [1990] dan [2005] adalah contoh modern otentik praktik matematika intuisi tradisional. Troelstra [1991] menempatkan logika intuisi dalam konteks historisnya sebagai dasar umum matematika konstruktif pada abad ke-20. Bezhanishvili dan de Jongh [2005, Other Internet Resources] mencakup perkembangan terkini dalam logika intuisi.
Kleene dan Vesley's [1965] memberikan perlakuan aksiomatik yang cermat terhadap analisis intuisi, sebuah bukti konsistensinya terhadap sub-teorinya yang benar secara klasik, dan sebuah aplikasi yang diperluas untuk teori generator bilangan asli Brouwer. Kleene's [1969] meresmikan teori fungsi rekursif parsial, yang memungkinkan formisialisasi yang tepat dari interpretasi realizabilitas fungsi yang digunakan dalam [1965] dan interpretasi q-realizability terkait yang memberi Aturan Gereja-Kleene untuk analisis intuisi.
Troelstra's [1973], Beeson's [1985] dan Troelstra dan van Dalen's [1988] menonjol sebagai studi paling komprehensif tentang teori formal intuisi dan semi-intutionistik, menggunakan metode konstruktif dan klasik, dengan bibliografi yang bermanfaat. Troelstra's [1998] menyajikan formula-as-types dan (Kleene and Aczel) menebas interpretasi untuk logika proposisional dan predikat, serta abstrak dan realistik untuk banyak aplikasi. Teori konstruktif Martin-Löf tentang tipe [1984] (lihat Bagian 3.4 dari entri mengenai matematika konstruktif ) menyediakan kerangka kerja umum lainnya dimana penalaran intuisi terus berkembang.
Sumber: plato.stanford.edu