Teorema de la compacidad para el cálculo proposicional - ¿buenos usos?

Question

El teorema de compacidad para el cálculo proposicional afirma que un conjunto de oraciones proposicionales tiene un modelo (asignación satisfactoria) si y sólo si cada subconjunto finito del mismo tiene un modelo. Estoy buscando usos del teorema para algo fuera de la lógica que sean lo suficientemente simples como para presentarlos sin antecedentes adicionales.

Un ejemplo de ello son los mosaicos, por ejemplo, los mosaicos de $\mathbb{Z}^2$ utilizando Azulejos Wang . Dado un conjunto de baldosas Wang se pueden introducir variables $X_{i,j}^k$ que significa "Azulejo no. $k$ fue colocado en $(i,j)$ ". Ahora construimos un conjunto infinito de sentencias que dicen que la asignación a las variables define un mosaico legal (es decir, para cada $(i,j)$ exactamente uno $X_{i,j}^k$ es verdadera, y también comprobamos la compatibilidad de los bordes). Ahora se puede utilizar el teorema de la compacidad para demostrar que un conjunto de baldosas cubre todo el plano si y sólo si cubre cualquier zona finita del plano.

¿Hay más usos con el mismo espíritu?

Answer 1

Puedes utilizar el Teorema de la compacidad para demostrar que un gráfico contable $G$ es $k$ -si y sólo si todo subgrafo finito de $G$ es $k$ -colorables. Se explica una prueba aquí pero la idea general es clara, y es casi más fácil realizar la solución que escribirla.

También puede utilizar el Teorema de la compacidad para introducir la noción de modelos no estándar de la aritmética, o los hiperreales. Es decir, se toma la teoría de $\mathbb{N}$ o $\mathbb{R}$ y adosar la familia infinita de sentencias

$$ x > n$$

como $n$ se extiende sobre $\mathbb{N}$ (aquí, $x$ es un nuevo símbolo constante). Estas sentencias afirman la existencia de algún valor $x$ mayor que cualquier número natural. Dado que cualquier subconjunto finito de esta teoría es satisfacible (interpretando $x$ como un número suficientemente grande), toda la teoría es satisfacible, y por tanto se obtienen modelos con elementos infinitesimales y/o ilimitados. Puede leer más sobre los modelos no estándar de la aritmética aquí y más sobre los hiperreales aquí que naturalmente se extiende al estudio de análisis no estándar .

Answer 2

Suponga que tiene un conjunto $S$ de estudiantes y un conjunto $C$ de clases. Cada estudiante será asignado a una sola clase. Cada estudiante $s\in S$ tiene una lista finita $C(s)\subseteq C$ de clases que está dispuesto a tomar, y cada clase $c\in C$ tiene una capacidad de inscripción finita $n_c$ . Para $T\subseteq S$ , un asignación de curso aceptable es una función $f:T\to C$ tal que

• $f(t)\in C(t)$ para cada $t\in T$ y
• $\left|f^{-1}\left[\{c\}\right]\right|\le n_c$ para cada $c\in C$ .

(En otras palabras, cada estudiante recibe una clase aceptable, y ninguna clase está saturada).

El teorema de la compacidad implica ahora fácilmente que si cada subconjunto finito de $S$ admite una asignación de curso aceptable, entonces también lo hace $S$ . Probablemente la forma más sencilla de modelarlo es como un grafo bipartito con partes $S$ y $C$ donde cada vértice de $S$ es tener grado $1$ cada vértice $c\in C$ tiene un grado no superior a $n_c$ y para cada $s\in S$ la única arista adyacente a $s$ debe terminar en uno de los vértices de $C(s)$ .

Answer 3

Existe una construcción muy bonita que muestra que todo orden parcial puede extenderse a un orden total utilizando el teorema de compacidad proposicional, véase http://www.math.caltech.edu/~2010-11/3term/ma006c/Notes46c.pdf (Gracias a Brian M. Scott por la versión en inglés).

La prueba funciona asumiendo un conjunto dado $S$ y para cada par $a,b \in S$ de valores, teniendo una variable $L_{a,b}$ que significa $a < b$ . Entonces es fácil formalizar los axiomas de un orden total y el orden parcial existente como un conjunto de fórmulas proposicionales. Utilizando la compacidad, se demuestra que el conjunto de fórmulas es satisfacible, es decir, que existe un orden total.