Przestrzeń topologiczna związana z SAT: czy jest zwarta?

Spełnialności problemem jest to, oczywiście, podstawowym problemem teoretycznym CS. Bawiłem się jedną wersją problemu z nieskończenie wieloma zmiennymi. $\newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}}$

Podstawowe ustawienia. Niech będzie niepustym i prawdopodobnie nieskończonym zestawem zmiennych . Dosłowność to albo zmienna albo jej negacja . Klauzula jest rozróżnieniem skończonej liczby literałów . Na koniec definiujemy formułę jako zestaw klauzul .$X$¬ x c$x \in X$$\neg x$$c$$F$

Przypisanie $X$ jest funkcją $\sigma : X \to \{0,1\}$ . Nie będę wyraźnie określać warunku, kiedy przypisanie $\sigma$ spełnia klauzulę; jest nieco nieporęczny i jest taki sam jak w standardowym SAT. Wreszcie zadanie spełnia formułę, jeśli spełnia każdą klauzulę składową. Niech $\sat(F)$ będzie zbiorem spełniających się zadań dla $F$ , a niech $\unsat(F)$ będzie dopełnieniem $\sat(F)$ .

Przestrzeń topologiczna.

Naszym celem jest nadanie przestrzeni wszystkich przydziałów $X$ , nazywając to $\Sigma$ , strukturą topologiczną . Nasze zamknięte zestawy mają postać $\sat(F)$ gdzie $F$ jest wzorem. Możemy zweryfikować, że jest to rzeczywiście topologia:

• Wszystkie formuły spełniają pustą formułę $\emptyset$ niezawierającą żadnych klauzul; więc $\Sigma$ jest zamknięta.
• Formuła $\{ x, \neg x \}$ dla dowolnego $x \in X$ jest sprzecznością. Więc $\emptyset$ jest zamknięty.
• Zamknięcie pod arbitralnym skrzyżowaniem. Załóżmy, jest preparatem dla każdego . Następnie . i ∈ I s a t ( ⋃ i ∈ I F i ) = ⋂ i ∈ I s a t ( F i$F_{i}$$i \in I$$\sat \left(\bigcup_{i \in I} F_i\right) = \bigcap_{i \in I} \sat(F_i)$
• Zamknięcie w ramach skończonej unii. Załóżmy, że $F$ i $G$ są dwiema formułami i definiują $$F \vee G := \{ c \vee d \,:\, c \in F, d \in G \}.$$ Następnie $\sat(F \vee G) = \sat(F) \cup \sat(G)$ To wymaga argumentu, ale pominę to.

Nazwij tę topologię $\mathcal T$ , „topologią satysfakcji” (!) Na $\Sigma$ . Oczywiście otwarte zestawy tej topologii mają postać $\unsat(F)$ . Co więcej, zaobserwowano, że zbiór zestawów otwartych

Kompaktowy? Uważam, że jest to interesujący, jeśli nie bardzo użyteczny sposób patrzenia na rzeczy. Chcę zrozumieć, czy ta przestrzeń topologiczna ma tradycyjne interesujące właściwości, takie jak zwartość, łączność itp. W tym poście ograniczymy się do zwartości:

Niech będzie niezliczoną liczbą zmiennych. ¹ Czy kompaktowy pod ?Σ $X$$\Sigma$$\mathcal T$

Można udowodnić, co następuje

Propozycja. jest zwarty, jeżeli i tylko dla preparatów unsatisfiable istnieje skończona unsatisfiable podstruktura .$\mathcal T$$F$$\{ c_1, c_2, \ldots, c_m \} \subseteq F$

(Niezbyt trudne ćwiczenie!) Po kilku dniach myślenia nie mam dużego postępu w udzielaniu odpowiedzi na to pytanie. Nie mam również silnych dowodów na zwartość lub przeciw zwartości. Czy możesz zasugerować jakieś podejście?

Wreszcie jako pytanie dodatkowe:

Czy taka struktura była wcześniej badana?

¹ Ograniczenie do policzalnego ma na celu uproszczenie; wydaje się także, że jest to kolejny naturalny krok od skończonej liczby zmiennych.$X$

To, co robisz, to uzyskiwanie topologicznej reprezentacji algebry boolowskiej. Badanie reprezentacji algeb Boolowskich sięga przynajmniej Lindenbauma i Tarskiego, którzy udowodnili (jak sądzę w 1925 r.), Że kompletne, atomowe algebry boolowskie są izomorficzne w stosunku do sieci powerset.

$x_1, x_1 \land x_2, \ldots$

Twierdzenie Stone'a o algebrach boolowskich Każda algebra boolowska jest izomorficzna z siecią kratownic podzbiorów przestrzeni topologicznej.

$\mathit{true}$

Kamienna przestrzeń algebry boolowskiej jest zwartą, całkowicie niepowiązaną przestrzenią Hausdorffa.

Było kilka wyników, które rozszerzają i uogólniają reprezentację Stone'a w różnych kierunkach. Naturalnym pytaniem jest pytanie, czy inne rodziny sieci mają takie reprezentacje. Wyniki Stone'a dotyczą również krat dystrybucyjnych. Topologiczne reprezentacje dla dowolnych sieci zostały przedstawione przez Alasdair Urquhart w 1978 roku. Sieci dystrybucyjne charakteryzują się większą różnorodnością w strukturze niż algebry logiczne i są bardzo interesujące. Inną reprezentację przypadku dystrybucyjnego podała Hilary Priestley w 1970 roku, wykorzystując ideę uporządkowanej przestrzeni topologicznej . Zamiast reprezentacji opartych na zestawach możemy znaleźć reprezentacje i topologie oparte na zestawach.

Konstrukcje w tych dokumentach mają jedną niezwykłą właściwość. Konstrukcja kamienia odwzorowuje nie tylko algebry boolowskie w przestrzeniach topologicznych: relacje strukturalne dotyczące algebry boolowskiej przekładają się na właściwości strukturalne między wynikowymi topologiami. Jest to dualność między kategoriami. Cała gama takich wyników nosi nazwę Stone Duality . Nieformalnie dualności dają nam precyzyjne tłumaczenia między wszechświatami matematycznymi: kombinatoryczny świat zbiorów, algebraiczny świat sieci, przestrzenny świat topologii i dedukcyjny świat logiki. Oto kilka punktów początkowych, które mogą pomóc.

1. Rozdział 11 wstępu do krat i porządku autorstwa Daveya i Priestleya obejmuje twierdzenie Stone'a.
2. Slajdy Matthew Gwynne obejmują twierdzenie i dają dowód zwartości. Matthew (w komentarzach) sugeruje również wprowadzenie do algebry logicznej Paula Halmosa.
3. Przechodząc od logiki zdań do logiki modalnej, algebra Boolean została rozszerzona o operator zachowujący łączenie i topologię z wnętrzem. Artykuł Jónssona i Tarskiego z 1952 roku, Boolean Algebras with Operators, jest niezwykle czytelny i zgodny ze współczesną notacją.
4. Rozdział 5 logiki modalnej autorstwa Blackburn, de Rijke i Venema omawia twierdzenie Stone'a i jego rozszerzenie na algebry logiczne wraz z operatorami.
5. Stone Spaces autorstwa Petera Johnstone'a przegląda takie wyniki dla różnych innych rodzajów algeb.