Konsekuensi komputasional dari teorema Fixed Shift Upper Friedman (tidak dapat dibuktikan)?

Harvey Friedman menunjukkan bahwa ada hasil titik tetap rapi yang tidak dapat dibuktikan dalam ZFC (teori himpunan Zermelo-Frankel biasa dengan Aksioma Pilihan). Banyak logika modern dibangun di atas operator titik tetap, jadi saya bertanya-tanya: apakah ada konsekuensi yang diketahui dari teorema Fixed Shift Upper Point untuk ilmu komputer teoretis?

Teorema Titik Tetap Geser Atas yang Tidak
Untuk semua , beberapa berisi .A = kubus ( A , 0 ) ∖ R [ A ] kami ( A $R \in \text{SDOI}(Q^k,Q^k)$$A = \text{cube}(A,0) \setminus R[A]$$\text{us}(A)$

Teorema USFP tampaknya merupakan pernyataan , jadi itu mungkin "cukup dekat" untuk komputabilitas (seperti memeriksa non-isomorfisme struktur otomatis), untuk memengaruhi ilmu komputer teoretis.$\Pi^1_1$

Untuk kelengkapan, berikut adalah definisi dari pembicaraan MIT Friedman dari November 2009 (lihat juga draft buku tentang "Teori Hubungan Boolean" ).

$Q$ adalah himpunan bilangan rasional. adalah orde yang setara jika setiap kali maka . Ketika maka pergeseran atas dari , dilambangkan , diperoleh dengan menambahkan 1 setiap non-negatif koordinat . Suatu relasi adalah agar invarian jika untuk setiap order invarian setara itu menyatakan bahwa . Suatu relasi$x, y \in Q^k$x i < x j ⇔ y i < y j x ∈ Q $1 \le i,j \le k$$x_i \lt x_j \Leftrightarrow y_i \lt y_j$$x \in Q^k$us ( x ) x A ⊆ Q $x$$\text{us}(x)$$x$$A \subseteq Q^k$ x ∈ A ⇔ y ∈ A R ⊆ Q k × Q $x,y \in Q^k$$x \in A \Leftrightarrow y \in A$$R \subseteq Q^k \times Q^k$adalah order invariant jika adalah invarian order sebagai bagian dari , dan secara ketat mendominasi jika untuk semua setiap kali maka . Lebih lanjut jika A adalah himpunan bagian dari Q ^ k maka R [A] menunjukkan \ {y | \ ada x \ dalam AR (x, y) \} , pergeseran atas A adalah \ text {us} (A) = \ {\ text {us} (x) | x \ dalam A \} , dan \ text {cube} (A, 0) menunjukkan paling sedikit B ^ k sehingga 0 \ dalam B dan A terkandung dalam B ^ k . MembiarkanQ 2 $R$$Q^{2k}$ R ( x , y ) maks ( x ) < maks ( y ) A Q k R [ A ] { y | ∃ x ∈ A R ( x , y ) } A us ( A ) = A , 0 ) B k 0 ∈ B A B $x,y \in Q^k$$R(x,y)$$\max(x) \lt \max(y)$$A$$Q^k$$R[A]$$\{ y | \exists x \in A R(x,y)\}$$A$kubus $\text{us}(A) = \{\text{us}(x) | x \in A\}$$\text{cube}(A,0)$$B^k$$0 \in B$$A$$B^k$$\text{SDOI}(Q^k,Q^k)$ menunjukkan himpunan dari semua hubungan invarian order yang sangat mendominasi $R \subseteq Q^k \times Q^k$ .

Sunting: Seperti yang Dömötör Pálvölgyi tunjukkan dalam komentar, menjadikan dan sebagai pemesanan yang biasa pada rasional tampaknya menghasilkan contoh tandingan. Pertama, himpunan tidak boleh kosong, karena kemudian juga kosong dan kemudian harus mengandung 0 oleh kondisi kubus, suatu kontradiksi. Jika himpunan non-kosong memiliki nilai maksimum maka tidak dapat berisi rasional yang lebih besar dari ini, sehingga harus berupa singleton, yang bertentangan dengan kondisi shift atas. Jika di sisi lain tidak memiliki infinite maka jadi harus kosong, sebuah kontradiksi. $k=1$$R$$A$$R[A]$$A$$A$$A$$R[A] = Q$$A$Adakah komentar tentang apakah ada masalah definisi tersembunyi yang tidak jelas, seperti mungkin model rasional tidak tersirat dari rasional?

Sunting lebih lanjut: Argumen di atas kira-kira benar, tetapi salah dalam penerapan shift atas. Operator ini hanya berlaku untuk koordinat non-negatif , sehingga pengaturan menjadi set singleton negatif menghasilkan titik tetap, seperti yang diinginkan. Dengan kata lain, jika maka adalah solusi, dan tidak ada solusi lain.$A$$m < 0$$A = \{m\}$

Saya tidak tahu konsekuensi apa pun dari teorema khusus ini, tetapi bukti normalisasi kalkulus lambda seperti kalkulus konstruksi induktif bergantung pada aksioma kardinal besar - meskipun himpunan istilah lambda dapat dihitung sebanyak yang Anda inginkan.

Saya pikir cara terbaik untuk memahami signifikansi komputasi dari aksioma set-theoretik yang menyatakan keberadaan kardinal besar adalah dengan memikirkan teori set sebagai cara menyusun teori grafik. Artinya, model dari himpunan adalah kumpulan elemen yang dilengkapi dengan hubungan biner yang digunakan untuk menginterpretasikan keanggotaan. Kemudian, aksioma teori himpunan memberi tahu Anda sifat-sifat hubungan keanggotaan, termasuk bagaimana Anda dapat membentuk set baru dari yang lama. Secara khusus, aksioma dasar berarti bahwa hubungan keanggotaan beralasan (yaitu, ia tidak memiliki rantai turun yang tak terbatas). Kebergantungan yang baik ini pada gilirannya berarti bahwa jika Anda dapat menyejajarkan status pelaksanaan suatu program dengan keanggotaan transitif dari elemen-elemen suatu set, maka Anda memiliki bukti terminasi.

Jadi pernyataan bahwa set "besar" ada memiliki hasil komputasi sebagai klaim bahwa kelas loop tertentu dalam bahasa pemrograman rekursif umum berakhir. Interpretasi ini bekerja secara seragam, mulai dari aksioma lama tak terbatas (yang membenarkan iterasi bilangan alami) sampai ke aksioma kardinal besar.

Apakah aksioma ini benar ? Nah, jika aksioma salah, Anda dapat menemukan program di salah satu kelas ini yang tidak berakhir. Tetapi jika itu benar, kita tidak akan pernah yakin, terima kasih pada teorinya Halting. Segala sesuatu mulai dari induksi bilangan alami adalah soal induksi ilmiah , yang mungkin selalu dipalsukan dengan eksperimen - Edward Nelson terkenal berharap untuk membuktikan bahwa eksponensial adalah fungsi parsial!