ńņš. 90 |

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.

Exercises

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

others.

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

world.

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,

respectively

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

assignments

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,

respectively:

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 |