Predikat rekursif primitif untuk eksponensiasi dan perkalian
Saya memiliki keyakinan yang dinyatakan secara informal dan dipegang lemah berikut ini, beberapa di antaranya tampak tidak konsisten bagi saya setelah direnungkan lebih lanjut. Saya bertanya-tanya di mana sumber kesalahan dalam pemikiran saya; kesalahan dalam definisi dasar adalah kemungkinan yang pasti.
Tidak mungkin untuk melakukan eliminasi bilangan dalam teori orde pertama dari bilangan bulat dengan penjumlahan dan perkalian. (Ini, sejauh yang saya tahu, versi yang sedikit lebih kuat dari teorema ketidaklengkapan pertama.)
Dalam teori orde pertama dari bilangan bulat dengan penjumlahan dan perkalian, dimungkinkan untuk menentukan predikat rekursif primitif untuk eksponen. (Dengan predikat eksponen, maksud saya adalah sesuatu yang berperilaku seperti "$Fabc\text{ just when }a^b = c.$")
Hal ini mungkin untuk melakukan penghapusan quantifier dalam teori orde pertama dari bilangan bulat dengan dua operasi$a \oplus b = \min(a, b)$ dan $a \otimes b = a + b$(yaitu, penambahan bilangan bulat biasa). Saya sadar bahwa kita juga membutuhkan predikat pembagian dan operator perkalian agar bilangan prima benar-benar melakukan eliminasi pembilang.
Dalam teori orde pertama dari bilangan bulat dengan operasi $\oplus$ dan $\otimes$, Anda dapat menentukan predikat rekursif primitif untuk perkalian (dengan cara yang hampir persis sama dengan predikat eksponen di atas).
Secara kasar, sepertinya ada gangguan dalam analogi antara "menara operasi biasa" $(+, \times, \hat{\phantom{n}}, \cdots)$ dan "menara operasi tropis" $(\min, +, \times, \cdots)$.
Lebih khusus lagi, jika (4) dan (3) benar Saya tidak mengerti mengapa seseorang tidak bisa dengan bebas menggunakan predikat perkalian dan kemudian memiliki situasi di mana kita berdua dapat melakukan eliminasi pembilang (melalui (3)) dan tidak melakukannya penghapusan pembilang (melalui (1)). Akan sangat mengejutkan saya jika (2) benar tetapi (4) tidak, dan akan lebih mengejutkan saya jika (2) salah.
Saya menduga bahwa saya tidak begitu memahami apa yang dimaksud dengan predikat eksponen (yaitu, definisi informal saya tentang $Fabc$ tidak benar, atau ada detail lain tentang "bebas menggunakan predikat perkalian" yang tidak saya sadari.
Jawaban
Klaim Anda $(1), (2)$, dan $(3)$apakah masing-masing benar. Klaim$(4)$, bagaimanapun, tidak benar ; memang, jika perkalian bisa didefinisikan selesai$(\mathbb{N};\max,+)$ lalu teori $Th(\mathbb{N};\max,+)$ akan serumit $Th(\mathbb{N};+,\times)$. Tetapi yang pertama bersifat rekursif sedangkan yang terakhir bahkan tidak dapat didefinisikan secara aritmatika.
Masalahnya adalah bahwa definisi perkalian yang "jelas" dalam istilah penjumlahan sebenarnya bukan urutan pertama : definisi rekursif bukanlah apriori sesuatu yang dapat dilakukan logika orde pertama. Dalam struktur yang cukup kaya, kita dapat menemukan cara untuk melakukan definisi rekursif dengan cara orde pertama, dan memang itulah kekayaan dari$Th(\mathbb{N};+,\times)$dalam pengertian ini yang memungkinkan eorema Godel, tetapi penambahan saja tidak cukup kuat untuk membuat ini berhasil. Kuncinya adalah jika kita memiliki penjumlahan dan perkalian kita dapat "mengkodekan" urutan terbatas naturals dengan individu alami (misalnya melalui$\beta$fungsi ) dan berbicara tentang konstruksi rekursif dengan berbicara tentang urutan pengkodean "perilaku langkah-demi-langkah mereka," tetapi dengan penambahan saja kita bahkan tidak dapat mengkodekan pasangan angka dengan nomor individu .
Menguraikan kalimat terakhir itu dan kembali ke klaim Anda $(2)$, berikut adalah garis besar cara mendefinisikan eksponensial menggunakan penjumlahan dan perkalian dengan urutan pertama:
Kita punya $a^b=c$ iff ada beberapa bilangan yang jika diartikan berurutan memiliki panjangnya $b$, istilah pertama $a$, istilah terakhir $c$, dan $i+1$istilah th sama dengan $a$ kali $i$istilah th.
Perhatikan bahwa ini adalah definisi "semua sekaligus" daripada definisi dengan "proses rekursif:" modulo detail pengkodean urutan terbatas dengan angka, ini hanya melibatkan penghitungan angka individual dan memeriksa properti dasar, yang persis seperti yang pertama- logika urutan bisa dilakukan. Tanpa kemampuan untuk mengkodekan urutan terbatas sebagai nomor individu dengan cara urutan pertama - yang$(\mathbb{N};\max,+)$ kekurangan - kita akan terjebak dengan definisi non-urutan pertama yang biasa.
- Sebagai tambahan, penting bahwa ini adalah "definisi yang dapat diverifikasi:" dalam teori $\mathsf{Q}$, yang merupakan bagian kecil dari teori lengkap $Th(\mathbb{N};+,\times)$, kami memiliki itu untuk masing-masing $a,b,c$ kalimat yang disingkat $$\underline{a}^{\underline{b}}=\underline{c}$$ (dimana $\underline{k}$ adalah angka yang mewakili bilangan asli $k$) dapat dibuktikan di $\mathsf{Q}$ jika $a^b=c$ dan tidak dapat dibuktikan di $\mathsf{Q}$ jika $a^b\not=c$. Ini disebut keterwakilan , dan merupakan salah satu ide kunci pembuktian Godel; pada kenyataannya, setiap fungsi rekursif dapat direpresentasikan .