Final del 22/06/17 (Lógica y Computabilidad)

Ejercicio 1

Demostrar que una función es primitiva recursiva sii pertenece a toca clase PRC.

Ejercicio 2

Enunciar y demostrar el Teorema de Rice

Ejercicio 3

Usando el teorema de correctitud de la lógica proposicional, probar que si $Gamma$ es un conjunto de fórmulas satisfacible, entonces es consistente.

Ejercicio 4

Sea L={0,S,<,+,·} con igualdad y sea N={N,0,S,<,+,·} la L-estructura de primer orden con la interpretación normal. Mostrar que existe un modelo de la Teoría de N en donde existe un elemento inalcanzable (Desde el 0, usando la función sucesor S).