Seminario de Lógica Matemática

El seminario está dirigido a estudiantes de pregrado y posgrado interesados en los fundamentos de la matemática, teoría de modelos y teoría de computabilidad. El objetivo es profundizar en conceptos y teoremas relacionados con lenguajes formales, lógica algebraica y decidibilidad. 
 
Los expositores serán distribuidos entre invitados y voluntarios. 

El siguiente drive contiene las presentaciones/apuntes de cada sesión:

https://drive.google.com/drive/folders/1xAmcDzXu6gQ-THBst1pKOQ5GHlCiHK0I




2024-06-05
16:10hrs.
Paul Toussaint. Usach
El Décimo Problema de Hilbert
Sala Multiusos (1° piso)
Abstract:
El décimo problema de Hilbert pertenece a la famosa lista de 23 problemas que publicó David Hilbert en 1900. El problema plantea encontrar un algoritmo general que determine cuándo un polinomio con coeficientes enteros y múltiples variables tiene una raíz entera. 70 años después, Yuri Matiyasevich da una solución definitiva: No puede existir tal algoritmo. En esta charla introduciremos los conceptos básicos de la teoría de la computabilidad y veremos como se relacionan con los polinomios diofantinos, para finalmente demostrar la sorprendente solución al décimo problema de Hilbert.
2024-05-29
16:10hrs.
Renato Lewin. PUC
Árboles de Gentzen
Sala Multiusos (1° piso)
2024-05-22
16:10hrs.
Sofía Errázuriz. PUC
El Teorema de Fagin: Capturando Clases de Complejidad con Lógica
Sala Multiusos (1° piso)
Abstract:
El teorema de Fagin es uno de los primeros resultados de complejidad descriptiva, en él se postula que es posible capturar la clase de complejidad NP utilizando un fragmento de lógica de segundo orden. En esta charla, se presentará la definición de NP y la demostración del teorema para estructuras con una relación binaria. 
2024-05-15
16:10hrs.
Miguel Romero. PUC
El Teorema de Recursión para Máquinas de Turing
Sala Multiusos (1° piso)
Abstract:
En esta charla se dará una demostración autocontenida del teorema de recursión para máquinas de Turing, el cual permite que una MT pueda acceder a su propio código. Se discutirán algunas implicancias de este teorema. 
2024-05-08
16:10hrs.
Pablo Barceló. PUC
Complejidad de Kolmogorov y una Demostración del Teorema de Gödel
Sala Multiusos (1° piso)
Abstract:
Definiremos la noción de complejidad de Kolmogorov de un string y demostraremos que el problema de computar tal complejidad es indecidible. A partir de esto entregaremos los ingredientes básicos para realizar una demostración sencilla del Teorema de Gödel.
2024-04-24
16:10hrs.
Renato Lewin. PUC
Lógica Modal: Semántica de Mundos Posibles
Sala Multiusos (1° Piso)
2024-04-18
16:10hrs.
Lucas Garrido. PUC
Autómatas Para la Decibilidad de Teorías Aritméticas Il: El teorema de Boudet-Comon
Sala Multiusos (2° piso)
Abstract:

En esta charla probaremos el teorema de Boudet-Comon, el cual mediante una construcción de AFD’s permite concluir la decibilidad de la teoría $$\mathfrak{N} = (\mathbb{N}, S, \leq, +)$$ ampliamente conocida como aritmética de Presburger.

2024-04-11
16:10hrs.
Luis Cofré. PUC
Autómatas para la Decibilidad de Teorías Aritméticas I: La Teoría de Autómatas
Sala Multiusos (2° Piso)
Abstract:

En esta charla abordaremos la decidibilidad de ciertas teorías aritméticas bajo el esquema de teoría de autómatas, viendo sus conceptos fundamentales y su relación con lenguajes regulares, concluyendo el teorema de Myhill-Nerode.

2024-04-09
16:10hrs.
Benjamín Oyarzún. Rwth Aachen Universität
Cálculo de Secuentes de Gentzen e Indecibilidad
Sala Multiusos (Piso 2)
Abstract:
En este seminario se pretende demostrar la inexistencia de un programa capaz de decidir la satisfacibilidad de una fórmula sin variables libres en la lógica de primer orden, es decir, no existe un programa que pueda demostrar o refutar conjeturas matemáticas arbitrarias en el contexto de FO.
2024-04-04
16:10hrs.
Renato Lewin. PUC
Algebrización de la Lógica II
Sala Multiusos
Abstract:
En esta charla desarrollaremas las herramientas para generalizar el proceso de Lindenbaum-Tarski estudiado la vez anterior a otros sistemas lógicos clásicos y no clásicos
2024-03-21
16:10hrs.
Renato Lewin. PUC
Algebrización de la Lógica I
Sala 2, Edificio Rolando Chuaqui
Abstract:
Las oraciones de la lógica proposicional clásica verifican una serie de propiedades algebraicas simlilares a las de los números. Esto sugiere hacer un tratamiento algebraico de la lógica. Adelantándose a su tiempo George Boole sentó las bases de este estudio. Ya en el siglo XX, Alfred Tarski hizo la construcción general que asocia este cálculo proposicional con una clase de álgebras que se denominan álgebras de Boole.

En esta charla estudiaremos con cierto detalle esta relación.