Juego de Ehrenfeucht–Fraïssé, ¿cómo puedo entenderlo?

Question

Mi curso de "Métodos formales" trata sobre los juegos de Ehrenfeucht-Fraïssé, especialmente en lo que respecta a la inexresabilidad en lógica FO.

De momento entiendo completamente qué son estos juegos y cómo se supone que deben funcionar. Pero no logro comprender varios teoremas sobre la inexpressabilidad, probablemente porque me faltan ciertos conceptos básicos.

He intentado leer el segundo capítulo de "Elementos de la teoría de modelos finitos" de Leonid Libkin pero fracasé bastante en ello.

¿Cuáles son los conceptos principales que debo entender antes de abordar directamente los juegos de Ehrenfeucht-Fraïssé? ¿Hay fuentes destacadas disponibles?

Answer 1

Aprendí sobre los juegos de Ehrenfeucht–Fraïssé a partir de las maravillosas notas informales del Prof. Moschovakis, las cuales se pueden encontrar aquí. Estas notas se utilizan en la secuencia de lógica de primer año de posgrado en UCLA, por lo que no asumen demasiado en cuanto a antecedentes. De hecho, estos juegos fueron cubiertos en el primer trimestre de la clase, así que no creo que fuera necesario estar familiarizado con algo más que lógica de primer orden y teoría de modelos elementales.