Ehrenfeucht–Fraïssé game
   HOME

TheInfoList



OR:

In the
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
discipline of
model theory In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, the Ehrenfeucht–Fraïssé game (also called back-and-forth games) is a technique based on
game semantics Game semantics (german: dialogische Logik, translated as ''dialogical logic'') is an approach to Formal semantics (logic), formal semantics that grounds the concepts of truth or Validity (logic), validity on game theory, game-theoretic concepts, su ...
for determining whether two
structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
s are
elementarily equivalent In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature ''σ'' are called elementarily equivalent if they satisfy the same first-order ''σ''-sentences. If ''N'' is a substructure of ''M'', one often ...
. The main application of Ehrenfeucht–Fraïssé games is in proving the inexpressibility of certain properties in first-order logic. Indeed, Ehrenfeucht–Fraïssé games provide a complete methodology for proving inexpressibility results for
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
. In this role, these games are of particular importance in finite model theory and its applications in computer science (specifically
computer aided verification In computer science, the International Conference on Computer-Aided Verification (CAV) is an annual academic conference on the theory and practice of computer-aided formal analysis of software and hardware systems, broadly known as formal methods ...
and
database theory Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems. Theoretical aspects of data management include, among other areas, the foundations of q ...
), since Ehrenfeucht–Fraïssé games are one of the few techniques from model theory that remain valid in the context of finite models. Other widely used techniques for proving inexpressibility results, such as the
compactness theorem In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful (but generally no ...
, do not work in finite models. Ehrenfeucht–Fraïssé-like games can also be defined for other logics, such as
fixpoint logic In mathematical logic, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by descriptive complexity theory and their relationship to database query lan ...
s and
pebble game In mathematics and computer science, a pebble game is a type of mathematical game played by placing "pebbles" or "markers" on a directed acyclic graph according to certain rules: * A given step of the game consists of either placing a pebble on an ...
s for finite variable logics; extensions are powerful enough to characterise definability in
existential second-order logic In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-order logic quantifies onl ...
.


Main idea

The main idea behind the game is that we have two structures, and two players – ''Spoiler'' and ''Duplicator''. Duplicator wants to show that the two structures are
elementarily equivalent In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature ''σ'' are called elementarily equivalent if they satisfy the same first-order ''σ''-sentences. If ''N'' is a substructure of ''M'', one often ...
(satisfy the same first-order
sentences ''The Four Books of Sentences'' (''Libri Quattuor Sententiarum'') is a book of theology written by Peter Lombard in the 12th century. It is a systematic compilation of theology, written around 1150; it derives its name from the ''sententiae'' o ...
), whereas Spoiler wants to show that they are different. The game is played in rounds. A round proceeds as follows: Spoiler chooses any element from one of the structures, and Duplicator chooses an element from the other structure. In simplified terms, the Duplicator's task is to always pick an element "similar" to the one that the Spoiler has chosen, whereas the Spoiler's task is to choose an element for which no "similar" element exists in the other structure. Duplicator wins if there exists an isomorphism between the eventual substructures chosen from the two different structures; otherwise, Spoiler wins. The game lasts for a fixed number of steps \gamma (which is an ordinal – usually a finite number or \omega).


Definition

Suppose that we are given two structures \mathfrak and \mathfrak, each with no
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
symbols and the same set of
relation Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...
symbols, and a fixed
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
''n''. We can then define the Ehrenfeucht–Fraïssé game G_n(\mathfrak,\mathfrak) to be a game between two players, Spoiler and Duplicator, played as follows: # The first player, Spoiler, picks either a member a_1 of \mathfrak or a member b_1 of \mathfrak. # If Spoiler picked a member of \mathfrak, Duplicator picks a member b_1 of \mathfrak; otherwise, Duplicator picks a member a_1 of \mathfrak. # Spoiler picks either a member a_2 of \mathfrak or a member b_2 of \mathfrak. # Duplicator picks an element a_2 or b_2 in the model from which Spoiler did not pick. # Spoiler and Duplicator continue to pick members of \mathfrak and \mathfrak for n-2 more steps. # At the conclusion of the game, we have chosen distinct elements a_1, \dots, a_n of \mathfrak and b_1, \dots, b_n of \mathfrak. We therefore have two structures on the set \, one induced from \mathfrak via the map sending i to a_i, and the other induced from \mathfrak via the map sending i to b_i. Duplicator wins if these structures are the same; Spoiler wins if they are not. For each ''n'' we define a relation \mathfrak \ \overset\ \mathfrak if Duplicator wins the ''n''-move game G_n(\mathfrak,\mathfrak). These are all equivalence relations on the class of structures with the given relation symbols. The intersection of all these relations is again an equivalence relation \mathfrak \sim \mathfrak.


Equivalence and inexpressibility

It is easy to prove that if Duplicator wins this game for all finite ''n'', that is, \mathfrak \sim \mathfrak, then \mathfrak and \mathfrak are elementarily equivalent. If the set of relation symbols being considered is finite, the converse is also true. If a property Q is true of \mathfrak but not true of \mathfrak, but \mathfrak and \mathfrak can be shown equivalent by providing a winning strategy for Duplicator, then this shows that Q is inexpressible in the logic captured by this game.


History

The
back-and-forth method In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular it can be used to prove that * any t ...
used in the Ehrenfeucht–Fraïssé game to verify elementary equivalence was given by
Roland Fraïssé Roland Fraïssé (; 12 March 1920 – 30 March 2008) was a French mathematical logician. Fraïssé received his doctoral degree from the University of Paris in 1953. In his thesis, Fraïssé used the back-and-forth method to determine whether t ...
in his thesis; it was formulated as a game by
Andrzej Ehrenfeucht Andrzej Ehrenfeucht (, born 8 August 1932) is a Polish-American mathematician and computer scientist. Life Andrzej Ehrenfeucht formulated the Ehrenfeucht–Fraïssé game, using the back-and-forth method given in Roland Fraïssé's PhD thesis. ...
. The names Spoiler and Duplicator are due to
Joel Spencer Joel Spencer (born April 20, 1946) is an American mathematician. He is a combinatorialist who has worked on probabilistic methods in combinatorics and on Ramsey theory. He received his doctorate from Harvard University in 1970, under the supervi ...
. Other usual names are Eloise icand Abelard (and often denoted by \exists and \forall) after Heloise and Abelard, a naming scheme introduced by
Wilfrid Hodges Wilfrid Augustine Hodges, FBA (born 27 May 1941) is a British mathematician and logician known for his work in model theory. Life Hodges attended New College, Oxford (1959–65), where he received degrees in both '' Literae Humaniores'' and (C ...
in his book ''Model Theory'', or alternatively Eve and Adam.


Further reading

Chapter 1 of Poizat's model theory text contains an introduction to the Ehrenfeucht–Fraïssé game, and so do Chapters 6, 7, and 13 of Rosenstein's book on linear orders. A simple example of the Ehrenfeucht–Fraïssé game is given in one of Ivars Peterson's MathTrek columns. Phokion Kolaitis' slidesCourse on combinatorial games in finite model theory by Phokion Kolaitis (.ps file)
/ref> and
Neil Immerman Neil Immerman (born 24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.
's book chapter on Ehrenfeucht–Fraïssé games discuss applications in computer science, the methodology for proving inexpressibility results, and several simple inexpressibility proofs using this methodology. Ehrenfeucht–Fraïssé games are the basis for the operation of derivative on modeloids
Modeloids
are certain equivalence relations and the derivative provides for a generalization of standard model theory.


References

*


External links



at MATH EXPLORERS' CLUB, Cornell Department of Mathematics.
Modeloids
I, Miroslav Benda, Transactions of the American Mathematical Society, Vol. 250 (Jun 1979), pp. 47 – 90 (44 pages) {{DEFAULTSORT:Ehrenfeucht-Fraisse Game Model theory