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:

Erin (the spoiler) and Fred (the copier).

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.

Erin always goes first. In this game, the choices from the left ordinal (7) match the order of the choices from the right ordinal (8), and so Fred wins.

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.

3 thoughts on “Get Started Playing Ehrenfeucht-Fraisse Games

  1. Yuri

    Hi Bryan,

    Unfortunately I can’t find your PDF file.
    Would you happen to still be able to upload or send it?