Sesión Lógica y ComputabilidadPropiedades asintóticas de estructuras ordenadas
Numa Grinberg
Universidad de Buenos Aires, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Uno de los teoremas más celebres de teoría de modelos finitos es la ley 0-1 de Fagin, que afirma que si \(\phi\) es una fórmula en la lógica de primer orden de grafos y \(\mathbf{G}(n)\) un grafo aleatorio de \(n\) vértices, entonces \(lim_{n\rightarrow\infty} \ Pr(\mathbf{G}(n)\models\phi){}\) existe y es \(0\) o \(1\).[1]
El teorema anterior se generalizo en varias direcciones y una de las más interesantes son los resultados “negativos” de Shelah y Compton, que demostraron que el teorema anterior deja de ser cierto si consideramos fórmulas \(\phi\) en la lógica de primer orden de grafos equipados con un orden. En ese caso los límites pueden no existir y los problemas de decisión asociados se vuelven indecidibles.[2]
En este trabajo generalizaremos las técnicas de Shelah y Compton, lo que nos permitirá extender sus resultados a nuevos tipos de estructuras no estudiadas anteriormente, como conjuntos equipados con una permutación y grafos sparse. Además, demostraremos nuevos resultados como que para todo real computable \(\alpha\in(0,1)\) existe una fórmula \(\phi\) en la lógica de primer orden de grafos equipados con un orden tal que \(lim_{n\rightarrow\infty} \ Pr(\mathbf{G}(n)\models\phi)=\alpha{}\)
Trabajo en conjunto con: Sergio Alejandro Abriola (Universidad de Buenos Aires, Argentina).
Referencias
[1] Fagin, R. (1976). Probabilities on finite models. The Journal of Symbolic Logic, 41, 50–58.
[2] Shelah, S., & Compton, K. (1987). Nonconvergence, undecidability, and intractability in asymptotic problems. The Journal of Pure and Applied Logic, 36, 207-224.