Affordable Access

Publisher Website

Chapter 6 The Ehrenfeucht-Fraïxsséa Game

Elsevier B.V.
DOI: 10.1016/s0079-8169(08)60591-7
  • Mathematics


Publisher Summary Suppose two linear orderings A and B are given. Two players, called player I and player II, play the following game. First, the player I picks an element from either A or B and player II picks an element from the other one. This procedure is repeated three times, so that when the game is completed, three (not necessarily distinct) elements of each linear ordering have been selected. At the very outset, either player I or player II can force a win in this game. This result, of course, follows from the general theorem of game theory that given any finite two-person game with complete information such that each play of the game ends in a victory for one of the two players, the first player has a winning strategy or the second player has a winning strategy. In general, of course, there is no need to restrict to the game with three moves. Thus for any fixed natural number n ≥ 1 and any linear orderings A and B have the game Gn(A, B), which is played as above with n rounds instead of three rounds. These games were first formulated by Ehrenfeucht, who used them in his analysis of the logical properties of the arithmetic of ordinals. A similar notion, without the game-theoretic terminology, had been formulated independently by Fraïssé.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

Trees and Ehrenfeucht–Fraı̈ssé games

on Annals of Pure and Applied Log... Jan 01, 1999

Ehrenfeucht games and ordinal addition

on Annals of Pure and Applied Log... Jan 01, 1997
More articles like this..