Lógica Matemática (I-2008)

El primer problema de la tarea 13 naturalmente no requiere fijar . Se trata de mostrar por qué los conjuntos y son recursivamente inseparables ( claramente varía sobre las fórmulas aritméticas). Para hacer este problema, suponga que y fueran recursivamente separables, digamos mediante un conjunto recursivo . Use que es representable mediante una fórmula de la aritmética y considere si o no. (Agradezco a Joaquín Maya el que haya preguntado por este problema.)

Además de los apuntes de clase sobre compacidad, la relación que vimos hoy y el teorema de Tarski-Vaught, colgué otros apuntes sobre el Teorema de Church (la aritmética es indecidible) y su consecuencia, buen cierre del curso: la lógica de primer orden es indecidible. Disfruten la lectura de esos temas.

Se me fue un error en la tarea 12. En el punto 3, segunda parte, pido que haga lo mismo (i.e. demostrar que es definible) en . En realidad, quería que probaran que (los reales positivos) es definible en .

Hay un texto en la pestaña Apuntes de Clase sobre los temas recientes. Hacen parte del inicio de un minicurso en Teoría de Modelos - no corresponden exactamente a lo visto recientemente en clase, pero hay material que les puede ser útil.

Esta es la última tarea del curso. No la discutiremos en clase - es material que ustedes deben preparar para el examen final. Sin embargo, recuerde que el miércoles 11 de junio habrá consultas sobre material de todo el curso - esto incluirá consultas sobre la tarea 13. Recuerde que la tarea 12 sí será discutida (como siempre) el viernes 6 de junio.

Click aquí.

Ahí está, para el 6 de junio.

Click aquí.

(Finalmente) estamos llegando al final de los temas del curso. Mañana viernes continuaremos con aplicaciones del criterio de Vaught y veremos el teorema de Löwenheim-Skolem ascendente. También presentarán ustedes soluciones a las tareas 9 (problemas faltantes) y 11.

La semana entrante (última de clases) veremos los siguientes temas:

1. Sección 3.1 del libro de Goldstern-Judah (dije 3.3 ayer - obviamente era 3.1, aunque de hecho también estamos viendo parte de 3.3) - páginas 131 a 148. Veremos inmersiones elementales y cadenas de modelos.
2. (Brevemente) el teorema de Church.
3. (Brevemente) modelos de teoría de conjuntos.

Habrá una tanda de problemas (12) para el viernes, como siempre. La colgaré entre hoy y mañana.

La siguiente semana habrá sesión de repaso y consultas (miércoles 11) y examen final (viernes 13). También habrá una tarea (13) para el examen final.

Los ejemplos de la semana que viene requieren revisar con cuidado varias definiciones que vienen del Álgebra. Miraremos teorías de cuerpos algebraicamente cerrados (la teoría se llama ), con característica ( primo o cero), o , teorías de módulos sobre anillos, varias teorías de grupos con axiomas adicionales (grupos libres de torsión, grupos de torsión).

Se me fue un error en las versiones anteriores de los apuntes de clase sobre deducción.

El axioma de cuantificadores como está originalmente ( (sin restricción sobre el término ) no funciona. Note (por ejemplo que no debe implicar que - ¡el que una función sea sobreyectiva no implica que tiene puntos fijos!). Esto se resuelve de varias maneras posibles (no se pueden tomar términos tan arbitrarios). Para nosotros es suficiente la siguiente restricción:

debe ser o mismo, o un término cerrado.

¡Agradezco a Pedro Zambrano el haber señalado este error!

Lista la tarea 11, para el viernes 30 de mayo. También está la versión (más actualizada, con la demostración del Teorema de Completitud de Gödel) en el numeral 4 de Apuntes de Clase.

Click aquí para la Tarea 11.