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

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

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.