Final del 21/12/17 (Lógica y Computabilidad)

Ejercicio 1

Demostrar que TOT no es c.e.

Ejercicio 2

Enunciar y demostrar el Teorema de la Deducción.

Ejercicio 3

Demostrar que si A es c.e. y A $\neq$ $\emptyset$, entonces A es el rango de una función parcial computable

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.