Demuestre que el teorema de la compacidad no se aplica a la lógica infinita

Question

Estoy tratando de entender por qué el teorema de la compacidad no se aplica en la lógica infinita y me pregunto si alguien tiene un buen ejemplo y explicación para esto.

Editar : Por lógica infinita entiendo la lógica que permite infinitas conjunciones y disyunciones. Más exactamente:

• $M \models \bigvee \Gamma$ si $M \models \varphi$ para algún conjunto de frases $\varphi \in \Gamma$ .
• $M \models \bigwedge \Gamma$ si $M \models \varphi$ para algún conjunto de frases $\varphi \in \Gamma$ .

Teorema de la compacidad:

El teorema de la compacidad establece que un conjunto de sentencias de primer orden tiene un modelo si y sólo si cada subconjunto finito del mismo tiene un modelo.

Gracias de antemano.

Answer 1

Esto se denomina "infinit ary lógica". Para cada par de cardinales infinitos $\kappa\ge\lambda$ existe una lógica $\mathcal{L}_{\kappa,\lambda}$ obtenida cerrando la lógica de primer orden bajo conjunciones y disyunciones de tamaño $<\kappa$ y cuantificación universal y existencial sobre tuplas de longitud $<\lambda$ . Las lógicas infinitas más comunes son de la forma $\mathcal{L}_{\kappa,\omega}$ - por lo que sólo se permite la cuantificación finita, aunque permitimos combinaciones booleanas "grandes".

La lógica $\mathcal{L}_{\omega,\omega}$ es la propia lógica de primer orden. La primera lógica infinitaria es $\mathcal{L}_{\omega_1,\omega}$ donde ampliamos la lógica de primer orden permitiendo contablemente infinito conjunciones y disyunciones. Aquí ya vemos un fallo de compacidad: consideremos la frase $$(*)\quad\bigvee_{n\in\mathbb{N}}[\forall x_1,...,x_n(\bigvee_{1\le i<j\le n}x_i=x_j)].$$ Esto es cierto en una estructura si dicha estructura es finita. Pero esto da lugar a un contraejemplo de compacidad (piénsese en la prueba de que toda teoría de primer orden con modelos finitos arbitrariamente grandes tiene un modelo infinito):

Considere la teoría $\{(*)\}\cup\{\mbox{"There are at least $ n $ elements"}: n\in\mathbb{N}\}$ .

Answer 2

Supongamos que existe una disyunción infinitamente larga (1).

\begin{equation}\tag{1}a_1\lor a_2\lor a_3\lor\dots\end{equation}

Consideremos entonces una colección infinita de fórmulas (2), formada por la negación de cada instancia de la disyunción.

\begin{equation}\tag{2}\{\lnot a_1,\lnot a_2,\lnot a_3,\dots\}\end{equation}

Una teoría $T$ formado por (1) y todas las fórmulas de (2) será necesariamente insatisfactible, ya que cada átomo proposicional negado $a_i$ no puede satisfacerse a menos que el átomo sea falso.

Sin embargo, todo subconjunto finito de fórmulas en $T$ será satisfacible, (por ejemplo $\lnot a_1$ y $a_1\lor a_2\lor a_3\lor\dots$ ). Si se aplica el teorema de la compacidad, entonces el conjunto que comprende todas las fórmulas de la teoría será satisfacible.

Esto es una contradicción, así que no es el caso que el teorema de la compacidad se aplique en lo que has llamado lógica infinita.