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. 

Durante el segundo semestre de 2025 estaremos haciendo sesiones de estudio centradas en teoría de modelos. 




2025-11-25
16:10hrs.
Lucas Garrido. PUC
Balance del semestre y proyecciones
Sala 1
Abstract:
En esta sesión final haremos una síntesis de los temas explorados a lo largo del semestre, destacando el rol de la expresividad lógica y su relación con nociones fundamentales de complejidad computacional. Además, discutiremos posibles extensiones y direcciones de investigación que enmarcarían la continuación del seminario de lógica en el próximo año académico
2025-11-18
16:10hrs.
Lucas Garrido. PUC
El Teorema de Immerman-Vardi
Sala 1
Abstract:
La lógica de primer orden con operador de punto fijo mínimo, FO(LFP), extiende la lógica clásica mediante definiciones inductivas que capturan procesos recursivos sobre estructuras finitas. Esta ampliación resulta esencial para expresar propiedades globales que están fuera del alcance de la lógica de primer orden pura. En esta sesión estudiaremos dicha ampliación, llegando a discutir el teorema de Immerman–Vardi, el cual establece que FO(LFP) define exactamente las propiedades computables por una MT determinista en tiempo polinomial para estructuras finitas y ordenadas.

2025-11-04
16:10hrs.
Luis Cofré. PUC
El teorema de Fagin y P vs NP
Sala 1
Abstract:
En esta charla exploraremos la profunda conexión entre lógica y clases de complejidad. El Teorema de Fagin nos dice que podemos expresar la clase NP a partir de un subconjunto de la logica de segundo orden y usaremos este hecho para dar una caracterización de P vs NP usando solo lógica.
2025-10-28
16:10hrs.
Cristóbal Villalobos. PUC
Lógica de Segundo Orden
Sala 1
Abstract:
Hablaremos del lenguaje de la lógica de Segundo orden, sus axiomas y la semántica. Veremos algunos ejemplos y propiedades.
2025-10-21
16:10hrs.
Francisco Didier. PUC
El Teorema de Trakhtenbrot
Sala 1
Abstract:
El teorema de completitud de Gödel nos permite saber que en lenguajes de primer orden, si una fórmula es válida en todo modelo, entonces es demostrable. Sería intuitivo afirmar que esto se mantiene en modelos finitos, pero no es el caso. Esto lo demostró Trakhtenbrot a través de su teorema, el cual es el que estudiaremos en esta sesión.
2025-10-07
16:10hrs.
Lucas Garrido. PUC
Introducción a la Complejidad Computacional
Sala 1
Abstract:
En esta sesión realizaremos un repaso introductorio de los conceptos fundamentales de complejidad computacional que sirven de base para el estudio de la lógica descriptiva. Revisaremos las clases famosas de complejidad (P, NP, PSPACE) y su interpretación lógica, la noción de reducción polinomial y las ideas detrás de completitud.
2025-09-30
16:10hrs.
Luis Cofré. PUC
Gaifman y Localidad de FO
Sala 1
Abstract:
En esta charla demostraremos que las consultas definibles en lógica de primer orden son Hanf y Gaifman locales, usando las nociones y la estructura de espacio métrico de los grafos vistas en la sesión pasada. Haremos énfasis en propiedades combinatoriales de las vecindades.
2025-09-23
16:10hrs.
Felipe Inostroza. PUC
Localidad en Modelos Finitos
Sala 1
Abstract:
En esta charla exploraremos aspectos fundamentales vinculados a la noción de localidad. Revisaremos definiciones básicas necesarias para hablar de vecindades en estructuras finitas y de cómo estas permiten acotar el alcance de las fórmulas de primer orden. Nos centraremos en las nociones complementarias de Hanf-localidad y Gaifman-localidad.

2025-09-02
16:10hrs.
Cristóbal Villalobos. PUC
Demostración teorema de Ehrenfeucht-Fraïssé
Sala 1
Abstract:
Veremos la demostración de este teorema y un par de corolarios que nos permitirán tener una estrategia completa para determinar si una propiedad es definible o no.
2025-08-26
16:10hrs.
Lucas Garrido. PUC
Juegos de Ehrenfeucht-Fraïssé: Límites de expresividad
Sala 1
Abstract:
Mostraremos cómo los juegos de Ehrenfeucht-Fraïssé permiten caracterizar cuándo dos estructuras son indistinguibles para fórmulas de rango acotado y, a partir de ello, derivar límites de expresividad. Un ejemplo fundamental será el caso de los órdenes lineales finitos, donde se demuestra que la propiedad de “tener un número par de elementos” no es definible en lógica de primer orden. 
2025-08-19
16:10hrs.
Lucas Garrido. PUC
Teoría de Modelos: Juegos de Ehrenfeucht-Fraïssé
Sala 1
Abstract:
En esta sesión revisaremos ejemplos que muestran la utilidad y las limitaciones del teorema de compacidad para demostrar la indefinibilidad de propiedades en estructuras de primer orden. Estas limitaciones motivan el uso de herramientas propias de la teoría de modelos finitos, en particular los juegos de Ehrenfeucht–Fraïssé, sobre los que centraremos la exposición.
2025-07-10
14:50hrs.
Luis Cofré. PUC
Teorema de Incompletitud de Gödel y Computabilidad II
Sala 1
Abstract:
En esta sección estudiaremos conceptos básicos de computación sobre maquinas de Turing, decidibilidad y usaremos reducción de lenguajes para demostrar que la teoría aritmética estudiada en la parte anterior de esta charla es indecidible.
2025-07-03
16:10hrs.
Luis Cofré. PUC
Teorema de Incompletitud de Gödel y Computabilidad I
Sala 1
Abstract:
En esta sesión veremos una demostración del teorema de incompletitud de Gödel a traves de teorias y veremos maquinas de turing para demostrar la indecidibilidad de los naturales.
2025-06-19
16:10hrs.
Cristóbal Villalobos. PUC
Teoría de la Demostración: Operaciones de la Aritmética de Peano
Sala 1
Abstract:
Definiremos suma y multiplicación formalmente, con vistas a demostrar el teorema de incompletitud de Gödel.
2025-06-12
16:10hrs.
Cristóbal Villalobos. PUC
Teoría de la Demostración: Axiomas y operaciones de la aritmética de Peano
Sala 1
Abstract:
Veremos las definiciones y axiomas que permitirán formalizar la estructura de los naturales de manera estándar, en vistas de demostrar los teoremas de incompletitud de Gödel.


2025-05-29
16:10hrs.
José Chang-Peng. PUC
Teoría de la Demostración: El principio de trivialidad
Sala 1
Abstract:
En esta sesión abordaremos la noción formal de demostración trivial desde un enfoque estructural.  
Presentaremos criterios precisos para caracterizar cuándo una demostración puede considerarse evidente o elemental en un sistema formal dado, al punto que ni siquiera merece ser escrita. Además, exploraremos la estructura algebraica y topológica que emerge al considerar el conjunto de demostraciones triviales, mostrando que este conjunto genera una topología natural en el espacio de todas las demostraciones.
2025-05-22
16:10hrs.
Luis Cofré. PUC
Teoría de la Demostración: Introducción a la Aritmética de Peano
Sala 1
Abstract:
En esta sesión estudiaremos el calculo de predicados con igualdad LKe y sus principales consecuencias para lograr una formulación de la Aritmética de Peano.
2025-05-15
16:10hrs.
Patricio Pérez Labra. PUC
Teoría de la Demostración: Consecuencias del Teorema de Corte-eliminación
Sala 1
Abstract:
Con el teorema de corte-eliminación en nuestro poder, analizaremos varias de las consecuencias que tiene este teorema para las demostraciones en LK y LJ.
2025-05-13
16:10hrs.
Victor Valencia. PUC
Teoría de la Demostración: Teorema de corte-eliminación
Sala 1
Abstract:
El teorema de corte-eliminación establece que si un secuente es LK-demostrable, entonces es LK-demostrable sin regla de corte. Estudiaremos la demostración original de este resultado.
2025-04-24
16:10hrs.
Francisco Didier. PUC
Teoría de la Demostración: Sistemas de Axiomas
Sala 1
Abstract:
Continuaremos estudiando la noción de demostración dentro de un sistema axiomático comparando la CPC-deducibilidad y CPI-deducibilidad de un secuente.