# Logic and Games

*First published Fri Jul 27, 2001; substantive revision Thu Jan 8, 2009*

Games between two players, of the kind where one player wins and one loses, became a familiar tool in many branches of logic during the second half of the twentieth century. Important examples are semantic games used to define truth, back-and-forth games used to compare structures, and dialogue games to express (and perhaps explain) formal proofs.

- 1. Games in the History of Logic
- 2. Logical Games
- 3. Semantic Games
- 4. More Semantic Games
- 5. Back-and-Forth Games
- 6. Games of dialogue, communication and proof
- 7. Other Model-theoretic Games
- Bibliography
- Other Internet Resources
- Related Entries

## 1. Games in the History of Logic

The links between logic and games go back a long way. If one thinks of
a debate as a kind of game, then
Aristotle
already made the connection;
his writings about syllogism are closely intertwined with his study of
the aims and rules of debating. Aristotle's viewpoint survived into the
common medieval name for logic: *dialectics*. In the mid
twentieth century Charles Hamblin revived the link between dialogue and
the rules of sound reasoning, soon after Paul Lorenzen had connected
dialogue to constructive foundations of logic.

There are close links between games and teaching. Writers throughout
the medieval period talk of dialogues as a way of
‘teaching’ or ‘testing’ the use of sound
reasoning. We have at least two textbooks of logic from the early
sixteenth century that present it as a game for an individual student,
and Lewis Carroll's *The Game of Logic* (1887) is a more recent
example in the same genre.

Mathematical game theory was founded in the early twentieth century. Although no mathematical links with logic emerged until the 1950s, it is striking how many of the early pioneers of game theory are also known for their contributions to logic: John Kemeny, J. C. C. McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo and others. In 1953 David Gale and Frank Stewart made fruitful connections between set theory and games. Shortly afterwards Leon Henkin suggested a way of using games to give semantics for infinitary languages.

The first half of the twentieth century was an era of increasing rigour and professionalism in logic, and to most logicians of that period the use of games in logic would probably have seemed frivolous. The intuitionist L. E. J. Brouwer expressed this attitude when he accused his opponents of causing mathematics ‘to degenerate into a game’ (as David Hilbert quoted him in 1927). Hermann Weyl used the notion of games to explain Hilbert's metamathematics: mathematical proofs proceed like plays of a meaningless game, but we can stand outside the game and ask meaningful questions about it. Wittgenstein's language games provoked little response from the logicians. But in the second half of the century the centre of gravity of logical research moved from foundations to techniques, and from about 1960 games were used more and more often in logical papers.

## 2. Logical Games

From the point of view of game theory, the games that appear in logic are not at all typical. They normally involve just two players, they often have infinite length, the only outcomes are winning and losing, and no probabilities are attached to actions or outcomes. The barest essentials of a logical game are as follows.

There are two players. In general we can call them ∀ and ∃. The pronunciations ‘Abelard’ and ‘Eloise’ go back to the mid 1980s and usefully fix the players as male and female (though feminist logicians have asked about the propriety of this type-casting). Other names are in common use for the players in particular types of logical game.

The players play by choosing elements of a set Ω, called the
*domain* of the game. As they choose, they build up a
sequence

a_{0},a_{1},a_{2}, …

of elements of Ω. Infinite sequences of elements of Ω
are called *plays*. Finite sequences of elements of Ω are
called *positions*; they record where a play might have got to
by a certain time. A function τ (the *turn function* or
*player function*) takes each position **a** to
either ∃ or ∀; if τ(**a**) = ∃,
this means that when the game has reached **a**, player
∃ makes the next choice (and likewise with ∀). The game
rules define two sets W_{∀} and W_{∃}
consisting of positions and plays, with the following properties: if a
position **a** is in W_{∀} then so is any
play or longer position that starts with **a** (and
likewise with W_{∃}); and no play is in both
W_{∀} and W_{∃}. We say that player
∀ *wins* a play **b**, and that
**b** is a *win* for ∀, if
**b** is in W_{∀}; if some position
**a** that is an initial segment of **b** is
in W_{∀}, then we say that player ∀ *wins
already at* **a**. (And likewise with ∃ and
W_{∃}.) So to summarise, a logical game is a 4-tuple
(Ω, τ, W_{∀}, W_{∃}) with the
properties just described.

We say that a logical game is *total* if every play is in
either W_{∀} or W_{∃}, so that there are
no draws. Unless one makes an explicit exception, logical games are
always assumed to be total. (Don't confuse being total with the much
stronger property of being determined—see below.)

It is only for mathematical convenience that the definition above
expects the game to continue to infinity even when a player has won at
some finite position; there is no interest in anything that happens
after a player has won. Many logical games have the property that in
every play, one of the players has already won at some finite position;
games of this sort are said to be *well-founded*. An even
stronger condition is that there is some finite number *n* such
that in every play, one of the players has already won by the
*n*-th position; in this case we say that the game has
*finite length*.

A *strategy* for a player is a set of rules that describe
exactly how that player should choose, depending on how the two players
have chosen at earlier moves. Mathematically, a strategy for
∀ consists of a function which takes each position
**a** with τ(**a**) = ∀ to an
element *b* of Ω; we think of it as an instruction to
∀ to choose *b* when the game has reached the position
**a**. (Likewise with a strategy for ∃.) A strategy
for a player is said to be *winning* if that player wins every
play in which he or she uses the strategy, regardless of what the other
player does. At most one of the players has a winning strategy (since
otherwise the players could play their winning strategies against each
other, and both would win, contradicting that W_{∀} and
W_{∃} have no plays in common). Occasionally one meets
situations in which it seems that two players have winning strategies
(for example in the forcing games below), but closer inspection shows
that the two players are in fact playing different games.

A game is said to be *determined* if one or other of the
players has a winning strategy. There are many examples of games that
are not determined, as Gale and Stewart showed in 1953 using the axiom
of choice. This discovery led to important applications of the notion
of determinacy in the foundations of set theory. Gale and Stewart also
proved an important theorem that bears their name: Every well-founded
game is determined. It follows that every game of finite length is
determined—a fact already known to Zermelo in 1913. (A more
precise statement of the Gale-Stewart theorem is this. A game
*G* is said to be *closed* if ∃ wins every play of
*G* in which she hasn't already lost at any finite position. The theorem
states that every closed game is determined.)

Just as in classical game theory, the definition of logical games above serves as a clothes horse that we can hang other concepts onto. For example it is common to have some laws that describe what elements of Ω are available for a player to choose at a particular move. Strictly this refinement is unnecessary, because the winning strategies are not affected if we decree instead that a player who breaks the law loses immediately; but for many games this way of viewing them seems unnatural. Below we will see some other extra features that can be added to games.

The definitions of game and strategy above were purely mathematical. So they left out what is probably the single most important feature of games, which is that people play them (at least metaphorically). The players aim to win, and by studying the strategies open to them we study what behaviour is rational for a person with a particular aim. In most games there are several players, so we can study what is a rational response to somebody else's behaviour. By restricting the players' moves and possible strategies, we can study bounded rationality, where an agent has to make rational decisions under conditions of limited information, memory or time.

In short, games are used for modelling rationality and bounded rationality. This is independent of any connection with logic. But some logics were designed for studying aspects of rational behaviour, and in recent years it has become increasingly common to link these logics to suitable games. See section 4 'More semantic games' and its bibliography.

But until recently, logical games were connected with rational behaviour in a quite different way. On the surface, the logic in question had no direct connection with behaviour. But logicians and mathematicians noticed that some ideas could be made more intuitive if they were linked to possible aims. For example in many applications of logical games, the central notion is that of a winning strategy for the player ∃. Often these strategies (or their existence) turn out to be equivalent to something of logical importance that could have been defined without using games—for example a proof. But games are felt to give a better definition because they quite literally supply some motivation: ∃ is trying to win.

This raises a question that is not of much interest mathematically, but
it should concern philosophers who use logical games. If we want
∃'s motivation in a game *G* to have any explanatory
value, then we need to understand what is achieved if ∃ does win.
In particular we should be able to tell a realistic story of a
situation in which some agent called ∃ is trying to do something
intelligible, and doing it is the same thing as winning in the game. As
Richard Dawkins said, raising the corresponding question for the
evolutionary games of Maynard Smith,

The whole purpose of our search … is to discover a suitable actor to play the leading role in our metaphors of purpose. We … want to say, ‘It is for the good of … ‘. Our quest in this chapter is for the right way to complete that sentence. (The Extended Phenotype, Oxford University Press, Oxford 1982, page 91.)

For future reference let us call this the *Dawkins question*. In
many kinds of logical game it turns out to be distinctly harder to
answer than the pioneers of these games realised.

## 3. Semantic Games

In the early 1930s Alfred Tarski proposed a definition of truth. His
definition consisted of a necessary and sufficient condition for a
sentence in the language of a typical formal theory to be true; his
necessary and sufficient condition used only notions from syntax and
set theory, together with the primitive notions of the formal theory in
question. In fact Tarski defined the more general relation
‘formula
φ(*x*_{1},…, *x*_{n}) is true
of the elements *a*_{1},…,
*a*_{n}’; truth of a sentence is the special case
where *n* = 0. For example the question whether

‘For allxthere isysuch that R(x,y)’ is true

reduces to the question whether the following holds:

For every objectathe sentence ‘There isysuch that R(a,y)’ is true.

This in turn reduces to:

For every objectathere is an objectbsuch that the sentence ‘R(a,b)’ is true.

In this example, that's as far as Tarski's truth definition will take us.

In the late 1950s Leon Henkin noticed that we can intuitively understand some sentences which can't be handled by Tarski's definition. Take for example the infinitely long sentence

For allx_{0}there isy_{0}such that for allx_{1}there isy_{1}such that … R(x_{0},y_{0},x_{1},y_{1},…).

Tarski's approach fails because the string of quantifiers at the
beginning is infinite, and we would never reach an end of stripping
them off. Instead, Henkin suggested, we should consider the game where
a person ∀ chooses an object *a*_{0} for
*x*_{0}, then a second person ∃ chooses an object
*b*_{0} for *y*_{0}, then ∀
chooses *a*_{1} for *x*_{1}, ∃
chooses *b*_{1} for *y*_{1} and so on. A
play of this game is a win for ∃ if and only if the infinite
atomic sentence

R(a_{0},b_{0},a_{1},b_{1},…)

is true. The original sentence is true if and only if player ∃
has a winning strategy for this game. Strictly Henkin used the game
only as a metaphor, and the truth condition that he proposed was that
the skolemised version of the sentence is true, i.e. that there are
functions *f*_{0}, *f*_{1}, … such
that for every choice of *a*_{0},
*a*_{1}, *a*_{2} etc. we have

R(a_{0},f_{0}(a_{0}),a_{1},f_{1}(a_{0},a_{1}),a_{2},f_{2}(a_{0},a_{1},a_{ 2}), …).

But this condition translates immediately into the language of
games; the Skolem functions *f*_{0} etc. define a winning
strategy for ∃, telling her how to choose in the light of earlier
choices by ∀. (It came to light sometime later that C. S. Peirce
had already suggested explaining the difference between
‘every’ and ‘some’ in terms of who chooses the
object; for example in his second Cambridge Conference lecture of
1898.)

Soon after Henkin's work, Jaakko Hintikka added that the same idea
applies with conjunctions and disjunctions. We can regard a conjunction
‘φ
∧
ψ’ as a
universally quantified statement expressing ‘Every one of the
sentences φ, ψ holds’, so it should be for the player
∀ to choose one of the sentences. As Hintikka put it, to play
the game *G*(φ∧ψ), ∀ chooses whether the game should
proceed as *G*(φ) or as *G*(ψ). Likewise
disjunctions become existentially quantified statements about sets of
sentences, and they mark moves where the player ∃ chooses how the
game should proceed. To bring quantifiers into the same style, he
proposed that the game *G*(∀ *x*
φ(*x*)) proceeds thus: player ∀ chooses an object and
provides a name *a* for it, and the game proceeds as
*G*(φ(*a*)). (And likewise with existential
quantifiers, except that ∃ chooses.) Hintikka also made an
ingenious suggestion for introducing negation. Each game G has a
*dual game* which is the same as G except that the players
∀ and ∃ are transposed in both the rules for playing and
the rules for winning. The game *G*(¬φ) is the dual of
*G*(φ).

One can prove that for any first-order sentence φ, interpreted
in a fixed structure *A*, player ∃ has a winning strategy
for Hintikka's game *G*(φ) if and only if φ is true in
*A* in the sense of Tarski. Two features of this proof are
interesting. First, if φ is any first-order sentence then the game
*G*(φ) has finite length, and so the Gale-Stewart theorem
tells us that it is determined. We infer that ∃ has a winning
strategy in exactly one of *G*(φ) and its dual; so she has a
winning strategy in *G*(¬φ) if and only if she doesn't
have one in *G*(φ). This takes care of negation. And second,
if ∃ has a winning strategy for each game
*G*(φ(*a*)), then after choosing one such strategy
*f*_{a} for each *a*, she can string
them together into a single winning strategy for
*G*(∀*x* φ(*x*)) (namely, ‘Wait
and see what element *a* ∀ chooses, then play
*f*_{a}’). This takes care of the clause
for universal quantifiers; but the argument uses the axiom of choice,
and in fact it is not hard to see that the equivalence of Hintikka's
and Tarski's definitions of truth is equivalent to the axiom of choice
(given the other axioms of Zermelo-Fraenkel set theory).

It's puzzling that we have here two theories of when a sentence is true, and the theories are not equivalent if the axiom of choice fails. In fact the reason is not very deep. The axiom of choice is needed not because the Hintikka definition uses games, but because it assumes that strategies are deterministic, i.e. that they are single-valued functions giving the user no choice of options. A more natural way of translating the Tarski definition into game terms is to use nondeterministic strategies. (However, Hintikka 1996 insists that the correct explication of ‘true’ is the one using deterministic strategies, and that this fact vindicates the axiom of choice.)

Computer implementations of these games of Hintikka proved to be a very effective way of teaching the meanings of first-order sentences. One such package was designed by Jon Barwise and John Etchemendy at Stanford, called ‘Tarski's World’. Independently another team at the University of Omsk constructed a Russian version for use at schools for gifted children.

In the published version of his John Locke lectures at Oxford,
Hintikka in 1973 raised the Dawkins question (see above) for these
games. His answer was that one should look to Wittgenstein's language
games, and the language games for understanding quantifiers are those
which revolve around seeking and finding. In the corresponding logical
games one should think of ∃ as Myself and ∀ as a hostile
Nature who can never be relied on to present the object I want; so to
be sure of finding it, I need a winning strategy. This story was never
very convincing; the motivation of Nature is irrelevant, and nothing in
the logical game corresponds to seeking. In retrospect it is a little
disappointing that nobody took the trouble to look for a better story.
It may be more helpful to think of a winning strategy for ∃ in
*G*(φ) as a kind of proof (in a suitable infinitary system)
that φ is true.

Later Jaakko Hintikka extended the ideas of this section in two
directions, namely to natural language semantics and to games of
imperfect information (see the next section). The name *Game-Theoretic Semantics*, GTS
for short, has come to be used to cover both of these extensions.

The games described in this section adapt almost trivially to
many-sorted logic: for example the quantifier ∀*x*, where
*x* is a variable of sort σ, is an instruction for player
∀ to choose an element of sort σ. This immediately gives
us the corresponding games for second-order logic, if we think of the
elements of a structure as one sort, the sets of elements as a second
sort, the binary relations as a third and so on. It follows that we
have, quite routinely, game rules for most generalised quantifiers too;
we can find them by first translating the generalised quantifiers into
second-order logic.

## 4. More Semantic Games

Structures of the following kind give rise to interesting games. The
structure *A* consists of a set *S* of elements (which we
shall call *states*, adding that they are often called
*worlds*), a binary relation *R* on *S* (we shall
read *R* as *arrow*), and a family
*P*_{1},…, *P _{n}* of subsets of

*S*. The two players ∀ and ∃ play a game G on

*A*, starting at a state

*s*which is given them, by reading a suitable logical formula φ as a set of instructions for playing and for winning.

Thus if φ is *P _{i}*, then player ∃ wins at
once if

*s*is in

*P*, and otherwise player ∀ wins at once. The formulas ψ∧θ, ψ∨θ and ¬ψ behave as in Hintikka's games above; for example ψ∧θ instructs player ∀ to choose whether the game shall continue as for ψ or for θ. If the formula φ is □ψ, then player ∀ chooses an arrow from

_{i}*s*to a state

*t*(i.e. a state

*t*such that the pair (

*s*,

*t*) is in the relation

*R*), and the game then proceeds from the state

*t*according to the instructions ψ. The rule for ◊ψ is the same except that player ∃ makes the choice. Finally we say that the formula φ is

*true at s in A*if player ∃ has a winning strategy for this game based on φ and starting at

*s*.

These games stand to modal logic in very much the same way as Hintikka's games stand to first-order logic. In particular they are one way of giving a semantics for modal logic, and they agree with the usual Kripke-type semantics. Of course there are many types and generalisations of modal logic (including closely related logics such as temporal, epistemic and dynamic logics), and so the corresponding games come in many different forms. One example of interest is the computer-theoretic logic of Matthew Hennessy and Robin Milner, used for describing the behaviour of systems; here the arrows come in more than one colour, and moving along an arrow of a particular colour represents performing a particular ‘action’ to change the state. Another example is the more powerful modal μ-calculus of Dexter Kozen, which has fixed point operators; see Chapter 5 of Stirling (2001).

In the related ‘logic of games’,
proposed by Rohit
Parikh, games that move us between the states are the subject matter
rather than a way of giving a truth definition. These games have many
interesting aspects. In 2003 the journal *Studia Logica* ran an issue
devoted to them, edited by Marc Pauly and Parikh.

A different kind of adjustment of semantic games is to drop the
assumption that each player knows the previous history of the play.
For example we can require a player to make a choice without knowing
what choices the other player has made at certain earlier moves. The classical
way to handle this within game theory is to make restrictions on the
strategies of the players. For example we can require that the
strategy function telling ∃ what to do at a
particular step is a function whose domain is the family of possible
choices of ∀ at just his first and second moves;
this is a way of expressing that ∃ doesn't
know how ∀ chose at his third and later moves.
Games with restrictions of this kind on the strategy functions are
said to be of *imperfect information*, as opposed to the
games of *perfect information* in the previous section.

The classic example of a logic with a semantic game of imperfect information is the Independence-Friendly (IF) logic of Hintikka and Gabriel Sandu. This logic is the same as first-order logic with Hintikka's game-theoretic semantics, except that a notation is added to some quantifiers (and possibly also some connectives), to show that the Skolem functions for these quantifiers (or connectives) are independent of certain variables. For example the sentence

(∀x)(∃y/ ∀x)R(x,y)

is read as: 'For every *x* there is *y*, not depending
on *x*, such that *R*(*x*, *y*)'.

There are three important comments to make on the distinction between perfect
and imperfect information. The first is that the Gale-Stewart theorem holds only for
games of perfect information. Suppose for example that ∀
and ∃ play the following game. First, ∀
chooses one of the numbers 0 and 1. Then ∃ chooses one of these two numbers. Player ∃ wins if the two numbers chosen are the same, and otherwise player ∀ wins. We require that ∃, when she makes her choice, doesn't know what ∀ chose; so a Skolem function for her will be a constant. (This game corresponds to the IF sentence above with *R* read as equality,
in a structure with a domain consisting of 0 and 1.) It's clear that player ∃ doesn't have a constant winning strategy, and also that player ∀ doesn't have a winning strategy at all. So this game is undetermined, although its length is only 2.

One corollary is that Hintikka's justification for reading negation as dualising ('players swap places'), in his games for first-order logic, doesn't carry over to IF logic. Hintikka's response has been that dualising was the correct intuitive meaning of negation even in the first-order case, so no justification is needed.

The second comment is that already in games of perfect information, it can happen
that winning strategies don't use all the available information. For example in a
game of perfect information, if player ∃ has a winning strategy, then she also has a winning strategy where the strategy functions depend only on the previous choices of ∀. (This is because she can reconstruct her
own previous moves using her earlier strategy functions.) A more specialised example is the modal logic games above: a player due to move at a state *s* never needs to
know how he or she came to be at that state, so the previous history of the game is
irrelevant. As the computer scientists say, these games are 'memoryless'.

When Hintikka used Skolem functions as strategies in his games for first-order
logic, he made the strategies for a player depend only on the previous moves of
the other player. (A Skolem function for ∃ depends only on
universally quantified variables.) Because the games were games of perfect information,
there was no loss in this, by the second comment above. But when he moved to IF logic,
the requirement that strategies depend only on moves of the other player really did make a difference. Hodges showed this by revising the notation, so that for example (∃*y*/*x*) means: 'There is *y* independent of *x*, regardless of which player chose *x*'.

Consider now the sentence

(∀x)(∃z)(∃y/x)(x=y),

played again on a structure with two elements 0 and 1. Player ∃ can win as follows. For *z* she chooses the same as player ∀ chose for *x*; then for *y* she chooses the same as she chose for *z*. This winning strategy works only because in this game ∃ can refer back to her own previous choices. She would have no winning strategy if the third quantifier was (∃*y*/*xz*), again because any Skolem function for this quantifier would have to be constant. The way that ∃ passes information to herself by referring to her previous choice is an example of the phenomenon of *signalling*. John von Neumann and Oskar Morgenstern illustrated it with the example of Bridge, where a single player consists of two partners who have to share information by using their public moves to signal to each other.

The third comment is that there is a dislocation between the intuitive idea of imperfect information and the game-theoretic definition of it in terms of strategies. Intuitively, imperfect information is a fact about the circumstances in which the game is played, not about the strategies. This is a very tricky matter, and it continues to lead to misunderstandings about IF and similar logics. Take for example the sentence

(∃x)(∃y/x)(x=y),

again played on a structure with elements 0 and 1. Intuitively one might think that if ∃ isn't allowed to remember at the second quantifier what she chose at the first, then she can hardly have a winning strategy. But in fact she has a very easy one: 'Always choose 0'!

Influences from economics and computer science have led a number of logicians to use logic for analysing decision making under conditions of partial ignorance. (See for example the article on Epistemic Logic.) There are several ways to represent states of knowledge. One is to take them as states or worlds in the kind of modal structure that we mentioned at the beginning of this section. Another is to use IF logic or a variant of it. How are these approaches related? Johan van Benthem 2006 presents some thoughts and results on this very natural question.

## 5. Back-and-Forth Games

In 1930 Alfred Tarski formulated the notion of two structures
*A* and *B* being *elementarily equivalent*, i.e.
that exactly the same first-order sentences are true in *A* as
are true in *B*. At a conference in Princeton in 1946 he
described this notion and expressed the hope that it would be possible
to develop a theory of it that would be ‘as deep as the notions
of isomorphism, etc. now in use’ (Hourya Sinaceur ed., “Address
at the Princeton University Bicentennial Conference on Problems of
Mathematics (December 17-19, 1946), by Alfred Tarski”, *Bulletin of
Symbolic Logic* **6** (2000): 1-44).

One natural part of such a theory would be a purely structural
necessary and sufficient condition for two structures to be
elementarily equivalent. Roland Fraïssé, a French-Algerian,
was the first to find a usable necessary and sufficient condition. It
was rediscovered a few years later by the Kazakh logician A. D.
Taimanov, and it was reformulated in terms of games by the Polish
logician Andrzej Ehrenfeucht. The games are now known as
*Ehrenfeucht-Fraïssé* games, or sometimes as
*back-and-forth* games. They have turned out to be one of the
most versatile ideas in twentieth-century logic. They adapt fruitfully
to a wide range of logics and structures.

In a back-and-forth game there are two structures *A* and
*B*, and two players who are commonly called Spoiler and
Duplicator. (The names are due to Joel Spencer in the early 1990s. More
recently Neil Immerman suggested Samson and Delilah, using the same
initials; this places Spoiler as the male player ∀ and
Duplicator as the female ∃.) Each step in the game consists of a
move of Spoiler, followed by a move of Duplicator. Spoiler chooses an
element of one of the two structures, and Duplicator must then choose
an element of the other structure. So after *n* steps, two
sequences have been chosen, one from *A* and one from
*B*:

(a_{0},…,a_{n-1};b_{ 0},…,b_{n-1}).

This position is a win for Spoiler if and only if some atomic
formula (of one of the forms
‘R(*v*_{0},…, *v*_{k-1})’
or
‘F(*v*_{0},…, *v*_{k-1})
= *v*_{k}’ or
‘*v*_{0}=*v*_{1}’, or one of these
with different variables) is satisfied by
(*a*_{0},…, *a*_{n-1}) in
*A* but not by
(*b*_{0},…, *b*_{n-1}) in
*B*, or vice versa. The condition for Duplicator to win is
different in different forms of the game. In the simplest form,
EF(*A*, *B*), a play is a win for Duplicator if and only
if no initial part of it is a win for Spoiler (i.e. she wins if she
hasn't lost by any finite stage). For each natural number *m*
there is a game EF_{m}(*A*, *B*); in this
game Duplicator wins after *m* steps provided she has not yet
lost. All these games are determined, by the Gale-Stewart Theorem. The
two structures *A* and *B* are said to be
*back-and-forth equivalent* if Duplicator has a winning strategy
for EF(*A*, *B*), and *m-equivalent* if she has a
winning strategy for
EF_{m}(*A*, *B*).

One can prove that if *A* and *B* are
*m*-equivalent for every natural number *m*, then they
are elementarily equivalent. On the other hand a winning strategy for
Spoiler in EF_{m}(*A*, *B*) can be
converted into a first-order sentence that is true in exactly one of
*A* and *B*, and in which the nesting of quantifier
scopes has at most *m* levels. So we have our necessary and
sufficient condition for elementary equivalence, and a bit more
besides.

If *A* and *B* are back-and-forth equivalent, then
certainly they are elementarily equivalent; but in fact back-and-forth
equivalence turns out to be the same as elementary equivalence in an
infinitary logic which is much more expressive than first-order logic.
There are many adjustments of the game that give other kinds of
equivalence. For example Barwise, Immerman and Bruno Poizat
independently described a game in which the two players have exactly
*p* numbered pebbles each; each player has to label his or her
choices with a pebble, and the two choices in the same step must be
labelled with pebbles carrying the same number. As the game proceeds,
the players will run out of pebbles and so they will have to re-use
pebbles that were already used. The condition for Spoiler to win at a
position (and all subsequent positions) is the same as before, except
that only the elements carrying labels at that position count. The
existence of a winning strategy for Duplicator in this game means that
the two structures agree for sentences which use at most *p*
variables (allowing these variables to occur any number of times).

The theory behind back-and-forth games uses very few assumptions
about the logic in question. As a result, these games are one of the
few model-theoretic techniques that apply as well to finite structures
as they do to infinite ones, and this makes them one of the
cornerstones of theoretical computer science. One can use them to
measure the expressive strength of formal languages, for example
database query languages. A typical result might say, for example, that
a certain language can't distinguish between ‘even’ and
‘odd’; we would prove this by finding, for each level
*n* of complexity of formulas of the language, a pair of finite
structures for which Duplicator has a winning strategy in the
back-and-forth game of level *n*, but one of the structures has
an even number of elements and the other has an odd number.
Semanticists of natural languages have found back-and-forth games
useful for comparing the expressive powers of quantifiers. (See for
example Peters and Westerståhl 2006 Section IV.)

There is also a kind of back-and-forth game that corresponds to our
modal semantics above in the same way as
Ehrenfeucht-Fraïssé games correspond to Hintikka's game
semantics for first-order logic. The players start with a state
*s* in the structure *A* and a state *t* in the
structure *B*. Spoiler and Duplicator move alternately, as
before. Each time he moves, Spoiler chooses whether to move in
*A* or in *B*, and then Duplicator must move in the other
structure. A move is always made by going forwards along an arrow from
the current state. If between them the two players have just moved to a
state *s*’ in *A* and a state *t*’ in *B*,
and some predicate *P _{i}* holds at just one of

*s*’ and

*t*’, then Duplicator loses at once. Also she loses if there are no available arrows for her to move along; but if Spoiler finds there are no available arrows for him to move along in either structure, then Duplicator wins. If the two players play this game with given starting states

*s*in

*A*and

*t*in

*B*, and both structures have just finitely many states, then one can show that Duplicator has a winning strategy if and only if the same modal sentences are true at

*s*in

*A*as are true at

*t*in

*B*.

There are many generalisations of this result, some of them
involving the following notion. Let *Z* be a binary relation
which relates states of *A* to states of *B*. Then we
call *Z* a *bisimulation* between *A* and
*B* if Duplicator can use *Z* as a nondeterministic
winning strategy in the back-and-forth game between *A* and
*B* where the first pair of moves of the two players is to
choose their starting states. In computer science the notion of a
bisimulation is crucial for the understanding of *A* and
*B* as systems; it expresses that the two systems interact with
their environment in the same way as each other, step for step. But a
little before the computer scientists introduced the notion,
essentially the same concept appeared in Johan van Benthem's PhD thesis
on the semantics of modal logic (1976).

## 6. Games of dialogue, communication and proof

Several medieval texts describe a form of debate called
*obligationes*. There were two disputants, Opponens and
Respondens. At the beginning of a session, the disputants would agree
on a ‘positum’, typically a false statement. The job of
Respondens was to give rational answers to questions from Opponens,
assuming the truth of the positum; above all he had to avoid
contradicting himself unnecessarily. The job of Opponens was to try to
force Respondens into contradictions. So we broadly know the answer to
the Dawkins question, but we don't know the game rules! The medieval textbooks
do describe several rules that the disputants should follow. But these
rules are not stipulated rules of the game; they are guidelines which
the textbooks derive from principles of sound reasoning with the aid of
examples. (Paul of Venice justifies one rule by the practice of
‘great logicians, philosophers, geometers and
theologians’.) In particular it was open to a teacher of
obligationes to discover new rules. This open-endedness implies that
obligationes are not logical games in our sense.

Not everybody agrees with the previous sentence. For example Catarina Dutilh Novaes 2005 makes a detailed defence of the view that obligationes present 'a remarkable case of conceptual similarity between a medieval and a modern theoretical framework' (her page 5). But whatever view we take on this question, these debates have inspired one important line of modern research in logical games.

Imagine ∃ taking an oral examination in proof theory. The examiner gives her a sentence and invites her to start proving it. If the sentence has the form

φ ∨ ψ

then she is entitled to choose one of the sentences and say ‘OK, I'll prove this one’. (In fact if the examiner is an intuitionist, he may insist that she choose one of the sentences to prove.) On the other hand if the sentence is

φ ∧ ψ

then the examiner, being an examiner, might well choose one of the conjuncts himself and invite her to prove that one. If she knows how to prove the conjunction then she certainly knows how to prove the conjunct.

The case of φ → ψ is a little subtler. She will probably want to start by assuming φ in order to deduce ψ; but there is some risk of confusion because the sentences that she has written down so far are all of them things to be proved, and φ is not a thing to be proved. The examiner can help her by saying ‘I'll assume φ, and let's see if you can get to ψ from there’. At this point there is a chance that she sees a way of getting to ψ by deducing a contradiction from φ; so she may turn the tables on the examiner and invite him to show that his assumption is consistent, with a view to proving that it isn't. The symmetry is not perfect: he was asking her to show that a sentence is true everywhere, while she is inviting him to show that a sentence is true somewhere. Nevertheless we can see a sort of duality.

Ideas of this kind lie behind the dialectical games of Paul Lorenzen. He showed that with a certain amount of pushing and shoving, one can write rules for the game which have the property that ∃ has a winning strategy if and only if the sentence that she is presented with at the beginning is a theorem of intuitionistic logic. In a gesture towards medieval debates, he called ∃ the Proponent and the other player the Opponent. Almost as in the medieval obligationes, the Opponent wins by driving the Proponent to a point where the only moves available to her are blatant self-contradictions.

Lorenzen claimed that the rules of his games could be justified on a pre-logical basis, and so they formed a foundation for logic. Unfortunately any ‘justification’ involves a convincing answer to the Dawkins question, and this Lorenzen never provided. For example he spoke of moves as ‘attacks’, even when (like the examiner's choice at φ ∧ ψ above) they look more like help than hostility. To repair Lorenzen's omission, one certainly needs to distinguish between different stances that a person might take in an argument: stating, assuming, conceding, querying, attacking, committing oneself. Whether it is really possible to define all these notions in a pre-logical way is a moot point. But perhaps this is unimportant. A more positive view is that this kind of refinement serves to link Lorenzen's dialogues to informal logic, and especially to the research that aims to systematise the possible structures of sound informal argument.

In any case, Lorenzen's games stand as an important paradigm of what
recent proof theorists have called *semantics of proofs*. A
semantics of proofs gives a ‘meaning’ not just to the
notion of being provable, but to each separate step in a proof. It
answers the question ‘What do we achieve by making this
particular move in the proof?’ During the 1990s a number of
workers at the logical end of computer science looked for games that
would stand to linear logic and some other proof systems in the same
way as Lorenzen's games stood to intuitionist logic. Andreas Blass, and
then later Samson Abramsky and colleagues, gave games that corresponded
to parts of linear logic, but at the time of writing we don't yet have
a perfect correspondence between game and logic. This example is
particularly interesting because the answer to the Dawkins question
should give an intuitive interpretation of the laws of linear logic, a
thing that this logic has badly needed. The games of Abramsky et al.
tell a story about two interacting systems. But while he began with
games in which the players politely take turns, Abramsky's more recent
work allows the players to act ‘in a distributed, asynchronous
fashion’, taking notice of each other only when they choose to.
These games are no longer in the normal format of logical games, and
their real-life interpretation raises a host of new questions.

Giorgi Japaridze has proposed a ‘computability logic’ for studying computation. Its syntax is first-order logic with some extra items reminiscent of linear logic. Its semantics is in terms of semantic games with some unusual features. For example it is not always determined which player makes the next move. The notion of strategy functions is no longer adequate for describing the players; instead Japaridze describes ways of reading the second player (player ∃ in our notation) as a kind of computing machine. Further information is on his website.

Another group of games of the same general family as Lorenzen's are the proof games of Pavel Pudlak 2000. Here the Opponent (called Prover) is in the role of an attorney in a court of law, who knows that the Proponent (called Adversary) is guilty of some offence. Proponent will insist he is innocent, and is prepared to tell lies to defend himself. Opponent's aim is to force Proponent to contradict something that Proponent is on record as having said earlier; but Opponent keeps the record and (as in the pebble games above) he sometimes has to drop items from the record for lack of space or memory. The important question is not whether Opponent has a winning strategy (it's assumed from the outset that he has one), but how much memory he needs for his record. These games are a useful device for showing upper and lower bounds on the lengths of proofs in various proof systems.

Another kind of logical game that allows lies is Ulam's Game with Lies. Here one player thinks of a number in some given range. The second player's aim is to find out what that number is, by asking the first player yes/no questions; but the first player is allowed to tell some fixed number of lies in his answers. As in Pudlak's games, there is certainly a winning strategy for the second player, but the question is how hard this player has to work in order to win. The measure this time is not space or memory but time: how many questions does he have to ask? Cignoli et al. 2000 Chapter 5 relate this game to many-valued logic.

## 7. Other Model-theoretic Games

The logical games in this section are mathematicians' tools, but they have some conceptually interesting features.

### Forcing games

Forcing games are also known to descriptive set theorists as
*Banach-Mazur games*; see the references by Kechris or Oxtoby
below for more details of the mathematical background. Model theorists
use them as a way of building infinite structures with controlled
properties. To sketch the idea, imagine that a countably infinite team
of builders are building a house *A*. Each builder has his or
her own task to carry out: for example to install a bath or to
wallpaper the entrance hall. Each builder has infinitely many chances
to enter the site and add some finite amount of material to the house;
these slots for the builders are interleaved so that the whole process
takes place in a sequence of steps counted by the natural numbers.

To show that the house can be built to order, we need to show that each builder separately can carry out his or her appointed task, regardless of what the other builders do. So we imagine each builder as player ∃ in a game where all the other players are lumped together as ∀, and we aim to prove that ∃ has a winning strategy for this game. When we have proved this for each builder separately, we can imagine them going to work, each with their own winning strategy. They all win their respective games and the result is one beautiful house.

More technically, the elements of the structure *A* are fixed
in advance, say as *a*_{0}, *a*_{1},
*a*_{2} etc., but the properties of these elements have
to be settled by the play. Each player moves by throwing in a set of
atomic or negated atomic statements about the elements, subject only to
the condition that the set consisting of all the statements thrown in
so far must be consistent with a fixed set of axioms written down
before the game. (So throwing in a negated atomic sentence ¬φ
has the effect of preventing any player from adding φ at a later
stage.) At the end of the joint play, the set of atomic sentences
thrown in has a canonical model, and this is the structure *A*;
there are ways of ensuring that it is a model of the fixed set of
axioms. A possible property P of *A* is said to be
*enforceable* if a builder who is given the task of making P
true of *A* has a winning strategy. A central point (due
essentially to Ehrenfeucht) is that the conjunction of a countably
infinite set of enforceable properties is again enforceable.

The name ‘forcing’ comes from an application of related ideas by Paul Cohen to construct models of set theory in the early 1960s. Abraham Robinson adapted it to make a general method for building countable structures, and Martin Ziegler introduced the game setting. More recently Robin Hirsch and Ian Hodkinson have used related games to settle some old questions about relation algebras.

Forcing games are a healthy example to bear in mind when thinking about the Dawkins question. They remind us that in logical games it need not be helpful to think of the players as opposing each other.

### Cut-and-choose games

In the traditional cut-and-choose game you take a piece of cake and cut it into two smaller pieces; then I choose one of the pieces and eat it, leaving the other one for you. This procedure is supposed to put pressure on you to cut the cake fairly. Mathematicians, not quite understanding the purpose of the exercise, insist on iterating it. Thus I make you cut the piece I chose into two, then I choose one of those two; then you cut this piece again, and so on indefinitely. Some even more unworldly mathematicians make you cut the cake into countably many pieces instead of two.

These games are important in the theory of definitions. Suppose we
have a collection *A* of objects and a family *S* of
properties; each property cuts *A* into the set of those objects
that have the property and the set of those that don't. Let ∃
cut, starting with the whole set *A* and using a property in
*S* as a knife; let ∀ choose one of the pieces (which are
subsets of *A*) and give it back to ∃ to cut again, once
more using a property in *S*; and so on. Let ∃ lose as
soon as ∀ chooses an empty piece. We say that
(*A*, *S*) has *rank* at most *m* if
∀ has a strategy which ensures that ∃ will lose before her
*m*-th move. The rank of (*A*, *S*) gives valuable
information about the family of subsets of *A* definable by
properties in *S*.

Variations of this game, allowing a piece to be cut into infinitely
many smaller pieces, are fundamental in the branch of model theory
called *stability theory*. Broadly speaking, a theory is
‘good’ in the sense of stability theory if, whenever we
take a model *A* of the theory and *S* the set of
first-order formulas in one free variable with parameters from
*A*, the structure (*A*, *S*) has
‘small’ rank. A different variation is to require that at
each step, ∃ divides into two each of the pieces that have
survived from earlier steps, and again she loses as soon as one of the
cut fragments is empty. (In this version ∀ is redundant.) With
this variation, the rank of (*A*,S) is called its
*Vapnik-Chervonenkis dimension*; this notion is used in
computational learning theory.

### Games on the tree of two successor functions

Imagine a tree that has been built up in levels. At the bottom level
there is a single root node, but a left branch and a right branch come
up from it. At the next level up there are two nodes, one on each
branch, and from each of these nodes a left branch and a right branch
grow up. So on the next level up there are four nodes, and again the
tree branches into left and right at each of these nodes. Continued to
infinity, this tree is called the *tree of two successor
functions* (namely left successor and right successor). Taking the
nodes as elements and introducing two function symbols for left and
right successor, we have a structure. A powerful theorem of Michael
Rabin states that there is an algorithm which will tell us, for every
monadic second-order sentence φ in the language appropriate for
this structure, whether or not φ is true in the structure.
(’Monadic second-order’ means that the logic is like
first-order, except that we can also quantify over sets of
elements—but not over binary relations on elements, for
example.)

Rabin's theorem has any number of useful consequences. For example Dov Gabbay used it to prove the decidability of some modal logics. But Rabin's proof, using automata, was notoriously difficult to follow. Yuri Gurevich and Leo Harrington, and independently Andrei Muchnik, found much simpler proofs in which the automaton is a player in a game.

This result of Rabin is one of several influential resuls that connect
games with automata. Another example is the *parity games* which
are used for verifying properties of modal systems. See for example
Stirling (2001) Chapter 6; Bradfield and Stirling (2006) discuss parity
games for the modal μ-calculus.

## Bibliography

### Games in the History of Logic

- Lewis Carroll,
*The Game of Logic*, Macmillan, London 1887. - Charles Hamblin,
*Fallacies*, Methuen, London (1970). - David Hilbert, “Die Grundlagen der Mathematik” 1927,
translated as “The foundations of mathematics” in Jean van
Heijenoort ed.,
*From Frege to Gödel*, Harvard University Press, Cambridge Mass. 1967, pp. 464-479. *Infinitistic Methods*(editors unnamed), Pergamon Press, Oxford 1961. (*Seminal papers of Henkin and Lorenzen appear in this book.*)- Agostino Nifo,
*Dialectica Ludicra (Logic as a game)*, Bindonis, Florence 1521. - Hermann Weyl, “Die heutige Erkenntnislage in der Mathematik”,
1925-7, translated as “The current epistemological situation in
mathematics” in Paolo Mancosu,
*From Brouwer to Hilbert: The Debate on the Foundations of Mathematics in the 1920s*, Oxford University Press, New York 1998, pp. 123-142. - Ernst Zermelo, “Uber eine Anwendung der Mengenlehre auf die Theorie
des Schachspiels”, in E. W. Hobson and A. E. H. Love (eds.),
*Proceedings of the Fifth International Congress of Mathematicians*, Volume II, Cambridge University Press, Cambridge 1913.

### Logical Games

- David Gale and F. M. Stewart, “Infinite games with perfect
information”, in
*Contributions to the Theory of Games II*, ed. H. W. Kuhn and A. W. Tucker, Annals of Mathematics Studies 28, Princeton University Press, Princeton NJ (1953): 245-266. - Alexander S. Kechris,
*Classical Descriptive Set Theory*, Springer, New York 1995. - Martin J. Osbourne and Ariel Rubinstein,
*A Course in Game Theory*, MIT Press, Cambridge Mass. 1994.

### Semantic Games

- Jon Barwise and John Etchemendy,
*The Language of First-Order Logic, including Tarski's World 3.0*, Cambridge University Press, Cambridge 1995. - Leon Henkin, “Some remarks on infinitely long formulas”, in
*Infinitistic Methods*(above, 1961): 167-183. - Jaakko Hintikka,
*Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic*, Clarendon Press, Oxford 1973. - Jaakko Hintikka,
*The Principles of Mathematics Revisited*, Cambridge University Press, New York 1996. (*See for example pages 40, 82 on the axiom of choice.*) - Wilfrid Hodges, “Elementary Predicate Logic 25: Skolem Functions”,
in
*Handbook of Philosophical Logic I*, 2nd edition, ed. Dov Gabbay and Franz Guenthner, Kluwer, Dordrecht (2001): 86-91 (*Proof of equivalence of game and Tarski semantics*). - Ph. G. Kolaitis, “Game quantification”, in J. Barwise and S. Feferman
(eds),
*Model-Theoretic Logics*, Springer, New York 1985, pp. 365-421. - Charles Sanders Peirce,
*Reasoning and the Logic of Things: The Cambridge Conferences Lectures of 1898*, ed. Kenneth Laine Ketner, Harvard University Press, Cambridge Mass. 1992.

### More Semantic Games

- Julian Bradfield and Colin Stirling, “Modal mu-calculi”, in P. Blackburn et al.
(eds),
*Handbook of Modal Logic*, Elsevier, Amsterdam 2006: 721-756. - Paul Dekker and Marc Pauly (eds),
*Journal of Logic, Language and Information***11**(3) (2002): 287-387 (*special issue on Logic and Games*). - Matthew Hennessy and Robin Milner, “Algebraic laws for indeterminism
and concurrency”,
*Journal of the ACM***32**(1985): 137-162. - Jaakko Hintikka and Gabriel Sandu, “Game-theoretical semantics”, in
*Handbook of Logic and Language*, ed. Johan van Benthem and Alice ter Meulen, Elsevier, Amsterdam (1997): 361-410. - Wilfrid Hodges, “Compositional semantics for a language of
imperfect information”,
*Logic Journal of the IGPL***5**(1997): 539-563. - Theo M. V. Janssen and Francien Dechesne, “Signalling: a
tricky business”, in J. van Benthem et al. (eds),
*The Age of Alternative Logics: Assessing the Philosophy of Logic and Mathematics Today*, Kluwer, Dordrecht 2006: 223-242. - Rohit Parikh, “The logic of games and its applications”, in “Topics
in the Theory of Computation”, ed. Marek Karpinski and Jan van Leeuwen,
*Annals of Discrete Mathematics***24**(1985): 111-140. - Marc Pauly and Rohit Parikh (eds),
*Studia Logica***72**(2) (2003): 163-256 (*special issue on Game Logic*). - Colin Stirling,
*Modal and Temporal Properties of Processes*, Springer, New York 2001. - Johan van Benthem, “The epistemic logic of IF games”, in Randall E.
Auxier and Lewis Edwin Hahn (eds),
*The Philosophy of Jaakko Hintikka*, Open Court, Chicago 2006: 481-513. - John von Neumann and Oskar Morgenstern,
*Theory of Games and Economic Behavior*, Princeton University Press, Princeton 1944.

### Back-and-Forth Games

- Johan van Benthem, “Correspondence Theory”, in
*Handbook of Philosophical Logic III*, 2nd edition, ed. Dov Gabbay and Franz Guenthner, Kluwer, Dordrecht (2001). - Patrick Blackburn, Maarten de Rijke and Yde Venema,
*Modal Logic*, Cambridge University Press, Cambridge (2001). - Kees Doets,
*Basic Model Theory*, CSLI Publications and FoLLI, Stanford 1996. - Heinz-Dieter Ebbinghaus and Jörg Flum,
*Finite Model Theory*, Springer, New York, Second edition 1999. - Andrzej Ehrenfeucht, “An application of games to the completeness
problem for formalized theories”,
*Fundamenta Mathematicae***49**(1961): 129-141. - Leonid Libkin,
*Elements of Finite Model Theory*, Springer, Berlin 2004. - Martin Otto,
*Bounded Variable Logics and Counting—A Study in Finite Models*, Lecture Notes in Logic**9**, Springer-Verlag 1997. - Stanley Peters and Dag Westerståhl,
*Quantifiers in Language and Logic*, Clarendon Press, Oxford 2006.

### Games of Dialogue, Communication and Proof

- Samson Abramsky and Radha Jagadeesan, “Games and full completeness
for multiplicative linear logic”,
*Journal of Symbolic Logic***59**(1994): 543-574. - Samson Abramsky and Paul-André Melliès, “Concurrent
games and full completeness”, in
*Proceedings of the Fourteenth International Symposium on Logic in Computer Science*, Computer Science Press of the IEEE (1999): 431-442. - Andreas Blass, “A game semantics for linear logic”,
*Annals of Pure and Applied Logic***56**(1992): 183-220. - Roberto L. O. Cignoli, Itala M. L. D'Ottaviano and Daniele Mundici,
*Algebraic Foundations of Many-Valued Reasoning*, Kluwer, Dordrecht 2000. - Catarina Dutilh Novaes,
*Formalizations apres la lettre: Studies in Medieval Logic and Semantics*, Doctoral Dissertation, University of Leiden 2005. - Walter Felscher, “Dialogues as a foundation for intuitionistic
logic”, in
*Handbook of Philosophical Logic V*, 2nd edition, ed. Dov Gabbay and Franz Guenthner, Kluwer, Dordrecht (2001). - Wilfrid Hodges and Erik C. W. Krabbe, “Dialogue foundations”,
*Proceedings of the Aristotelian Society, Supplementary Volume***75**(2001): 17-49. - Giorgi Japaridze, “Introduction to computability logic”,
*Annals of Pure and Applied Logic***123**(2003): 1-99. - Paul Lorenzen, “Ein dialogisches Konstruktivitätskriterium”,
in
*Infinitistic Methods*(above, 1961): 193-200. - Paul of Venice,
*Logica Magna II (8), Tractatus de Obligationibus*, ed. E. Jennifer Ashworth, British Academy and Oxford University Press, New York (1988). - Pavel Pudlak, “Proofs as games”,
*American Mathematical Monthly*,**107**(6) (2000): 541-550. - Douglas N. Walton and Erik C. W. Krabbe,
*Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning*, State University of New York Press, Albany 1995.

### Other Model-Theoretic Games

- Martin Anthony and Norman Biggs,
*Computational Learning Theory*, Cambridge University Press, Cambridge (1992) (*for Vapnik-Chervonenkis dimension*). - Yuri Gurevich and Leo Harrington, “Trees, automata, and games”, in
*Proceedings of the ACM Symposium on the Theory of Computing*, ed. H. R. Lewis, ACM, San Francisco (1984): 171-182. - Robin Hirsch and Ian Hodkinson,
*Relation Algebras by Games*, North-Holland, New York (2002). - Wilfrid Hodges,
*Building Models by Games*, Cambridge University Press, Cambridge (1985). - Wilfrid Hodges,
*Model Theory*, Cambridge University Press, Cambridge (1993). - J. C. Oxtoby,
*Measure and Category*, Springer-Verlag, New York (1971). - Martin Ziegler, “Algebraisch abgeschlossene Gruppen”, in
*Word Problems II, The Oxford Book*, ed. S. I. Adian et al., North-Holland, Amsterdam (1980): 449-576.

## Other Internet Resources

## Related Entries

game theory | generalized quantifiers | logic: classical | logic: epistemic | logic: infinitary | logic: informal | logic: intuitionistic | logic: modal | model theory | set theory