Teorema menarik mana di TCS yang mengandalkan Axiom of Choice? (Atau alternatifnya, Aksioma Penentuan?)

Matematikawan terkadang khawatir tentang Aksioma Pilihan (AC) dan Aksioma Penentuan (AD).

Aksioma of Choice : Mengingat setiap koleksi dari set tidak kosong, ada fungsi f yang, diberikan satu set S di C , mengembalikan anggota dari S .${\cal C}$$f$$S$${\cal C}$$S$

Aksioma Penentuan : Biarkan menjadi seperangkat string bit panjang tak terhingga. Alice dan Bob memainkan permainan di mana Alice mengambil bit 1 b 1 , Bob mengambil bit 2 b 2 , dan seterusnya, hingga string tak terbatas x = b 1 b 2 ⋯ dibuat. Alice memenangkan permainan jika x ∈ S , Bob memenangkan pertandingan jika x ∉ S . Asumsinya adalah bahwa untuk setiap S , ada strategi kemenangan untuk salah satu pemain. (Misalnya, jika S hanya terdiri dari string semua-yang, Bob bisa menang dalam banyak gerakan.)$S$$b_1$$b_2$$x = b_1 b_2 \cdots$$x \in S$$x \not \in S$ $S$$S$

Diketahui bahwa kedua aksioma ini tidak konsisten satu sama lain. (Pikirkan tentang itu, atau pergi ke sini .)

Matematikawan lain hanya sedikit atau tidak memperhatikan penggunaan aksioma ini sebagai bukti. Mereka tampaknya hampir tidak relevan dengan ilmu komputer teoretis, karena kami percaya bahwa kami bekerja sebagian besar dengan objek yang terbatas. Namun, karena TCS mendefinisikan masalah keputusan komputasi sebagai string bit tak terbatas, dan kami mengukur (misalnya) kompleksitas waktu suatu algoritma sebagai fungsi asimptotik di atas natural, selalu ada kemungkinan bahwa penggunaan salah satu aksioma ini dapat merambat. menjadi beberapa bukti.

Apa contoh paling mencolok dalam TCS yang Anda tahu di mana aksioma ini diperlukan ? (Apakah Anda tahu ada contoh?)

Hanya untuk sedikit pertanda, perhatikan bahwa argumen diagonalisasi (lebih dari set semua mesin Turing, katakanlah) bukan aplikasi dari Aksioma Pilihan. Meskipun bahasa yang didefinisikan oleh mesin Turing adalah string bit tak terbatas, setiap mesin Turing memiliki deskripsi terbatas, jadi kami benar-benar tidak memerlukan fungsi pilihan untuk banyak set tak terbatas di sini.

(Saya menaruh banyak tag karena saya tidak tahu dari mana contoh itu berasal.)

Pernyataan aritmatika apa pun yang dapat dibuktikan dalam ZFC dapat dibuktikan dalam ZF, dan karenanya tidak "memerlukan" aksioma pilihan. Dengan pernyataan "aritmatika" yang saya maksud adalah pernyataan dalam bahasa aritmatika tingkat pertama, yang berarti bahwa itu dapat dinyatakan hanya dengan menggunakan bilangan pengukur atas bilangan asli ("untuk semua bilangan asli x" atau "ada bilangan asli x"), tanpa menghitung lebih dari set bilangan alami. Sepintas mungkin tampak sangat membatasi untuk melarang kuantifikasi atas set bilangan bulat; Namun, himpunan bilangan bulat terbatas dapat "dikodekan" menggunakan bilangan bulat tunggal, jadi tidak apa-apa untuk mengkuantifikasi himpunan bilangan bulat berhingga.

$P\ne NP$

Tetapi tunggu, Anda dapat mengatakan, bagaimana dengan pernyataan aritmatika yang buktinya memerlukan sesuatu seperti lemma Koenig atau teorema pohon Kruskal? Tidakkah ini membutuhkan bentuk aksioma pilihan yang lemah? Jawabannya adalah bahwa itu tergantung pada bagaimana Anda menyatakan hasil dalam pertanyaan. Sebagai contoh, jika Anda menyatakan teorema minor minor dalam bentuk, "mengingat setiap set grafik tak berlabel yang tak terbatas, harus ada dua di antaranya sehingga satu adalah minor dari yang lain," maka sejumlah pilihan diperlukan untuk berbaris melalui set data Anda yang tak terbatas, memilih simpul, subgraf, dll. [EDIT: Saya membuat kesalahan di sini. Seperti yang dijelaskan oleh Emil Jeřábek, teorema minor minor — atau paling tidak pernyataan paling alami dari ketiadaan AC — dapat dibuktikan dalam ZF. Tapi kesalahan modulo ini, apa yang saya katakan di bawah ini pada dasarnya masih benar. ] Namun, jika sebaliknya Anda menuliskan pengodean tertentu dengan bilangan alami dari hubungan minor pada graf berhingga berlabel, dan frasa teorema minor graf sebagai pernyataan tentang urutan parsial tertentu ini, maka pernyataan tersebut menjadi aritmetika dan tidak memerlukan AC dalam bukti.

Kebanyakan orang merasa bahwa "esensi kombinatorial" dari teorema minor graph sudah ditangkap oleh versi yang memperbaiki pengkodean tertentu, dan bahwa kebutuhan untuk memanggil AC untuk melabeli semuanya, jika Anda dihadapkan dengan set-general yang umum. versi teoretis dari masalah, adalah semacam artefak yang tidak relevan dari keputusan untuk menggunakan teori himpunan daripada aritmatika sebagai landasan logis seseorang. Jika Anda merasakan hal yang sama, maka teorema minor minor tidak memerlukan AC. (Lihat juga posting ini oleh Ali Enayat ke Yayasan Milis Matematika, yang ditulis sebagai jawaban atas pertanyaan serupa yang pernah saya miliki.)

Contoh bilangan kromatik dari pesawat adalah juga masalah interpretasi. Ada berbagai pertanyaan yang dapat Anda ajukan yang ternyata setara jika Anda menganggap AC, tetapi merupakan pertanyaan berbeda jika Anda tidak menganggap AC. Dari sudut pandang TCS, inti kombinatorial dari pertanyaan adalah warna dari subgraph yang terbatas pada pesawat, dan fakta bahwa Anda kemudian dapat (jika Anda mau) menggunakan argumen kekompakan (di sinilah AC masuk) untuk menyimpulkan sesuatu tentang jumlah kromatik dari seluruh bidang lucu, tetapi agak menarik minat. Jadi saya tidak berpikir ini adalah contoh yang sangat bagus.

Saya pikir pada akhirnya Anda mungkin lebih beruntung bertanya apakah ada pertanyaan TCS yang memerlukan aksioma kardinal besar untuk resolusi mereka (daripada AC). Karya Harvey Friedman telah menunjukkan bahwa pernyataan keuangan tertentu dalam teori grafik dapat memerlukan aksioma kardinal besar (atau setidaknya konsistensi 1 aksioma semacam itu). Contoh-contoh Friedman sejauh ini sedikit buatan, tetapi saya tidak akan terkejut melihat contoh serupa muncul "secara alami" di TCS dalam hidup kita.

Pemahaman saya adalah bahwa bukti yang diketahui untuk teorema Robertson-Seymour menggunakan Aksioma Pilihan (melalui teorema pohon Kruskal). Ini sangat menarik dari sudut pandang TCS, karena teorema Robertson-Seymour menyiratkan bahwa pengujian keanggotaan dalam keluarga kecil tertentu dari grafik dapat dilakukan dalam waktu polinomial. Dengan kata lain, Aksioma Pilihan dapat digunakan secara tidak langsung untuk membuktikan bahwa algoritma waktu polinom ada untuk masalah tertentu, tanpa benar-benar membangun algoritma tersebut.

Ini mungkin, meskipun, tidak persis apa yang Anda cari, karena tidak jelas apakah AC sebenarnya diperlukan di sini.

Ini berkaitan dengan jawaban yang diberikan oleh Janne Korhonen.

Ada aliran hasil di tahun 80-an dan 90-an yang mencoba untuk mengkarakterisasi sistem aksioma (dengan kata lain, teori aritmatika) yang diperlukan untuk membuktikan perluasan Teorema Kruskal Tree (KTT; KTT asli dari 1960). Secara khusus, Harvey Friedman membuktikan beberapa hasil mengikuti garis ini (lihat SG Simpson. Non-provabilitas properti kombinatorial tertentu dari pohon hingga . Di LA Harrington et al., Editor, Harvey Friedman, Research on Foundations of Mathematics. Elsevier, North-Holland, 1985) . Hasil ini menunjukkan bahwa (ekstensi tertentu) KTT harus menggunakan Aksioma Pemahaman "kuat" (yaitu, aksioma yang mengatakan bahwa set kerumitan logis tinggi tertentu ada). Saya tidak tahu persis tentang kemampuan ekstensi KTT di ZF (tanpa aksioma pilihan).

Sejalan dengan aliran hasil ini, ada upaya untuk menghubungkannya ke TCS ("Teori B") melalui sistem penulisan ulang . Idenya adalah untuk membangun sistem penulisan ulang (menganggapnya sebagai semacam pemrograman fungsional, atau program lambda-kalkulus) yang pemutusan mereka bergantung pada (ekstensi) KTT tertentu (koneksi asli antara KTT dan pemutusan sistem penulisan dibuktikan oleh N Dershowitz (1982)). Ini menyiratkan bahwa untuk menunjukkan bahwa program-program tertentu mengakhiri seseorang perlu aksioma yang kuat (karena ekstensi KTT membutuhkan aksioma semacam itu). Untuk jenis hasil ini, lihat misalnya A. Weiermann, Batas kompleksitas untuk beberapa bentuk teorema Kruskal yang terbatas , Journal of Symbolic Computation 18 (1994), 463-488.

${\mathbb R}^2$

Dalam Shelah dan Soifer, "Aksioma pilihan dan jumlah kromatik pesawat," ditunjukkan bahwa jika semua subgraph yang terbatas dari pesawat adalah empat-kromatik, maka

• Jika Anda mengasumsikan aksioma pilihan, maka bidangnya empat-berwarna.
• Jika Anda mengasumsikan prinsip pilihan tergantung dan bahwa semua set Lebesgue dapat diukur, maka bidangnya lima, enam, atau tujuh berwarna.

Beberapa karya Olivier Finkel tampaknya terkait dengan pertanyaan --- meskipun tidak harus secara eksplisit tentang Aksioma Pilihan itu sendiri --- dan sejalan dengan jawaban Timothy Chow. Misalnya, mengutip abstrak Teorema Ketidaklengkapan, Kardinal Besar, dan Automata atas Kata-kata Hingga , TAMC 2017 ,

$T_n := ZFC + \text{``There exist (at least) $n$ inaccessible cardinals''}$$n \geq 0$

[Ini bukan jawaban langsung untuk pertanyaan Anda, namun itu mungkin sugestif dan / atau informatif bagi sebagian orang.]

Polling P vs NP William Gasarch memberikan beberapa statistik tentang "bagaimana P vs NP akan diselesaikan":

1. 61 pikir P ≠ NP.
2. 9 pikir P = NP.
3. 4 berpikir bahwa itu independen . Sementara tidak ada sistem aksioma tertentu yang disebutkan, saya menganggap mereka berpikir itu tidak bergantung pada ZFC .
4. 3 hanya menyatakan bahwa itu TIDAK independen dari Aritmatika Rekursif Primitif.
5. 1 mengatakan itu akan tergantung pada model.
6. 22 tidak memberikan pendapat.

Wikipedia memiliki pandangan yang menarik tentang kemerdekaan:

... Rintangan ini juga membuat beberapa ilmuwan komputer menyarankan bahwa masalah P versus NP mungkin tidak tergantung pada sistem aksioma standar seperti ZFC (tidak dapat dibuktikan atau dibantah di dalamnya). Interpretasi hasil independensi dapat berupa bahwa tidak ada algoritma waktu polinomial yang ada untuk masalah NP-complete, dan bukti seperti itu tidak dapat dikonstruksikan dalam (misalnya) ZFC, atau bahwa algoritma waktu polinomial untuk masalah NP-complete mungkin ada, tetapi tidak mungkin untuk membuktikan di ZFC bahwa algoritma tersebut benar [ 1] Namun, jika dapat ditunjukkan, menggunakan teknik semacam itu yang saat ini diketahui berlaku, bahwa masalah tidak dapat diputuskan bahkan dengan asumsi yang jauh lebih lemah memperluas aksioma Peano (PA) untuk aritmatika bilangan bulat, maka harus ada hampir algoritma polinomial-waktu untuk setiap masalah dalam NP [ 2 ]. Oleh karena itu, jika seseorang percaya (seperti kebanyakan teori kompleksitas lakukan) bahwa tidak semua masalah dalam NP memiliki algoritma yang efisien, itu akan mengikuti bahwa bukti independensi menggunakan teknik-teknik tersebut tidak mungkin dilakukan. Selain itu, hasil ini menyiratkan bahwa membuktikan independensi dari PA atau ZFC menggunakan teknik yang dikenal saat ini tidak lebih mudah daripada membuktikan keberadaan algoritma yang efisien untuk semua masalah dalam NP.

$ZF$

$G$$\chi(H)$$H$$G$$G$

$ZF$