Juego Ehrenfeucht-Frais

Los juegos Ehrenfeucht-Frais ( a veces juegos de ida y vuelta ) son una técnica para determinar si dos estructuras son elementalmente equivalentes a . La principal aplicación de los juegos de Ehrenfeucht-Frais es la prueba de la imposibilidad de expresar ciertas propiedades en lógica de primer orden . Además, los juegos de Ehrenfeucht-Frais proporcionan una metodología completa para probar la imposibilidad de expresar propiedades en lógica de primer orden. En este papel, estos juegos son especialmente importantes en la teoría de modelos finitos y sus aplicaciones en informática (especialmente en la verificación informática y la teoría de bases de datos). ) porque los juegos de Ehrenfeucht-Frais son una de las pocas técnicas en la teoría de modelos que son válidas en el contexto de modelos finitos. Otras técnicas ampliamente utilizadas para demostrar la imposibilidad de expresar propiedades, comoel teorema de compacidad, no funcionan para modelos finitos.

Juegos como el juego Ehrenfeucht-Frais también se pueden definir para otras lógicas, como la lógica de punto fijo [1] y los juegos de fichas para lógicas con un número finito de variables. Las extensiones son lo suficientemente poderosas para describir la definibilidad en la lógica existencial de segundo orden .

Idea principal

La idea principal del juego es que tenemos dos estructuras y dos jugadores (definidos a continuación). Uno de los jugadores quiere mostrar que estas dos estructuras son distintas, mientras que el otro jugador quiere mostrar que son elementalmente equivalentes a (satisfacer las mismas oraciones de primer orden). El juego se juega en rondas. La ronda se desarrolla de la siguiente manera: Primero, el primer jugador Innovador [2] selecciona cualquier elemento de una de las estructuras, y el otro jugador selecciona un elemento de otra estructura. El objetivo del segundo jugador siempre es seleccionar un elemento que sea "similar" al elemento elegido por el Innovador . El segundo jugador ( el Conservador ) gana si hay un isomorfismo entre los elementos elegidos en dos estructuras diferentes.

El juego termina en un número fijo de pasos ( ) ( ordinal , pero generalmente un número finito o ). $\gama$ $\omega$

Definición

Supongamos que se nos dan dos estructuras y con el mismo conjunto de relaciones de caracteres y se nos da un número natural fijo n . Entonces podemos definir el juego Ehrenfeucht-Frais como un juego entre dos jugadores, el Innovador y el Conservador , de la siguiente manera: ${\mathfrak {A}}$ ${\mathfrak {B}}$ $G_{n}({\mathfrak {A}),{\mathfrak {B)))$

El primer jugador, Innovador , elige un miembro de estructura o un miembro de estructura . $un_{1}$ ${\mathfrak {A}}$ $b_{1}$ ${\mathfrak {B}}$
Si el Innovador selecciona un miembro de la estructura , el Conservador selecciona un miembro de la estructura . De lo contrario, el Conservador selecciona a un miembro de la estructura . ${\mathfrak {A}}$ $b_{1}$ ${\mathfrak {B}}$ $un_{1}$ ${\mathfrak {A}}$
El innovador selecciona un miembro de estructura o un miembro de estructura . $un_{2}$ ${\mathfrak {A}}$ $b_{2}$ ${\mathfrak {B}}$
El conservador selecciona un elemento o en el modelo del que Novator no seleccionó. $un_{2}$ $b_{2}$
El Innovador y el Conservador continúan seleccionando miembros de las estructuras y todavía están en los pasos. ${\mathfrak {A}}$ ${\mathfrak {B}}$ $n-2$
Al final del juego, hemos elegido varios elementos de estructura y estructura . Por lo tanto, tenemos dos estructuras en el conjunto , una obtenida de la estructura por mapeo a , y la otra obtenida de la estructura por reflexión a . El conservador gana si estas estructuras son las mismas. El innovador gana si no son iguales. $a_{1},\puntos,a_{n}$ ${\mathfrak {A}}$ ${\displaystyle b_{1},\puntos,b_{n))$ ${\mathfrak {B}}$ ${\ estilo de visualización \ {1, \ puntos, n \}}$ ${\mathfrak {A}}$ $i$ $ai}$ ${\mathfrak {B}}$ $i$ $bi}$

Para cualquier n , definimos la relación si el conservador gana el juego de n - movimientos . Todas estas son relaciones de equivalencia en la clase de estructuras con símbolos relacionales dados. La intersección de todas estas relaciones es nuevamente una relación de equivalencia . ${\mathfrak {A}}{\stackrel {n}{\sim}}{\mathfrak {B}}$ $G_{n}({\mathfrak {A}),{\mathfrak {B)))$ ${\mathfrak{A}}\sim {\mathfrak{B}}$

Es fácil probar que si el Conservador gana el juego para todo n , es decir , entonces y son elementalmente equivalentes. Si el conjunto de relaciones de caracteres es finito, lo contrario también es cierto. ${\mathfrak{A}}\sim {\mathfrak{B}}$ ${\mathfrak {A}}$ ${\mathfrak {B}}$

Historia

El método de lanzadera (o método de selección) utilizado en el juego Ehrenfeucht-Frais para verificar la equivalencia elemental fue propuesto por Roland Freise en su disertación [3] [4] . El método fue formulado en forma de juego por Andrzej Ehrenfeucht [5] . Los nombres Spoiler y Duplicator fueron dados por Joel Spencer [6] . Los nombres Eloise y Abelard también se usan (y a menudo se indicany) después de los nombres de Eloise y Abelard , siguiendo el esquema de nombres propuesto por Wilfried Hodgis en su libro Model Theory . $\existe$ $\para todos$

Lectura para leer más

El capítulo 1 del libro de Poise sobre teoría de modelos [7] contiene una introducción al juego Ehrenfeucht-Frais. Los capítulos 6, 7 y 13 del libro de Rosenstein sobre órdenes lineales [8] también contienen una introducción al juego. Se pueden encontrar ejemplos simples del juego Ehrenfeucht-Frais en una de las columnas MathTrek de Ivars Peterson [9] .

En el libro de Vereshchagin y Shen [10] se puede encontrar una introducción al juego Ehrenfeucht-Frais y algunos ejemplos simples de este juego .

Las diapositivas de Fokion Kolaitis [11] y el capítulo del libro de Neil Immerman [12] sobre juegos Ehrenfeucht-Frais discuten aplicaciones en informática, un teorema metodológico para probar la inexpresabilidad y algunas pruebas simples de inexpresabilidad usando esta metodología.

Notas

↑ Bossé, 1993 , pág. 100–114.
↑ Se utiliza la terminología del libro de Vereshchagin y Shen ( Vereshchagin, Shen 2008 ). En la versión en inglés Novator=Spoiler, Conservative=Duplicator. En el libro, el juego se llama el juego Ehrenfeucht y se dan algunos ejemplos de juegos simples para transmitir la idea.
↑ Fraisse, 1950 , p. 1022-1024.
↑ Fraisse, 1954 , p. 35-182.
↑ Ehrenfeucht, 1961 , pág. 129-141.
↑ Enciclopedia de Filosofía de Stanford, entrada sobre Lógica y Juegos.
↑ Poizat, 2000 .
↑ Rosenstein, 1982 .
↑ Un ejemplo de un juego Ehrenfeucht-Frais.
↑ Vereshchaguin, Shen, 2008 .
↑ Curso de juegos combinatorios en teoría de modelos finitos por Phokion Kolaitis
↑ Immerman, 1999 , pág. Capítulo 6.

Literatura

Vereshchagin N.K., Shen A. Conferencias sobre lógica matemática y teoría de algoritmos. Parte 2. Lenguajes de cálculo.. - Moscú, 2008. - P. 143. - ISBN 978-5-94057-322-7 .
Uwe Bossé. An Ehrenfeucht–Fraïssé game for fixpoint logic and estratified fixpoint logic // Computer Science Logic: 6th Workshop, CSL'92, San Miniato, Italy, 28 de septiembre - 2 de octubre de 1992. Artículos seleccionados / Egon Börger. - Springer-Verlag , 1993. - T. 702. - S. 100-114. — (Apuntes de clase en informática). — ISBN 3-540-56992-8 .
Roland Fraisse. Sur una nueva clasificación de los sistemas de relaciones // Comptes Rendus. - 1950. - Emisión. 230 .
Roland Fraisse. Sur quelques clasificaciones des sistemas de relaciones. - París, 1953. - (tesis). Publicado en
- Roland Fraisse. Publicaciones Scientifiques de l'Université d'Alger. - 1954. - (serie A).
Ehrenfeucht A. {{{título}}} // Fundamenta Mathematicae. - 1961. - Emisión. 49 .
Bruno Poizat. Un curso de teoría de modelos / tr. Moisés Klein. — Nueva York: Springer-Verlag, 2000.
José G. Rosenstein. Órdenes Lineales. - Nueva York: Prensa Académica, 1982.
Neil Immerman. capítulo 6 // Complejidad descriptiva . - Springer, 1999. - ISBN 978-0-387-98600-5 .
Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Marx Maarten, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein. Teoría de modelos finitos y sus aplicaciones. - Berlín: Springer-Verlag , 2007. - (Textos de Informática Teórica. Serie EATCS). - ISBN 978-3-540-00428-8 .

Enlaces

Seis conferencias sobre juegos de Ehrenfeucht-Fraïssé en el CLUB DE EXPLORADORES DE MATEMÁTICAS, Departamento de Matemáticas de Cornell.
Modeloids I, Miroslav Benda, Transactions of the American Mathematical Society, vol. 250 (junio de 1979), págs. 47-90 (44 páginas)