Final del 05/08/13 (Lógica y Computabilidad)

Ejercicio 1

Probar que la clase de funciones computables es una clase PRC

Ejercicio 2

Definir conjunto de índices. Enunciar y demostrar el Teorema de Rice

Ejercicio 3

Usando el Teorema de Correctitud de la lógica proposicional probar que si $\Gamma$ es satisfactible entonces $\Gamma$ es consistente.

Ejercicio 4

Dado L un lenguaje de primer orden con igualdad. Decidir si las siguientes afirmaciones son verdaderas o falsas.

1. Existe un conjunto $\Gamma$ tal que $\Gamma \models A$ sii A tiene universo infinito.

2. Existe un conjunto $\Gamma$ tal que $\Gamma \models A$ sii A tiene universo finito.

3. El conjunto $\Gamma$ del ítem 1 necesariamente es infinito.