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

1) Definir PRC. Probar que una función es primitiva recursiva sii pertenece a toda clase PRC.

2) Probar que A ⊆ N es computable sii A y Ā son computablemente enumerables

3) Definir "conjunto maximal consistente". Probar que si Γ es maximal consistente, entonces:

a) φ en Γ ó (excluyente) ¬φ en Γ

b) φ en Γ sii Γ |-- φ (consecuencia sintáctica)

4) Probar que si una teoría de primer orden con igualdad tiene modelos arbitrariamente grandes, entonces tiene modelos infinitos.