Final del 07/03/19 (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

Enunciar y demostrar el teorema de Rice.

Ejercicio 3

Si $\Gamma$ es m.c. entonces para toda fórmula $\varphi$ vale:

- $\varphi \in \Gamma$ (o excluyente) $\neg \varphi \in \Gamma$

- $\Gamma \vdash \varphi \iff \varphi \in \Gamma$

Ejercicio 4

Si $\Gamma$ tiene modelos arbitrariamente grandes, tiene modelo infinito.