Timeline for What are some other uses for Ehrenfeucht-Fraïssé games?
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2021 at 11:24 | answer | added | FactEngine | timeline score: 1 | |
| Jan 18, 2013 at 16:55 | vote | accept | Cole Leahy | ||
| Jan 15, 2013 at 1:30 | answer | added | Jesse Alama | timeline score: 5 | |
| Oct 27, 2011 at 2:58 | answer | added | Zeeshan Mahmud | timeline score: 5 | |
| Aug 13, 2011 at 13:41 | comment | added | Emil Jeřábek | For games of length $\omega$ (or any limit ordinal for that matter) in a countable language, it does not matter whether the game is nested or unnested. | |
| Aug 12, 2011 at 23:13 | comment | added | François G. Dorais | No, unnested games are to deal with functions and constants (the two games are the same for a relational language). However, when he talks about the ranks of positions in the Karp game, he is basically talking about winning the Barwise game with that length. Since Hodge is more-or-less authoritative, I think it is fine to call your games EF games without further comments. We'll just leave this thread of comments here for those who are more familiar with the Barwise games. | |
| Aug 12, 2011 at 22:14 | comment | added | Cole Leahy | Are Barwise's games what Hodges calls unnested? | |
| Aug 12, 2011 at 22:12 | history | edited | Cole Leahy | CC BY-SA 3.0 |
Reflected disambiguating comment
|
| Aug 12, 2011 at 22:09 | comment | added | François G. Dorais | And yes, Karp's main result was that Duplicator wins $G_\omega(\mathfrak{A},\mathfrak{B})$ if and only if $\mathfrak{A}$ and $\mathfrak{B}$ are $L_{\infty,\omega}$-equivalent, which implies the result you stated. | |
| Aug 12, 2011 at 22:09 | comment | added | Cole Leahy | I see. I'll edit the question to flag this. | |
| Aug 12, 2011 at 22:07 | comment | added | François G. Dorais | I figured out the history here. On the one hand, the EF games I just described were introduced by Barwise. On the other hand, Karp studied the game $G_\omega(\mathfrak{A},\mathfrak{B})$ as you describe it. (Longer games have been studied by various later authors.) It appears that both variants have been called EF games... | |
| Aug 12, 2011 at 22:06 | comment | added | Cole Leahy | I would believe it if you told me that unnested EF games are more useful than the ones I described. Do you care to elaborate? | |
| Aug 12, 2011 at 22:06 | comment | added | Cole Leahy | François, I just copied the definition from pp. 95 to 96 of Hodges's treatise on model theory. Theorem 3.2.3 there states that, in the finite or countable case, Duplicator wins $G_\omega(\mathfrak{A}, \mathfrak{B})$ iff $\mathfrak{A}$ and $\mathfrak{B}$ are isomorphic. Perhaps you're thinking of what on p. 102 Hodges calls "unnested" EF games. Corrollary 3.3.3 states that $\mathfrak{A}$ and $\mathfrak{B}$ are elementarily equivalent iff Duplicator wins every such game of finite length. This fits with your second comment. | |
| Aug 12, 2011 at 21:41 | history | edited | Cole Leahy |
Added big-list tag.
|
|
| Aug 12, 2011 at 21:15 | comment | added | François G. Dorais | Also, Duplicator wins $G_\omega(\mathfrak{A},\mathfrak{B})$ if and only if $\mathfrak{A}$ and $\mathfrak{B}$ are elementarily equivalent. When $\mathfrak{A}$ and $\mathfrak{B}$ are finite or countable and Duplicator wins the $G_\gamma(\mathfrak{A},\mathfrak{B})$ game for every ordinal $\gamma$, then $\mathfrak{A}$ and $\mathfrak{B}$ are isomorphic. | |
| Aug 12, 2011 at 21:13 | comment | added | François G. Dorais | This is not how EF games are defined for ordinals $\gamma \geq \omega$. The plays of an EF game are always finite. At each move, Spoiler picks an ordinal smaller than the previous one he played, or smaller than $\gamma$ if this is the first move. The game ends when Spoiler picks the ordinal 0, which is bound to happen in finitely many steps. | |
| Aug 12, 2011 at 20:51 | history | asked | Cole Leahy | CC BY-SA 3.0 |