Un espacio topológico relacionado con SAT: ¿es compacto?

El problema de la satisfacción es, por supuesto, un problema fundamental en la CS teórica. Estaba jugando con una versión del problema con infinitas variables. $\newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}}$

Configuración básica. Sea un conjunto de variables no vacío y posiblemente infinito . Un literal es una variable o su negación . Una cláusula es una disyunción del número finito de literales . Finalmente, definimos una fórmula como un conjunto de cláusulas .$X$¬ x c$x \in X$$\neg x$$c$$F$

Una asignación de es una función . No definiré explícitamente la condición para cuando una asignación satisface una cláusula; es un poco engorroso y es lo mismo que en el SAT estándar. Finalmente, una asignación satisface una fórmula si satisface todas las cláusulas constituyentes. Sea el conjunto de asignaciones satisfactorias para F , y sea \ unsat (F) el complemento de \ 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)$

Un espacio topológico.

Nuestro objetivo es dotar al espacio de todas las asignaciones de $X$ , llame a esto $\Sigma$ , con una estructura topológica . Nuestros conjuntos cerrados tienen la forma $\sat(F)$ donde $F$ es una fórmula. Podemos verificar que esta es realmente una topología:

• La fórmula vacía $\emptyset$ que no contiene cláusulas es satisfecha por todas las asignaciones; entonces $\Sigma$ está cerrado.
• La fórmula $\{ x, \neg x \}$ para cualquier $x \in X$ es una contradicción. Entonces $\emptyset$ está cerrado.
• Cierre bajo intersección arbitraria. Supongamos es una fórmula para cada . Entonces . 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)$
• Cierre bajo unión finita. Suponga que $F$ y $G$ son dos fórmulas, y defina $$F \vee G := \{ c \vee d \,:\, c \in F, d \in G \}.$$ Entonces $\sat(F \vee G) = \sat(F) \cup \sat(G)$ . Esto necesita un argumento, pero me saltearé esto.

Llame a esta topología $\mathcal T$ , la "topología de satisfacción" (!) En $\Sigma$ . Por supuesto, los conjuntos abiertos de esta topología tienen la forma \ unsat (F)$\unsat(F)$ . Además, he observado que la colección de conjuntos abiertos

¿Compacto? Siento que esta es una forma interesante, si no terriblemente útil, de ver las cosas. Quiero entender si este espacio topológico posee propiedades tradicionales interesantes como compacidad, conectividad, etc. En esta publicación, nos limitaremos a la compacidad:

Dejemos que sea ​​una colección infinitamente contable de variables. ¹ ¿Es compacto bajo ?$X$$\Sigma$$\mathcal T$

Uno puede probar lo siguiente

Proposición. es compacto si y sólo para todas las fórmulas unsatisfiable , existe una subfórmula finita unsatisfiable .$\mathcal T$$F$$\{ c_1, c_2, \ldots, c_m \} \subseteq F$

(¡Ejercicio no tan duro!) Después de varios días de pensar, no tengo mucho progreso para responder esta pregunta. Tampoco tengo pruebas sólidas a favor o en contra de la compacidad. ¿Puedes sugerir algún enfoque?

Finalmente, como una pregunta extra:

¿Se ha estudiado tal estructura antes?

¹ La restricción a contable es solo por simplicidad; También se siente como el siguiente paso natural de un número finito de variables.$X$

Lo que está haciendo es derivar una representación topológica de un álgebra booleana. El estudio de las representaciones de álgebras booleanas se remonta al menos a Lindenbaum y Tarski, quienes probaron (en 1925, creo) que las álgebras booleanas atómicas completas son isomorfas a redes reticuladas.

Sin embargo, hay álgebras booleanas que no son completas y atómicas. Por ejemplo, la secuencia , es una cadena descendente que no tiene límite en el álgebra booleana definida sobre las fórmulas. Marshall Stone , quien propuso la máxima "siempre topologizar" (Marshall H. Stone. La representación de álgebras booleanas , 1938) resolvió la cuestión de si las álgebras booleanas arbitrarias, como la que usted menciona, también tenía representaciones basadas en conjuntos . .$x_1, x_1 \land x_2, \ldots$

Teorema de la representación de Stone para álgebras booleanas Cada álgebra booleana es isomorfa a la red de subconjuntos de clopen de un espacio topológico.

La idea principal es considerar cuáles son las asignaciones satisfactorias de una fórmula en su caso. En el caso general, considera los homomorfismos de un álgebra booleana en el álgebra booleana de dos elementos (los valores de verdad). El inverso de le proporciona los conjuntos de asignaciones satisfactorias, o lo que se llama ultrafiltros del álgebra booleana. A partir de estos, se puede obtener una topología llamada espectro o espacio de piedra de un álgebra booleana. Stone también proporciona la respuesta a su pregunta.$\mathit{true}$

El espacio de piedra de un álgebra booleana es un espacio de Hausdorff compacto y totalmente desconectado.

Ha habido varios resultados que amplían y generalizan la representación de Stone en varias direcciones. Una pregunta natural es preguntar si otras familias de redes tienen tales representaciones. Los resultados de Stone también se aplican a las redes distributivas. Alasdair Urquhart dio representaciones topológicas para redes arbitrarias en 1978. Las redes distributivas disfrutan de una mayor diversidad en la estructura, en comparación con las álgebras booleanas y son de gran interés. Hilary Priestley dio una representación diferente para el caso distributivo en 1970, utilizando la idea de un espacio topológico ordenado . En lugar de representaciones basadas en conjuntos, podemos encontrar representaciones y topologías basadas en poset.

Las construcciones en estos documentos tienen una propiedad notable. La construcción de Stone no solo asigna álgebras booleanas a espacios topológicos: las relaciones estructurales que relacionan álgebras booleanas se traducen en propiedades estructurales entre las topologías resultantes. Es una dualidad entre categorías. Toda la gama de tales resultados se llama Stone Duality . Informalmente, las dualidades nos dan traducciones precisas entre universos matemáticos: el mundo combinatorio de los conjuntos, el mundo algebraico de las redes, el mundo espacial de la topología y el mundo deductivo de la lógica. Aquí hay algunos puntos de partida que pueden ayudar.

1. El capítulo 11 de Introducción a los enrejados y el orden , de Davey y Priestley, cubre el teorema de Stone.
2. Las diapositivas de Matthew Gwynne cubren el teorema y dan una prueba de compacidad. Matthew (en los comentarios) también sugiere Introducción a las álgebras booleanas de Paul Halmos.
3. Al pasar de la lógica proposicional a la lógica modal, el álgebra booleana se extiende con un operador de preservación de unión y una topología con un interior. El artículo de Jónsson y Tarski de 1952, Boolean Algebras with Operators es extremadamente legible y consistente con la notación moderna.
4. El Capítulo 5 de Modal Logic de Blackburn, de Rijke y Venema cubre el teorema de Stone y su extensión a álgebras booleanas con operadores.
5. Stone Spaces por Peter Johnstone revisa dichos resultados para varios otros tipos de álgebras.