Juego de Ehrenfeucht-Fraïssé, etc.

Febrero 5, 2008
En este juego, dados dos modelos \mathfrak A y \mathfrak B, la jugadora \exists (Eloísa, o la jugadora “constructora”, o II) trata de demostrar que dos modelos \mathfrak A y \mathfrak B son isomorfos; mientras tanto, el jugador \forall (Abelardo, o el “aguafiestas”, o I) trata de mostrar que no lo son.
En la versión EF_n({\mathfrak A},{\mathfrak B}), Abelardo “desafía” a Eloísa escogiendo un punto no escogido x_i todavía en A o en B, y Eloísa debe responder escogiendo otro elemento y_i del otro modelo tal que el isomorfismo se mantenga al agregar la pareja (x_i,y_i) (o (y_i,x_i), dependiendo de la escogencia de Abelardo) a lo ya escogido. Abelardo tiene n oportunidades para desafiar a Eloísa, y esta tiene n oportunidades para responder manteniendo el isomorfismo parcial.
Gana Eloísa si logra responder las n veces. De lo contrario gana Abelardo.
En la versión EF_\omega({\mathfrak A},{\mathfrak B}) Abelardo tiene \omega oportunidades de desafiar a Eloísa.
EF_\omega({\mathfrak A},{\mathfrak B}) es un juego cerrado, luego por Gale-Stewart es determinado.
Relacionado con  EF_\omega({\mathfrak A},{\mathfrak B}) están la relación {\mathcal A}\approx_p {\mathcal B} y la noción de conjunto de back & forth (CB&F). No es difícil ver que Eloísa tiene una estrategia ganadora para EF_\omega({\mathfrak A},{\mathfrak B}) si y solo si existe un CB&F para {\mathfrak A} y {\mathfrak B}.
No alcanzamos ayer a ver que para  EF_n({\mathfrak A},{\mathfrak B}) sucede algo análogo a lo anterior: en lugar de un CB&F hay que considerar una sucesión de back & forth (SB&F) – ver página 57: una “versión estratificada” de los CB&Fs.
Al igual que en el caso de \approx_p, tenemos ahora la relación de equivalencia asociada a existencia de SB&Fs de longitud n,  {\mathcal A}\approx_p ^n{\mathcal B}. Y no es difícil verificar que {\mathcal A}\approx_p^n {\mathcal B} si y solo si Eloísa tiene una estrategia ganadora para EF_n({\mathcal A},{\mathcal B}).

Deja un Comentario » | matemática | Etiquetado: | Permalink
Escrito por Andrés Villaveces