División de Estudios de Posgrado de la Facultad de Filosofía y Letras de la UNAM
Seminario de Investigación y Tesis (Metalógica y Computabilidad), primavera de 1999
Dr. Raymundo Morado
Sala de Becarios del IIF, miércoles de 2:30 a 4:30, asesorías viernes 2 a 4 o por cita
Objetivo general
Objetivo general: Se ofrece una introducción a la teoría de la computabilidad, usando las nociones y resultados para estudiar metalógicamente a los sistemas lógicos.
Febrero 3: Capítulo 1: Enumerabilidad y Capítulo 2: Diagonalización
Febrero 10: Capítulo 3: Máquinas de Turing y Capítulo 4: Incomputabilidad por productividad
Febrero 17: Capítulo 5: Incomputabilidad por diagonalización y 6: Computabilidad por ábaco
Febrero 24: Capítulo 7: Funciones recursivas y Capítulo 8: Computabilidad Turing y recursividad
Marzo 3: Capítulo 9: Lógica de primer orden y Capítulo 10: Indecidibilidad
Marzo 10: Capítulo 11: Corrección y Capítulo 12: Completud y compacidad
Marzo 17: Capítulo 13: Skolem-Löwenheim y Capítulo 14: Representabilidad
Marzo 24: Capítulo 15: Indecidibilidad, indefinibilidad e incompletud y Capítulo 16: Demostrabilidad
Abril 7: Capítulo 17: Modelos no estándar y Capítulo 18: Lógica de segundo orden
Abril 14: Capítulo 19: Aritmética y Capítulo 20: Definibilidad aritmética
Abril 21: Capítulo 21: Decidibilidad aritmética y Capítulo 22: Lógica diádica
Abril 28: Capítulo 23: Craig y Capítulo 24: Aplicaciones de Craig
Mayo 5: Capítulo 25: Lógica monádica y diádica y Capítulo 26: Ramsey
Mayo 12: Capítulo 27: Modalidad y Capítulo 28: Oraciones indecidibles
Mayo 19: Capítulo 29: Modelos no recursivos de Z y Entrega de trabajos finales.
Metodología: El propósito del seminario es producir trabajos originales de investigación conducentes a una tesis de grado. Por ello, tratamos de conectar los temas del seminario a los intereses de los alumnos quienes presentarán investigación original periodicamente.
Forma de valuación: Cada miembro del grupo resuelve problemas por escrito, hace varias presentaciones, y entrega un trabajo de investigación final.
Ejercicios por escrito
Capítulo I
1.Dé un ejemplo novedoso de conjunto enumerable que no sea denumerable.
2.Dé un ejemplo novedoso de conjunto denumerable.
3.¿Por qué no se pueden enumerar todas las tautologías en orden alfabético?
4.Describa una función que enumere al conjunto de todas las tautologías.
5.Escriba las tablas de verdad de las conectivas proposicionales bivalentes veritativo-funcionales monádicas (como la negación) que podría haber.
6.Presente una enumeración infinita de ellas.
7.¿Cuáles diádicas podría haber (conjunción, equivalencia, etc.)? Invente un nombre para las que no lo tengan.
8.Presente una función que enumere al conjunto de ellas.
9.¿Cuántas triádicas podría haber? ¿Cuántas tetrádicas? ¿Cuántas sin importar su aridad?
10.Demuestre que el conjunto de todas estas conectivas, es enumerable. (Consejo: estudie la respuesta a la pregunta 1.4.)
11.¿En qué sentido no se pueden poner las funciones de verdad en una lista?
12.¿En qué sentido sí?
13.Dé un ejemplo novedoso de función parcial, identificando cuál es el dominio y cuál el rango.
14.Complete la frase: Un conjunto es enumerable si y sólo si es el .... de alguna... de...
Capítulo II
15.Dé un ejemplo novedoso de conjunto no enumerable.
16.La presentación de la prueba de Cantor tiene una reductio ad absurdum dentro de otra. ¿Cuál es cuál?
17.Demuestre que no es enumerable el conjunto de las verdades. (Consejo: Piense que hay algo verdadero sobre cada conjunto de números.)
18.Si las fórmulas lógicas fueran siempre cadenas finitas a partir de elementos de cierto alfabeto finito, demuestre que el conjunto de fórmulas lógicas sería enumerable.
19.¿Qué concluye de las dos respuestas anteriores?
20.Suponga que tenemos un conjunto denumerable de lenguajes, cada uno con un conjunto denumerable de oraciones. Demuestre que el conjunto de todas las oraciones de todos esos lenguajes es denumerable.
21.¿Puede computar más un dios sempiterno (sin principio ni fin) que uno simplemente inmortal (sin fin)? Demuéstrelo.