Get Started Playing Ehrenfeucht-Fraisse Games
Ehrenfeucht-Fraisse games are a very useful method in logic, when you’re trying to figure out if two models are elementarily (logically) equivalent or not. This may be of special interest to philosophers of science, since the ’empirical equivalence’ of two models is much better characterized by elementary equivalence than it is by isomorphism.
At any rate, I’ve written a friendly introduction to this method (PDF). Here’s a little of what you’ll find there.
Ehrenfeucht-Fraisse games involve two players: a copier (who tries to copy the other player’s moves), and a spoiler (who tries to spoil the other player’s copying). I call the players, Erin and Fred:
All that Erin and Fred need to play a game is a pair of models (L-structures) M and N. The ordinals are nice, simple structures that can be used to illustrate how this works, so let’s make M and N two ordinals — say 7 and 8. We begin by setting the number of moves in the game — say 3.
Game play then consists of Erin first choosing an element of one ordinal, followed by Fred choosing an element of the other ordinal. The game is over when they’ve each chosen three elements. If the 3 elements from 7 are in the same order as the three elements of 8, the Fred (the copier) wins. If they’re not, then Erin (the spoiler) wins. Below is an example game in which Fred has won.
One of the most interesting applications of these games in model theory is established by a theorem due to Ehrenfeucht:
Theorem: Two L-structures M and N are elementarily equivalent iff for every Ehrenfeucht-Fraisse game on M and N, Fred has a winning strategy.
This fact has led to many interesting results, including a simple proof of which ordinals are elementarily equivalent. If this sounds interesting, it is! For more details, see my friendly introduction (PDF).
Comments and suggestions are always appreciated. Enjoy!
Soul Physics is authored by Bryan W. Roberts. Thanks for subscribing.
Want more Soul Physics? Try the Soul Physics Tweet.
- Another Unexpectedly Simple Failure of Determinism
- How Time Really Passes
Much more accessible introduction than in wikipedia(the real one, not simple.wikipedia.org:-)
BTW, link to pdf seems to be broken.
Hi Bryan,
Unfortunately I can’t find your PDF file.
Would you happen to still be able to upload or send it?
Regards,
Yuri
Thanks for letting me know, I’ve fixed the link — it should be accessible now!