Final del 22/12/14 (Lógica y Computabilidad)

1) Demostrar que Gamma U {¬Phi} es inconsistente si y solo si Phi es consecuencia sintactica de Gamma. (En logica proposisional la demo). En la demo de la clase se usa un galeraso (un teorema de SP), que santi dijo que se puede usar, o uno equivalente.

2) Probar que en un lenguaje de primer ordern con igualdad si una teoria tiene modelos arbitrariamente grandes, tiene modelo infinito. No habia aclarado que era con igualdad, tambien vale sin, pero la demo hay que partirla en dos casos (con y sin).

3) Enuncie el teorema de la recursion y demuestrelo usando el teorema del parametro.

4) Pruebe que Tot no es c.e. ni co-c.e.