Solución Ejercicio 4 Parcial Lógica 14/11/2014 (Lógica y Computabilidad - Departamento de Computación)

Supongamos que la $\varphi$ existe. Definimos

Error al representar (error de sintaxis): {\displaystyle \varphi_1: f(x) \neq c \\ \varphi_2: f(f(x)) \neq c \\ \vdots} $\varphi _{n}:f(f(...(f(x))...))\neq c$ (aplicar $f$ $n$ veces)

Armamos el conjunto $A=\{\varphi \}\cup \{\varphi _{i}|i\geq 1\}$. Vamos a demostrar satisfacibilidad e insatisfacibilidad de $A$, llegando a una contradicción.

Satisfacibilidad de A: Por compacidad, si todos los subconjuntos finitos de $A$ son satisfacibles, entonces $A$ es satisfacible. Tomemos $a\subseteq A$ finito. Como es finito, existe un $n$ tal que para todo $\varphi _{i}\in A$, $i\leq n$. Entonces, $a\subseteq a'=\{\varphi \}\cup \{\varphi _{i}|i\geq 1\wedge i\leq n\}$. Si probamos satisfacibilidad de $a'$, probaremos satisfacibilidad de $a$. Para eso, usaremos $C$ una $L$-estructura con $c_{C}=\emptyset$, $f_{C}(y)=(y+1)\mod (n+1)$, $=_{C}$ siendo la igualdad entre elementos, y el universo siendo los enteros de $0$ hasta $n$. Tomaremos también la valuación $v$ tal que $v(x)=0$. Con esta valuación y estructura se cumple $\varphi$, y también se cumplen las $\varphi _{i}$. Con lo cual $a'$ es satisfacible $\Rightarrow a$ es satisfacible, siendo $a$ cualquier subconjunto finito de $A\Rightarrow A$ es satisfacible.

Insatisfacibilidad de A: Asumamos que se cumplen todas las $\varphi _{i}$ para alguna valuación $v$, tal que $v(x)=x'$. Asumamos también que se cumple $\varphi$, en particular para este $x'$, o sea que $(\exists n_{x'})f(f(...(f(x))...))=c$ (aplicar $f$ $n_{x'}$ veces). Pero esto contradice $\varphi _{n_{x'}}$, que dice que lo anterior no vale. ABS! Entonces, $A$ no es satisfacible.

Llegamos a la conclusión que $A$ es satisfacible e insatisfacible. ABS! que vino de suponer que existía una $\varphi$ que expresaba la propiedad. $\square$