Práctica 4: Compacidad (Lógica y Computabilidad)

Ejercicio 07

• Ej 7) Sea Γ con la propiedad de que cada valuación satisface al menos una fórmula de Γ. Probar que existe un número finito de fórmulas $\alpha _{1},...,\alpha _{n}\in \Gamma$ tales que $\alpha _{1}\lor ...\lor \alpha _{n}$ es tautología.

Solución: Pruebo por absurdo.

Supongo que $\forall \alpha _{1},...,\alpha _{n}\in \Gamma ,\alpha _{1}\lor ...\lor \alpha _{n}$ no es una tautología. Entonces $\exists v/v(\alpha _{1}\lor ...\lor \alpha _{n})=0\Rightarrow v(\alpha _{i})=0,1\leq i\leq n$ (*)

Defino Γ´ $=\{\neg \alpha :\alpha \in \Gamma \}.$ Como $v(\neg \alpha )=1\Leftrightarrow v(\alpha )=0$, si pruebo que Γ´ es satisfacible $\Rightarrow \exists v/v(\neg \alpha )=1\forall \alpha \in \Gamma \Rightarrow v(\alpha )=0\forall \alpha \in \Gamma$.

Sea Φ ⊆ Γ´ finito / $\Phi =\{\neg \alpha _{1},...,\neg \alpha _{n}\}\forall \alpha _{i}\in \Gamma ,1\leq i\leq n$. Φ es satisfacible si y sólo si $\exists v/v(\neg \alpha _{i})=1\forall 1\leq i\leq n\Leftrightarrow \exists v(\alpha _{i})=0\forall 1\leq i\leq n$. Esta valuación existe por hipótesis (*). Entonces, por el teorema de compacidad, Γ´ es satisfacible. Absurdo puesto que Γ tiene la propiedad de que toda valuación satisface al menos una de sus fórmulas.