. 90
( 107 .)


496 / Advanced Topics in FOL

Figure 18.1: Mary Ellen™s World.

represents circumstances that determine the truth values of all of the sentences
of a language, but it does so in such a way that identity and the ¬rst-order
quanti¬ers ∀ and ∃ are respected. This will allow us to give a precise de¬nition
of ¬rst-order consequence and ¬rst-order validity.
In our intuitive explanation of the semantics of quanti¬ed sentences, we
appealed to the notion of a “domain of discourse,” de¬ning truth and sat-
isfaction relative to such a domain. We took this notion to be an intuitive
one, familiar both from our experience using Tarski™s World and from our
ordinary experience communicating with others about real-world situations.
The notion of a ¬rst-order structure results from modeling these domains in
a natural way using set theory.
Let™s begin with a very simple language, a sublanguage of the blocks lan-
guage. Assume that we have only three predicates, Cube, Larger, and =, and
one name, say c. Even with this simple language there are in¬nitely many
sentences. How should we represent, in a rigorous way, the circumstances that
determine the truth values of sentences in this language?
By way of example, consider Mary Ellen™s World, shown in Figure 18.1.
modeling a world
This world has three cubes, one of each size, and one small tetrahedron named
c. Our goal is to construct a mathematical object that represents everything
about this world that is relevant to the truth values of sentences in our toy
language. Later, we will generalize this to arbitrary ¬rst-order languages.
Since sentences are going to be evaluated in Mary Ellen™s World, one thing
we obviously need to represent is that the world contains four objects. We do
this by using a set D = {b1 , b2, b3 , b4 } of four objects, where b1 represents
domain of discourse
the leftmost block, b2 the next, and so forth. Thus b4 represents the sole
tetrahedron. This set D is said to be the domain of discourse of our ¬rst-
order structure.
To keep ¬rst-order structures as clean as possible, we represent only those
features of the domain of discourse that are relevant to the truth of sentences
in the given ¬rst-order language. Given our current sublanguage, there are

Chapter 18
First-order structures / 497

many features of Mary Ellen™s World that are totally irrelevant to the truth
of sentences. For example, since we cannot say anything about position, our
mathematical structure need not represent any facts about the positions of our
blocks. On the other hand, we can say things about size and shape. Namely,
we can say that an object is (or is not) a cube and that one object is (or is
not) larger than another. So we will need to represent these sorts of facts. We
do this by assigning to the predicate Cube a certain subset Cu of the domain
of discourse D, namely, the set of cubes. This set is called the extension of extensions of predicates
the predicate Cube in our structure. In modeling the world depicted above,
this extension is the set Cu = {b1 , b2 , b3}. Similarly, to represent facts about
the relative sizes of the objects, we assign to the predicate Larger a set La of
ordered pairs x, y , where x, y ∈ D. If x, y ∈ La, then this represents the
fact that x is larger than y. So in our example, we would have

La = { b2 , b1 , b3 , b1 , b3 , b2 , b2 , b4 , b3 , b4 }

La is said to be the extension of Larger in the structure.
There is only one more thing we need to make our representation complete,
at least as far as the present language is concerned. We have to hook up the
individual constant c with the block it names. That is, we need to build into
our structure something that tells us that c is a name of block b1 rather than
one of the other blocks. Or, to put it more technically, we need to represent the
fact that in our world b1 is the referent of the name c. So we need to pair the referents of constants
name c with the object b1 that it names. The simplest way to do this in general
is to have a function which assigns to each name in the language whatever
object in the domain it happens to name. You might call this function the
naming function. (The way we actually handle this when we come to the ¬nal
de¬nition incorporates the naming function in a slightly di¬erent way.)
We have neglected to say anything about the identity predicate =. That is identity
because its extension is ¬xed, once we have the domain D. It is always inter-
preted as meaning identity, so the extension is just the set of pairs a, a where
a ∈ D. So in this case, it consists of the set { b1 , b1 , b2 , b2 , b3 , b3 , b4 , b4 }.
Let™s stick with our little language a bit longer, but consider how we would
want to represent other worlds. In general we need: a domain of discourse D,
a subset Cu of D to serve as the extension of the predicate Cube, a set La of
pairs from D to serve as the extension of the predicate Larger, and a pairing
of the name c with its referent, some element of the domain D of discourse.
In order to have one single object to represent the whole world, with all
its relevant facts, we package the domain of discourse, the extensions of the
predicates, and the referents of the names, all into one mathematical object.
Just how this packaging is done is not too important, and di¬erent textbooks

Section 18.1
498 / Advanced Topics in FOL

do it in somewhat di¬erent ways. The most elegant packaging, and the one
we adopt, is to use a single function M. (“M” stands for “model,” which is
another common term for what we are calling a structure.)
The function M is de¬ned on the predicates of the language, the names
of the language, and the quanti¬er symbol ∀. Such a function is called a ¬rst-
order structure provided the following conditions are satis¬ed:
de¬nition of
¬rst-order structure
1. M(∀) is a nonempty set D, called the domain of discourse of M.
2. If P is an n-ary predicate symbol of the language then M(P) is a set of
n-tuples x1 , . . . , xn of elements of D. This set is called the extension of
P in M. It is required that the extension of the identity symbol consist
of all pairs x, x , for x ∈ D.
3. if c is any name of the language, then M(c) is an element of D, and is
called the referent of c in M.
Instead of writing M(Cube), it is more common to write CubeM , and similarly
for the other predicates and names. And it is common to write just DM for
the domain of discourse M(∀), or even just D if it is clear from context which
structure M we are talking about.
Let™s think for a minute about the conditions we™ve imposed on ¬rst-
order structures. If our goal in de¬ning the notion of a structure were simply
to devise set-theoretic models of blocks worlds, then it would be natural to
impose much stronger conditions than we have. For example, we might want
to require that DM be a set of blocks (not just any old objects), that CubeM
always be the set of cubes in DM and that LargerM always be the ordered
pairs x, y where x is larger than y. These requirements would be analogous
to our condition that the extension of the identity symbol always corresponds
to the real identity relation.
But remember what we are trying to capture. We are interested in char-
acterizing the ¬rst-order consequence relation, and as we have explained, this
relation ignores the speci¬c meanings of predicates other than =. When we
ignore the speci¬c meanings of Cube and Larger, all that we care about is
which objects in the domain satisfy the atomic w¬s Cube(x) and Larger(x, y).
This is why in our de¬nition we allow extensions of these predicates to be
arbitrary sets, so long as the arity of the relation is respected.


18.1 Write out a complete description of a ¬rst-order structure M that would represent Mary Ellen™s
 World. This has been done above except for the packaging into a single function.

Chapter 18
First-order structures / 499

18.2 (Simon says) Open Mary Ellen™s World. The structure M that we have used to model this world,
‚ with respect to the sublanguage involving only Cube, Larger, and c, is also a good model of
many other worlds. What follows is a list of proposed changes to the world. Some of them
are allowable changes, in that if you make the change, the model M still represents the world
with respect to this language. Other changes are not. Make the allowable changes, but not the
1. Move everything back one row.
2. Interchange the position of the tetrahedron and the large cube.
3. Make the tetrahedron a dodecahedron.
4. Make the large cube a dodecahedron.
5. Make the tetrahedron (or what was the tetrahedron, if you have changed it) large.
6. Add a cube to the world.
7. Add a dodecahedron to the world.

Now open Mary Ellen™s Sentences. Check to see that all these sentences are true in the world you
have built. If they are not, you have made some unallowable changes. Submit your modi¬ed
18.3 In the text we modeled Mary Ellen™s World with respect to one sublanguage of Tarski™s World.
 How would our structure have to be modi¬ed if we added the following to the language: Tet,
Dodec, Between? That is, describe the ¬rst-order structure that would represent Mary Ellen™s
World, in its original state, for this expanded language. [Hint: One of your extensions will be
the empty set.]
18.4 Consider a ¬rst-order language with one binary predicate Outgrabe. Suppose for some reason
 we are interested in ¬rst-order structures M for this language which have the particular domain
{Alice, Mad Hatter }. List all the sets of ordered pairs that could serve as the extension of the
symbol Outgrabe. How many would there be if the domain had three elements?
18.5 In Section 14.4 (page 387) we promised to show how to make the semantics of generalized
 quanti¬ers rigorous. How could we extend the notion of a ¬rst-order structure to accommo-
date the addition of a generalized quanti¬er Q? Intuitively, as we have seen, a sentence like
Q x (A(x), B(x)) asserts that a certain binary relation Q holds between the set A of things that
satisfy A(x) and the set B that satis¬es B(x) in M. Thus, the natural way to interpret them
is by means of a binary relation on „˜(DM ). What quanti¬er corresponds to the each of the
following binary relations on sets?
1. A ⊆ B
2. A © B = …
3. A © B = …
4. |A © B |= 1
5. |A © B |¤ 3
6. |A © B | > | A ’ B |

Section 18.1
500 / Advanced Topics in FOL

18.6 While we can™t say with precision exactly which binary relation a speaker might have in mind
 with the use of some quanti¬ers, like many, we can still use this framework to illustrate the
nature of the logical properties like conservativity, monotonicity, and so forth discussed in
Section 14.5. Each of the following properties of binary relations Q on subsets of D correspond
to a property of quanti¬ers. Identify them.
1. Q(A, B) if and only if Q(A, A © B)
2. If Q(A, B) and A ⊆ A then Q(A , B)
3. If Q(A, B) and A ⊆ A then Q(A , B)
4. If Q(A, B) and B ⊆ B then Q(A, B )
5. If Q(A, B) and B ⊆ B then Q(A, B )

Section 18.2
Truth and satisfaction, revisited

In Chapter 9, we characterized the notion of truth in a domain of discourse
rather informally. You will recall that in order to de¬ne what it means for
a quanti¬ed sentence (either ∀x S(x) or ∃x S(x)) to be true, we had to have
recourse to the notion of satisfaction, what it means for an object b to satisfy a
w¬ S(x) in a domain of discourse. This was de¬ned in terms of what it means
for the simpler sentence S(c) to be true, where c was a new name.
Now that we have de¬ned the notion of a ¬rst-order structure, we can
treat truth and satisfaction more rigorously. The aim here is just to see how
modeling satisfaction
and truth our informal treatment looks when you treat it mathematically. There should
be nothing surprising in this section, unless it is that these intuitive notions
are a bit complicated to de¬ne rigorously.
In our earlier discussion, we explained what it meant for an object b in
the domain of discourse to satisfy a w¬ S(v) with one free variable. That was
enough to serve our needs in discussing truth and the game. However, for
more advanced work, it is important to understand what it means for some
objects to satisfy a w¬ P(x1 , . . . , xn ) with n-free variables, for any n ≥ 0. The
case of n = 0 is the important special case where there are no free variables,
that is, where P is a sentence.
Let M be a ¬rst-order structure with domain D. A variable assignment
variable assignments
in M is, by de¬nition, some (possibly partial) function g de¬ned on a set of
variables and taking values in the set D. Thus, for example, if D = {a, b, c}
then the following would all be variable assignments in M:

1. the function g1 which assigns b to the variable x

Chapter 18
Truth and satisfaction, revisited / 501

2. the function g2 which assigns a, b, and c to the variables x, y, and z,

3. the function g3 which assigns b to all the variables of the language

4. the function g4 which is the empty function, that is, does not assign
values to any variables

The special case of the empty variable assignment g4 is important, so we empty variable
assignment (g… )
denote it by g… .
Given a w¬ P, we say that the variable assignment g is appropriate for P appropriate
if all the free variables of P are in the domain of g, that is, if g assigns objects
to each free variable of P. Thus the four variable assignments g1 , g2 , g3 , and
g4 listed above would have been appropriate for the following sorts of w¬s,

1. g1 is appropriate for any w¬ with the single free variable x, or with no
free variables at all;

2. g2 is appropriate for any w¬ whose free variables are a subset of {x, y, z};

3. g3 is appropriate for any w¬ at all; and

4. g4 (which we just agreed to write as g… ) is appropriate for any w¬ with no


. 90
( 107 .)