Matemáticas (plan 1983) 2016-1

Optativas de los Niveles VII y VIII, Lógica Matemática III

Introducción.

En este curso veremos los primeros resultados limitativos sobre el método axiomático, algoritmos, funciones recursivas, la aritmética y las propiedades de completud y decibilidad, el lema de la diagonal, el lema de Löb, los teoremas de Gödel, Tarski y Church; las primeras nociones de teorías indecidibles.

Temario.

I. Un Cálculo de Predicados (el sistema MB).

Correctud, Completud. Compacidad; Teorías consistentes y completas.

II. La Aritmética.

El modelo estándar de la Aritmética.

Fragmentos de la Aritmética (P, Q, E, etc.).

III. Algoritmos y Conjuntos Decidibles.

Lenguajes contables. Procedimientos Efectivos y Algoritmos. Conjuntos Decidibles, Efectivamente Numerables y Funciones Calculables. Conjuntos Indecidibles. Teorías Axiomáticas, Efectivamente Numerables y Decidibles.

IV. Funciones Recursivas.

Funciones Recursivas Primitivas. Predicados Recursivos y Cuantificadores Acotados. Tesis de Church.

V. Aritmetización y Representabilidad.

Definibilidad en Q y en el modelo estándar. Aritmetización y Representabilidad. Predicados de Prueba.

VI. Teoremas Limitativos.

Teorema del Punto Fijo (Lema de la Diagonal). Teorema de Indefinibilidad de Tarski. Primer Teorema de Incompletud de Gödel-Rosser. Teorema de Löb. Segundo Teorema de Incompletud de Gödel. Indecibilidad de Q y de la artimética.

VII. Teorías Indecidibles.

Teorías Indecidibles, esencialmente indecidibles, fuertemente indecidibles, etc.

Forma de evaluación.

En cada capítulo se entrega una guía para trabajar el material visto. De aquí se extraen los exámenes parciales, de reposición y final.

Habrá un examen por capítulo, tentativamente, y la calificación final será el promedio de los parciales. Habrá dos reposiciones como máximo. Tanto en reposición como en final: “borrón y cuenta nueva”.

En cada guía hay problemas para aumentar punto en la calificación correspondiente, esto es: si se entregan antes del examen correspondiente y están bien resueltos, aumenta un punto; en caso contrario, no afecta la calificación correspondiente. Sólo afectan al examen correspondiente y no se guardan para otros capítulos.

Bibliografía.

[BJ] Boolos-Jeffrey. Computability and Logic.

[E] Enderton, H. Introducción Matemática a la Lógica

[M] Mendelson, E.Introduction to Mathematicla Logic.

[S] Shoelfield, J. Logical Mathematic.

[TMR] Tarski-Mostowski-Robinson. Undecidible Theories.