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

De Cuba-Wiki
Revisión del 04:13 16 nov 2017 de Berocs (discusión | contribs.) (Agrega solución a ejercicio. Tardas mucho tiempo en pasar el ejercicio de la hoja a latex.)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

Plantilla:Back

Supongamos que la existe. Definimos

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

Armamos el conjunto . Vamos a demostrar satisfacibilidad e insatisfacibilidad de , llegando a una contradicción.

Satisfacibilidad de A: Por compacidad, si todos los subconjuntos finitos de son satisfacibles, entonces es satisfacible. Tomemos finito. Como es finito, existe un tal que para todo , . Entonces, . Si probamos satisfacibilidad de , probaremos satisfacibilidad de . Para eso, usaremos una -estructura con , , siendo la igualdad entre elementos, y el universo siendo los enteros de hasta . Tomaremos también la valuación tal que . Con esta valuación y estructura se cumple , y también se cumplen las . Con lo cual es satisfacible es satisfacible, siendo cualquier subconjunto finito de es satisfacible.

Insatisfacibilidad de A: Asumamos que se cumplen todas las para alguna valuación , tal que . Asumamos también que se cumple , en particular para este , o sea que (aplicar veces). Pero esto contradice , que dice que lo anterior no vale. ABS! Entonces, no es satisfacible.

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