Ein topologischer Raum im Zusammenhang mit SAT: Ist er kompakt?

Das Erfüllbarkeit Problem ist natürlich, ein grundsätzliches Problem in der theoretischen CS. Ich habe mit einer Version des Problems mit unendlich vielen Variablen gespielt. $\newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}}$

Grundeinstellung. Sei eine nicht leere und möglicherweise unendliche Menge von Variablen . Ein Literal ist entweder eine Variable oder ihre Negation . Eine Klausel ist eine Disjunktion einer endlichen Anzahl von Literalen . Schließlich definieren wir eine Formel als eine Menge von Klauseln .$X$¬ x c$x \in X$$\neg x$$c$$F$

Eine Zuordnung von ist eine Funktion . Ich werde die Bedingung nicht explizit definieren, wenn eine Zuweisung eine Klausel erfüllt; Es ist etwas umständlich und entspricht dem Standard-SAT. Schließlich erfüllt eine Zuweisung eine Formel, wenn sie jede konstituierende Klausel erfüllt. Sei die Menge befriedigender Zuordnungen für und sei \ unsat (F) das Komplement von \ sat (F) .σ : X → { 0 , 1 } σ s a t ( F ) F u n s a t ( F ) s a t ( F $X$$\sigma : X \to \{0,1\}$$\sigma$$\sat(F)$$F$$\unsat(F)$$\sat(F)$

Ein topologischer Raum.

Unser Ziel ist es, den Raum aller Zuweisungen von $X$ , das heißt $\Sigma$ , mit einer topologischen Struktur auszustatten . Unsere geschlossenen Mengen haben die Form $\sat(F)$ wobei $F$ eine Formel ist. Wir können überprüfen, ob dies tatsächlich eine Topologie ist:

• Die leere Formel $\emptyset$ keine Klauseln enthält , wird von allen Aufgaben erfüllt; also ist $\Sigma$ geschlossen.
• Die Formel $\{ x, \neg x \}$ für ein beliebiges $x \in X$ ist ein Widerspruch. So $\emptyset$ ist geschlossen.
• Schließung unter willkürlicher Überschneidung. Angenommen $F_{i}$ ist eine Formel für jedes $i \in I$ . Dann ist $\sat \left(\bigcup_{i \in I} F_i\right) = \bigcap_{i \in I} \sat(F_i)$ .
• Schließung unter endlicher Vereinigung. Angenommen, $F$ und $G$ sind zwei Formeln und definieren $$F \vee G := \{ c \vee d \,:\, c \in F, d \in G \}.$$ Dann ist $\sat(F \vee G) = \sat(F) \cup \sat(G)$ Hierfür ist ein Argument erforderlich, das überspringe ich jedoch.

Nennen Sie diese Topologie $\mathcal T$ , die "Erfüllbarkeitstopologie" (!) In $\Sigma$ . Natürlich haben die offenen Mengen dieser Topologie die Form \ unsat (F)$\unsat(F)$ . Außerdem habe ich festgestellt, dass die Sammlung offener Mengen

Kompakt? Ich halte dies für eine interessante, wenn nicht sogar fürchterlich nützliche Betrachtungsweise. Ich möchte verstehen, ob dieser topologische Raum traditionelle interessante Eigenschaften wie Kompaktheit, Verbundenheit usw. besitzt. In diesem Beitrag beschränken wir uns auf Kompaktheit:

Sei eine unendlich zählbare Sammlung von Variablen. ¹ Ist compact unter ?$X$$\Sigma$$\mathcal T$

Man kann folgendes beweisen

Vorschlag. ist kompakt, wenn und nur für alle nicht erfüllbaren Formeln eine endliche nicht erfüllbare Unterformel .$\mathcal T$$F$$\{ c_1, c_2, \ldots, c_m \} \subseteq F$

(Nicht so harte Übung!) Nach einigen Tagen des Nachdenkens habe ich keine großen Fortschritte bei der Beantwortung dieser Frage. Ich habe auch keine starken Beweise für oder gegen Kompaktheit. Können Sie einen Ansatz vorschlagen?

Zum Schluss als Bonusfrage:

Wurde eine solche Struktur schon einmal untersucht?

¹ Die Beschränkung auf zählbares dient nur der Vereinfachung. es fühlt sich auch wie der nächste natürliche Schritt aus einer endlichen Anzahl von Variablen an.$X$

Sie leiten eine topologische Darstellung einer Booleschen Algebra ab. Das Studium der Darstellungen von Booleschen Algebren geht zumindest auf Lindenbaum und Tarski zurück, die (glaube ich) 1925 bewiesen haben, dass die vollständigen atomaren Booleschen Algebren isomorph zu Powerset-Gittern sind.

Es gibt jedoch Boolesche Algebren, die nicht vollständig und atomar sind. Beispielsweise ist die Folge eine absteigende Kette, für die in der über Formeln definierten Booleschen Algebra keine Beschränkung besteht. Die Frage, ob beliebige Boolesche Algebren, wie die von Ihnen erwähnte, auch satzbasierte Darstellungen hatten, wurde von Marshall Stone gelöst , der die Maxime "Immer topologisieren" aufstellte (Marshall H. Stone. Die Darstellung von Booleschen Algebren , 1938). .$x_1, x_1 \land x_2, \ldots$

Stones Darstellungssatz für Boolesche Algebren Jede Boolesche Algebra ist isomorph zum Gitter geschlossener Teilmengen eines topologischen Raums.

Die Hauptidee ist zu überlegen, was in Ihrem Fall die zufriedenstellenden Zuordnungen zu einer Formel sind. Im allgemeinen Fall betrachten Sie Homomorphismen aus einer Booleschen Algebra in die Boolesche Algebra mit zwei Elementen (die Wahrheitswerte). Die Inverse von Sie die Sätze von erfüllenden Belegungen gibt, oder was Ultra der Boolesche Algebra genannt. Aus diesen kann man eine Topologie erhalten, die als Spektrum oder Steinraum einer Booleschen Algebra bezeichnet wird. Stone liefert auch die Antwort auf Ihre Frage.$\mathit{true}$

Der Steinraum einer Booleschen Algebra ist ein kompakter, völlig unverbundener Hausdorff-Raum.

Es gibt mehrere Ergebnisse, die die Darstellung von Stone in verschiedene Richtungen erweitern und verallgemeinern. Eine natürliche Frage ist, ob andere Gitterfamilien solche Darstellungen haben. Stones Ergebnisse gelten auch für Verteilungsgitter. Topologische Darstellungen für beliebige Gitter wurden 1978 von Alasdair Urquhart gegeben. Verteilungsgitter weisen im Vergleich zu Booleschen Algebren eine größere Strukturvielfalt auf und sind von großem Interesse. Eine andere Darstellung für den Verteilungsfall wurde 1970 von Hilary Priestley unter Verwendung der Idee eines geordneten topologischen Raums gegeben . Anstelle von satzbasierten Darstellungen finden wir posetbasierte Darstellungen und Topologien.

Die Konstruktionen in diesen Papieren haben eine bemerkenswerte Eigenschaft. Die Konstruktion von Stone ordnet nicht nur Boolesche Algebren topologischen Räumen zu: Strukturelle Beziehungen, die Boolesche Algebren betreffen, führen zu strukturellen Eigenschaften zwischen den resultierenden Topologien. Es ist eine Dualität zwischen Kategorien. Die gesamte Bandbreite solcher Ergebnisse wird als Stone Duality bezeichnet . Inoffiziell liefern Dualitäten präzise Übersetzungen zwischen mathematischen Universen: der kombinatorischen Welt der Mengen, der algebraischen Welt der Gitter, der räumlichen Welt der Topologie und der deduktiven Welt der Logik. Hier sind einige Ansatzpunkte, die hilfreich sein können.

1. Kapitel 11 der Einführung in Gitter und Ordnung von Davey und Priestley behandelt Stones Theorem.
2. Die Folien von Matthew Gwynne decken den Satz ab und geben einen Beweis für die Kompaktheit. Matthäus (in den Kommentaren) schlägt auch eine Einführung in die Booleschen Algebren von Paul Halmos vor.
3. Beim Übergang von der Aussagenlogik zur Modallogik wird die Boolesche Algebra um einen Verknüpfungserhaltungsoperator und eine Topologie mit einem Innenraum erweitert. Die Booleschen Algebren mit Operatoren aus dem Jahr 1952 von Jónsson und Tarski sind äußerst lesbar und stimmen mit der modernen Notation überein.
4. Kapitel 5 der Modal Logic von Blackburn, de Rijke und Venema befasst sich mit Stones Theorem und seiner Erweiterung auf Boolesche Algebren mit Operatoren.
5. Stone Spaces von Peter Johnstone überprüft solche Ergebnisse für verschiedene andere Arten von Algebren.