Final del 20/02/20 (Lógica y Computabilidad)

Ejercicio 1

Si $A\neq \emptyset$ y además es c.e., entonces $A$ es el rango de una función p.r.

Ejercicio 2

Definir conjunto de índices. Dar un ejemplo de un conjunto que lo sea y de uno que no lo sea. Enunciar y demostrar el Teorema de Rice.

Ejercicio 3

Demostrar que, si $\Gamma$ tiene modelos arbitrariamente grandes, entonces $\Gamma$ tiene modelo infinito

Ejercicio 4

Demostrar que existen modelos no estándar de la aritmética.