El teorema de la coloración implica el teorema de la compacidad

Question

Teorema de la compacidad : Dejemos que $\Sigma$ sea un conjunto de fórmulas. Si todo subconjunto finito de $\Sigma$ tiene una realización entonces $\Sigma$ también tiene una realización.

Definición[Realización] : Dejemos que $\Sigma$ sea un conjunto de fórmulas, $S_\Sigma\subset\mathcal{P}$ sea el conjunto de frases que aparecen en $\Sigma$ . $f^*:\Phi\to \{0,1\}$ donde $\Phi$ es un conjunto de fórmulas y $f^*(\phi\wedge\psi)=f^*(\phi)f^*(\psi)$ , $f^*(\phi\lor\psi)=\max\{\phi,\psi\}$ , $f^*(\lnot\phi)=1-f^*(\phi)$ y para todos $\phi\in \Sigma$ tenemos $f^*(\phi)=1$ . $f:S_\Sigma\to \{0,1\},p\mapsto f^*(p)$ se llama una realización de $\Sigma$ .

Teorema de la coloración : Todo grafo que tiene todos los subgrafos finitos que son coloreables a 3 bandas es coloreable a 3 bandas.

¿Cómo implica el teorema de la coloración el teorema de la compacidad?

Answer 1

Se trata de una cuestión interesante, ya que normalmente se demuestra lo contrario, es decir, que el teorema de la compacidad (para la lógica proposicional) implica el teorema de los 3 colores.

Para ir en sentido contrario, tenemos que construir un gráfico a partir del conjunto de fórmulas. Empezamos con un triángulo con vértices $S_0,S_1,S_2$ . Podemos suponer que cualquier $3$ -el coloreado los coloreará $0,1,2$ respectivamente. Añade un vértice para cada variable y añade una arista desde ella hasta $S_2$ . Entonces cada variable será coloreada $0$ o $1$ , que por supuesto interpretaremos como valores de verdad. Es fácil construir artilugios utilizando $S_{0..2}$ para calcular el valor de cualquier operación booleana sobre los valores de dos vértices dados. Así, para cada fórmula podemos añadir un subgrafo finito del que un vértice se coloreará según su valor de verdad dado que los vértices de las variables se han coloreado según la asignación de verdad. Se fusiona ese vértice con $S_1$ . Esto obliga a que la coloración sólo sea posible si la asignación de verdad satisface la fórmula. Ahora observe que cualquier conjunto finito de fórmulas es capturado por un subgrafo finito, por lo que el $3$ -se puede aplicar el teorema del color para obtener el teorema de la compacidad.

Answer 2

Otro concepto relacionado con la compacidad es el de Ideal primo booleano principio, BPI, que afirma que toda colección de elementos en un álgebra booleana arbitraria con propiedad de intersección finita (cada dos elementos tienen encuentro no nulo), FIP, puede extenderse a un ultrafiltro.

Se sabe que el BPI es equivalente al principio de coloración: véase el artículo de H.Lauchli de 1971 Colorear grafos infinitos y el teorema del ideal primo booleano .

Podemos entonces trasladar esta pregunta a una algebraica utilizando Lindenbaum-Tarski álgebras. Sea $F$ denotar el conjunto de todos los formluas de la lógica clásica y definir su cociente $F/_\cong$ , donde $\varphi\cong\psi$ si estas dos fórmulas son equiprobables en la lógica clásica (equivalentemente, tienen el mismo valor en cada realización). Por tanto, los elementos de $F/_\cong$ tienen la forma $[\varphi]=\{\psi\, |\,\psi\cong\varphi \}$ . A continuación, podemos equipar naturalmente este conjunto con operaciones booleanas: $[\varphi]\wedge [\psi]=[\varphi\wedge\psi]$ y de forma similar para otras conectivas. Nótese que su cero tiene una forma $[\bot]$ la clase de equivalencia de las fórmulas contradictorias, e.q. $[\psi\wedge\neg\psi]=[\bot]$ . $F/_\cong$ con estas operaciones entonces de un álgebra booleana, que llamamos álgebra de Lindenbaum-Tarski, vamos a denotarla $\mathrm{LT}$ .

Para un conjunto de fórmulas $\Sigma$ definir $[\Sigma]:=\{[\psi]\, |\, \psi\in \Sigma\}$ . Se pueden demostrar fácilmente las dos equivalencias siguientes:

• $\Sigma$ es finitamente realizable.
• $[\Sigma]$ tiene FIP en $\mathrm{LT}$ .

(Ver que si $\psi_1\dots\psi_n\in\Sigma$ entonces hay una realidad $v$ tal que $v(\psi_i)=1$ Por lo tanto $\bigwedge \psi_i\ncong \bot$ y en consecuencia $\bigwedge[\psi_i]=[\bigwedge \psi_i]\neq [\bot]=0$ ). La segunda equivalencia:

• $\Sigma$ es el máximo conjunto realizable de fórmulas.
• $[\Sigma]$ es un ultrafiltro en $\mathrm{LT}$ .

La realización del testimonio viene dada por $f(v)=1$ si [v] está en el ultrafiltro $[\Sigma]$ . Así, BPI nos permite ampliar $\Sigma$ a un conjunto mayor de fórmulas que es realizable (por supuesto, $\Sigma$ será realizable).