From: rld@math.ohio-state.edu (Randall Dougherty) Subject: Re: planar graphs and first-order definability Date: 7 Sep 1999 20:06:43 GMT Newsgroups: sci.math Keywords: Ehrenfeucht-Fraisse games In article , Allan Adler wrote: >That sounds pretty neat. Where can one find an exposition of >these Ehrenfeucht-Fraisse games? One place is chapter 26 of Monk's "Mathematical Logic." (If anyone knows of an exposition for a wider audience with less notation and more examples, please let me know.) I think the first place where it was written about in explicit game form was a paper of Ehrenfeucht: Fundamenta Mathematicae 49 (1961), 129-141. Randall Dougherty rld@math.ohio-state.edu Department of Mathematics, Ohio State University, Columbus, OH 43210 USA "I have yet to see any problem, however complicated, that when looked at in the right way didn't become still more complicated." Poul Anderson, "Call Me Joe" ============================================================================== [From MathSciNet --djr] [Note: they're actually Ehrenfeucht-Fra�ss� games --djr] 82a:03033 03C80 (03C95 68F05 90D45) Weese, Martin Generalized Ehrenfeucht games. Fund. Math. 109 (1980), no. 2, 103--112. [To journal home page] [...] In 1961, A. Ehrenfeucht formulated a game-theoretic criterion for elementary equivalence of two structures. This criterion has since been generalized to many nonelementary logics, including those with the quantifiers mentioned above as well as many others. [...] Reviewed by John Cowles _________________________________________________________________ 23 #A3666 02.50 Ehrenfeucht, A. An application of games to the completeness problem for formalized theories. Fund. Math. 49 1960/1961 129--141. [To journal home page] Model-theoretic results are given for the lower predicate calculus with identity, the set-theoretic $\varepsilon$-relation and any set $A$ of additional predicates. (A preliminary account was given in Bull. Acad. Polon. Sci. Cl. III 5 (1957), 35--37, IV [MR 19, 4].) Given such a formal system, all models are considered in which the variables range over individuals and finite sets, each predicate of $A$ is a relation among individuals, and a specified singulary predicate of $A$ identifies the individuals. Models $M$ and $N$ are called "indiscernible" if, for any closed formula, satisfaction in $M$ is equivalent to satisfaction in $N$. It is shown that a sufficient, but not necessary, condition that $M$ and $N$ be indiscernible is that, for each positive integer $n$, the second player have a winning strategy in the game $H\sb n(M,N)$ defined thus. $H\sb n(M,N)$ is an $n$-move game. In each move, the first player chooses one of the two models and points out a finite sequence of individuals in it; then the second player pairs each individual of the sequence with an individual in the other model. Let $(a\sb 1,b\sb 1),\cdots,(a\sb p,b\sb p)$, where the $a$'s are in $M$ and $b$'s are in $N$, be the sequence of pairs resulting from a play of the game. The condition for the second player to win is that, for each predicate $\alpha$ in $A$---say with $v$ variables and interpretations $\alpha\sb M$ and $\alpha\sb N$ in the respective models---the following is true: for all $v$-tuples $(i\sb 1,\cdots,i\sb v)$ of integers from 1 to $p,\alpha\sb M(a\sb {i\sb 1},\cdots,a\sb {i\sb v})\equiv\alpha\sb N(b\sb {i\sb 1},\cdots,b\sb {i\sb v})$. A second set of results is obtained regarding satisfaction of a particular subset of closed formulas (roughly speaking, those that express statements about individuals). Models $M$ and $N$ are called "elementarily indiscernible" if, for any formula of this particular subset, satisfaction in $M$ is equivalent to satisfaction in $N$. A sufficient condition that $M$ and $N$ be elementarily indiscernible is that, for each positive integer $n$, the second player have a winning strategy in the game $G\sb n(M,N)$, which differs from $H\sb n(M,N)$ in that in each move the first player points out a single individual. This condition is not in general necessary, but it is necessary whenever $A$ is finite. The game-theoretic results are applied to three particular formalized theories of ordinal numbers. For each theory, infinitely many infinite classes of indiscernible models are found. Moreover, the same techniques lead to necessary and sufficient conditions that an ordinal number be definable in the respective theories. Reviewed by G. F. Rose _________________________________________________________________ 19,4d 02.0X Ehrenfeucht, A. Application of games to some problems of mathematical logic. (English. Russian summary) Bull. Acad. Polon. Sci. Cl. III. 5 (1957), 35--37, IV,. This is a preliminary report and the proofs of the theorems contained in it will be published in Fund. Math. It contains a necessary and sufficient condition for elementary indiscernibility of models, a sufficient condition for the indiscernibility of models by means of finite sets and three theorems, the second of which is the following: If player II has a winning method in $H\sb n(M',M")$ for every $n$, then $M'$ and $M"$ are indiscernible by finite sets. Here $H\sb n(M',M")$ is a game in which the two players I and II make $n$ moves, and $M'$ and $M"$ are two models for an elementary theory $T$ which has no terms and a finite number of predicates only. The set of these predicates is denoted by $P$. In every move the player I points out an arbitrary finite number $m$ of elements either from $\vert M'\vert $ or from $\vert M"\vert $, where $\vert M\vert $ denotes the set of individuals of $M$. Player II has to match every individual pointed out by I with an individual in the other model. Player II wins if for any predicate $\alpha\in P$ and any finite sequence $k\sb 1,\cdots,k\sb {a(\alpha)}$, where $1\leq k\sb i\leq n$, $\text{stsf}\sb {M'}\alpha(a'{}\sb {k\sb {{1}}},\cdots,a\sb {ka(\alpha)})$ if, and only if, $\text{stsf}\sb {M"}\alpha(a\sb {k\sb {{\bf 1}}}{}",\cdots,a\sb {ka(\alpha)}{}")$. All notations concerning theories and models are those used by Ehrenfeucht and Mostowski [Fund. Math. 43 (1956), 50--68; MR 18, 863]. Reviewed by B. Germansky � Copyright American Mathematical Society 2000