Ruang topologi terkait dengan SAT: apakah kompak?

Masalah Kepuasan , tentu saja, masalah mendasar dalam CS teoritis. Saya bermain dengan satu versi masalah dengan banyak sekali variabel. $\newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}}$

Pengaturan Dasar. Biarkan $X$ menjadi seperangkat variabel bebas dan mungkin tak terbatas . Literal adalah variabel $x \in X$ atau negasi $\neg x$ . Klausa $c$ adalah disjungsi dari jumlah literal yang terbatas . Akhirnya, kami mendefinisikan rumus $F$ sebagai satu set klausa .

Tugas $X$ adalah fungsi $\sigma : X \to \{0,1\}$ . Saya tidak akan secara eksplisit menentukan kondisi saat suatu penugasan $\sigma$ memenuhi klausa; itu sedikit rumit, dan sama seperti pada SAT standar. Akhirnya, sebuah tugas memenuhi formula jika memenuhi setiap klausa konstituen. Biarkan $\sat(F)$ menjadi himpunan tugas yang memuaskan untuk $F$ , dan biarkan $\unsat(F)$ menjadi pelengkap $\sat(F)$ .

Ruang topologi.

Tujuan kami adalah untuk memberikan ruang pada semua penugasan $X$ , sebut ini $\Sigma$ , dengan struktur topologi . Set tertutup kami adalah dari bentuk $\sat(F)$ mana $F$ adalah rumus. Kami dapat memverifikasi bahwa ini memang topologi:

• Formula kosong $\emptyset$ yang tidak mengandung klausa dipenuhi oleh semua tugas; jadi $\Sigma$ ditutup.
• Rumus $\{ x, \neg x \}$ untuk setiap $x \in X$ adalah sebuah kontradiksi. Jadi $\emptyset$ ditutup.
• Penutupan di bawah persimpangan sewenang-wenang. Misalkan $F_{i}$ adalah formula untuk setiap $i \in I$ . Kemudian $\sat \left(\bigcup_{i \in I} F_i\right) = \bigcap_{i \in I} \sat(F_i)$ .
• Penutupan di bawah serikat terbatas. Misalkan $F$ dan $G$ adalah dua rumus, dan tentukan $$F \vee G := \{ c \vee d \,:\, c \in F, d \in G \}.$$ Kemudian $\sat(F \vee G) = \sat(F) \cup \sat(G)$ . Ini membutuhkan argumen, tapi saya akan melewatkan ini.

Sebutkan topologi ini $\mathcal T$ , "topologi kepuasan" (!) Di $\Sigma$ . Tentu saja, set terbuka topologi ini adalah dalam bentuk $\unsat(F)$ . Selain itu, saya mengamati bahwa koleksi set terbuka

Kompak? Saya merasa ini cara yang menarik, jika tidak terlalu berguna, untuk melihat sesuatu. Saya ingin memahami apakah ruang topologi ini memiliki sifat menarik tradisional seperti kekompakan, keterhubungan dll. Dalam posting ini, kita akan membatasi diri kita pada kekompakan:

Biarkan menjadi kumpulan variabel yang tak terhingga jumlahnya. ¹ Apakah ringkas di bawah ?Σ $X$$\Sigma$$\mathcal T$

Seseorang dapat membuktikan hal berikut

Dalil. kompak jika dan hanya untuk semua formula unsatisfiable , terdapat subformula terbatas unsatisfiable . F { c 1 , c 2 , … , c m } ⊆ $\mathcal T$$F$$\{ c_1, c_2, \ldots, c_m \} \subseteq F$

(Latihan yang tidak terlalu sulit!) Setelah beberapa hari berpikir, saya tidak memiliki banyak kemajuan dalam menjawab pertanyaan ini. Saya juga tidak memiliki bukti kuat untuk atau menentang kekompakan. Bisakah Anda menyarankan beberapa pendekatan?

Akhirnya, sebagai pertanyaan bonus:

Apakah struktur seperti itu telah dipelajari sebelumnya?

¹ Pembatasan untuk menghitung hanya untuk kesederhanaan; itu juga terasa seperti langkah alami berikutnya dari jumlah variabel terbatas.$X$

Apa yang Anda lakukan adalah mendapatkan representasi topologi dari aljabar Boolean. Studi tentang representasi aljabar Boolean kembali setidaknya ke Lindenbaum dan Tarski yang membuktikan (pada tahun 1925, saya pikir) bahwa aljabar Boolean atom yang lengkap adalah isomorfik untuk kisi-kisi penyetelan.

Namun ada, aljabar Boolean yang tidak lengkap dan atom. Sebagai contoh, urutan , adalah rantai menurun yang tidak memiliki batas dalam aljabar Boolean yang didefinisikan di atas rumus. Pertanyaan apakah aljabar Boolean yang sewenang-wenang, seperti yang Anda sebutkan, juga memiliki representasi berbasis set diselesaikan oleh Marshall Stone , yang mengemukakan pepatah "selalu melakukan topologi" (Marshall H. Stone. Representasi aljabar Boolean , 1938) .$x_1, x_1 \land x_2, \ldots$

Teorema Representasi Batu untuk Aljabar Boolean Setiap aljabar Boolean bersifat isomorfik terhadap kisi himpunan bagian himpunan bagian dari ruang topologis.

Gagasan utamanya adalah mempertimbangkan apa yang dalam kasus Anda merupakan penugasan yang memuaskan untuk suatu formula. Dalam kasus umum, Anda mempertimbangkan homomorfisme dari aljabar Boolean ke dalam dua elemen Aljabar Boolean (nilai kebenaran). Kebalikan dari memberi Anda set tugas yang memuaskan, atau apa yang disebut ultrafilters dari aljabar Boolean. Dari ini, seseorang dapat memperoleh topologi yang disebut spektrum atau ruang Batu dari aljabar Boolean. Stone juga memberikan jawaban untuk pertanyaan Anda.$\mathit{true}$

Ruang Stone dari aljabar Boolean adalah ruang Hausdorff yang kompak dan benar-benar terputus.

Ada beberapa hasil yang memperluas dan menggeneralisasi representasi Stone ke berbagai arah. Pertanyaan yang wajar adalah menanyakan apakah keluarga kisi lain memiliki representasi seperti itu. Hasil Stone juga berlaku untuk kisi distributif. Representasi topologis untuk kisi-kisi sewenang-wenang diberikan oleh Alasdair Urquhart pada tahun 1978. Kisi distributif menikmati keragaman yang lebih besar dalam struktur, dibandingkan dengan aljabar Boolean dan sangat menarik. Representasi yang berbeda untuk kasus distributif diberikan oleh Hilary Priestley pada tahun 1970, menggunakan ide ruang topologi yang teratur . Alih-alih representasi berbasis set, kita dapat menemukan representasi dan topologi berbasis poset.

Konstruksi dalam makalah ini memiliki satu properti yang luar biasa. Konstruksi batu memetakan tidak hanya aljabar Boolean ke ruang topologi: hubungan struktural yang terkait Aljabar Boolean diterjemahkan ke dalam sifat struktural antara topologi yang dihasilkan. Ini adalah dualitas antar kategori. Keseluruhan hasil tersebut disebut Dualitas Batu . Secara informal, dualitas memberi kita terjemahan yang tepat antara alam semesta matematika: dunia kombinatorial, dunia kisi aljabar, dunia topologi spasial dan dunia deduktif logika. Berikut adalah beberapa poin awal yang dapat membantu.

1. Bab 11 Pengantar Kisi dan Ketertiban , oleh Davey dan Priestley membahas teorema Stone.
2. Slide Matthew Gwynne menutupi teorema dan memberikan bukti kekompakan. Matius (dalam komentar) juga menyarankan Pengantar Boolean Algebras oleh Paul Halmos.
3. Dalam bergerak dari logika proposisional ke logika modal, aljabar Boolean diperluas dengan operator pengawet gabungan dan topologi dengan interior. Karya Jónsson dan Tarski tahun 1952, Boolean Algebras with Operators sangat mudah dibaca dan konsisten dengan notasi modern.
4. Bab 5 Modal Logic oleh Blackburn, de Rijke dan Venema mencakup teorema Stone dan perluasannya ke aljabar Boolean dengan operator.
5. Stone Spaces oleh Peter Johnstone ulasan hasil tersebut untuk berbagai jenis aljabar lainnya.