I've been reading recently about Ehrenfeucht-Fraisse games. It is easy for me to understand it if it's played on two Kripke models: legal moves for both players (Spoiler and Duplicator) are those respecting both accesibilily and forcing relations on associated structures. Furthermore, I understand the equivalence between bisimilarity of two models and winning strategy for Duplicator (although I am not able to formally prove it yet).

But what if we have some vocabulary with more than one binary relation? What if we have relations with arity greater than $2$? How is EF game then played? I would be glad if someone can clarify this.

  • $\begingroup$ Does the definition on Wikipedia make sense to you? If not, what do you find confusing? $\endgroup$ – Alex Kruckman May 25 '18 at 17:01
  • $\begingroup$ On second reading, I see you require the moves in the game to respect the forcing relation in addition to the accessibility relation. So maybe you're referring to a nonstandard kind of Ehrenfeucht-Fraïssé game that's defined to correspond to bisimilarity in Kripke models instead of elementary equivalence in first-order structures. $\endgroup$ – Alex Kruckman May 25 '18 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.