We next come to the de¬nition of truth by way of satisfaction. The de¬ni-

tion we gave earlier required us to de¬ne this by means of substituting names

for variables. The de¬nition we are about to give ends up being equivalent,

but it avoids this detour. It works by de¬ning satisfaction more generally. In

particular, we will de¬ne what it means for an assignment g to satisfy a w¬

P(x1, . . . , xn ) in M. We will de¬ne this by induction, with cases corresponding

to the various ways of building up w¬s from atomic w¬s. This will reduce the

problem gradually to the base case of atomic w¬s, where we say explicitly

what satisfaction means.

In order to handle the two inductive clauses in which P starts with a

quanti¬er, we need a way to modify a variable assignment. For example, if g modi¬ed variable

assignments

is de¬ned on x and we want to say what it means for g to satisfy ∀z Likes(x, z),

then we need to be able to take any object b in the domain of discourse and

consider the variable assignment which is just like g except that it assigns the

value b to the variable z. We will say that g satis¬es our w¬ ∀z Likes(x, z) if

and only if every such modi¬ed assignment g satis¬es Likes(x, z). To make

this a bit easier to say, we introduce the notation “g[z/b]” for the modi¬ed

variable assignment. Thus, in general, g[v/b] is the variable assignment whose

Section 18.2

502 / Advanced Topics in FOL

domain is that of g plus the variable v and which assigns the same values as

g, except that the new assignment assigns b to the variable v.

Here are a couple examples, harking back to our earlier examples of vari-

able assignments given above:

1. g1 assigns b to the variable x, so g1 [y/c] assigns b to x and c to y. By

contrast, g1 [x/c] assigns a value only to x, the value c.

2. g2 assigns a, b, c to the variables x, y, and z, respectively. Then g2 [x/b]

assigns the values b, b, and c to x, y, and z, respectively. The assignment

g2 [u/c] assigns the values c, a, b, and c to the variables u, x, y, and z,

respectively.

3. g3 assigns b to all the variables of the language. g3 [y/b] is the same

assignment, g3 , but g3 [y/c] is di¬erent. It assigns c to y and b to every

other variable.

4. g4 , the empty function, does not assign values to any variables. Thus

g4 [x/b] is the function which assigns b to x. Notice that this is the same

function as g1 .

Notice that what variable assignments do for us is allow us to treat free

variables as if they have a temporary denotation, not one assigned by the

structure, but one assigned for purposes of the inductive de¬nition of satisfac-

tion. Thus, if a variable assignment g is appropriate for a w¬ P, then between

M and g, all the terms (constants and variables) in P have a denotation. For

[[t]]M any term t, we write [[t]]M for the denotation of t. Thus [[t]]M is tM if t is an

g g g

individual constant and g(t) if t is a variable.

We are now in a position to de¬ne what it means for a variable assignment

g to satisfy a w¬ P in a ¬rst-order structure M. First, it is always required

that g be appropriate for P, that is, be de¬ned for all the free variables of P,

and maybe other free variables. Second, there is nothing at all surprising in

the following de¬nition. There shouldn™t be, anyway, since we are just trying

to make precise the intuitive idea of satisfaction of a formula by a sequence

of objects. We suggest that you work through the example at the end of the

de¬nition, referring back to the de¬nition as needed, rather than try to read

the de¬nition itself right o¬.

De¬nition (Satisfaction) Let P be a w¬ and let g be an assignment in M

de¬nition of

satisfaction which is appropriate for P.

1. The atomic case. Suppose P is R(t1 , . . . ,tn ), where R is an n-ary predi-

cate. Then g satis¬es P in M if and only if the n-tuple [[t1 ]]M , . . . , [[tn ]]M

g g

M.

is in R

Chapter 18

Truth and satisfaction, revisited / 503

2. Negation. Suppose P is ¬Q. Then g satis¬es P in M if and only if g

does not satisfy Q.

3. Conjunction. Suppose P is Q § R. Then g satis¬es P in M if and only

if g satis¬es both Q and R.

4. Disjunction. Suppose P is Q ∨ R. Then g satis¬es P in M if and only

if g satis¬es Q or R or both.

5. Conditional. Suppose P is Q ’ R. Then g satis¬es P in M if and only

if g does not satisfy Q or g satis¬es R or both.

6. Biconditional. Suppose P is Q ” R. Then g satis¬es P in M if and

only if g satis¬es both Q and R or neither.

7. Universal quanti¬cation. Suppose P is ∀v Q. Then g satis¬es P in M

if and only if for every d ∈ DM , g[v/d] satis¬es Q.

8. Existential quanti¬cation. Suppose P is ∃v Q. Then g satis¬es P in

M if and only if for some d ∈ DM , g[v/d] satis¬es Q.

M |= P [g]

It is customary to write

M |= P [g]

to indicate that the variable assignment g satis¬es w¬ P in the structure M.

Let™s work through a very simple example. We take a structure M with

domain D = {a, b, c}. Let us suppose that our language contains the binary

predicate Likes and that the extension of this predicate is the following set of

pairs:

LikesM = { a, a , a, b , c, a }

That is, a likes itself and b, c likes a, and b likes no one. Let us consider the w¬

∃y (Likes(x, y) § ¬Likes(y, y))

with the single free variable x. If the above de¬nition is doing its stu¬, it

should turn out that an assignment g satis¬es this w¬ just in case g assigns

a to the variable x. After all, a is the only individual who likes someone who

does not like himself.

Let™s examine the de¬nition of satisfaction to see if this is the way it

turns out. First, note that g has to assign some value to x, since it has to be

appropriate for the formula. Let us call this value e; e is one of a, b, or c. Next,

we see from the clause for ∃ that g satis¬es our w¬ just in case there is some

object d ∈ D such that g[y/d] satis¬es the w¬

Likes(x, y) § ¬Likes(y, y)

Section 18.2

504 / Advanced Topics in FOL

But g[y/d] satis¬es this w¬ if and only if it satis¬es Likes(x, y) but does not

satisfy Likes(y, y), by the clauses for conjunction and negation. Looking at

the atomic case, we see that this is true just in case the pair e, d is in the

extension of Likes, while the pair d, d is not. But this can only happen if

e = a and d = b. Thus the only way our original g can satisfy our w¬ is if it

assigns a to the variable x, as we anticipated.

Notice in the above example how we started o¬ with a w¬ with one free

variable and an assignment de¬ned on that one variable, but in order to give

our analysis, we had to move to consider a w¬ with two free variables and

so to assignments de¬ned on those two free variables. This is typical. After

all, what we are really interested in is truth for sentences, that is, w¬s with

no free variables, but in order to de¬ne this, we must de¬ne something more

general, satisfaction of w¬s with free variables by assignments de¬ned on those

variables. Indeed, having de¬ned satisfaction, we are now in a position to look

at the special case where the w¬s have no free variables and use it for our

de¬nition of truth.

De¬nition (Truth) Let L be some ¬rst-order language and let M be a struc-

de¬nition of truth

ture for L. A sentence P of L is true in M if and only if the empty variable

assignment g… satis¬es P in M. Otherwise P is false in M.

M |= P Just as we write M |= Q [g] if g satis¬es a w¬ Q in M, so too we write:

M |= P

if the sentence P is true in M.

Let™s look back at the structure given just above and see if the sentence

∃x ∃y (Likes(x, y) § ¬Likes(y, y))

come out as it should under this de¬nition. First, notice that it is a sentence,

that is, has no free variables. Thus, the empty assignment is appropriate

for it. Does the empty assignment satisfy it? According to the de¬nition of

satisfaction, it does if and only if there is an object that we can assign to the

variable x so that the resulting assignment satis¬es

∃y (Likes(x, y) § ¬Likes(y, y))

But we have seen that there is such an object, namely, a. So the sentence is

true in M; in symbols, M |= ∃x ∃y (Likes(x, y) § ¬Likes(y, y)).

Consider next the sentence

∀x ∃y (Likes(x, y) § ¬Likes(y, y))

Chapter 18

Truth and satisfaction, revisited / 505

Does the empty assignment satisfy this? It does if and only if for every object

e in the domain, if we assign e to x, the resulting assignment g satis¬es

∃y (Likes(x, y) § ¬Likes(y, y))

But, as we showed earlier, g satis¬es this only if g assigns a to x. If it assigns,

say, b to x, then it does not satisfy the w¬. Hence, the empty assignment does

not satisfy our sentence, i.e., the sentence is not true in M. So its negation is;

in symbols, M |= ¬∀x ∃y (Likes(x, y) § ¬Likes(y, y)).

A number of problems are given later to help you understand that this

does indeed model the informal, intuitive notion. In the meantime, we will

state a proposition that will be important in proving the Soundness Theorem

for fol. Intuitively, whether or not a sentence is true in a structure should

depend only on the meanings speci¬ed in the structure for the predicates and

individual constants that actually occur in the sentence. That this is the case

is a consequence of the following, somewhat stronger claim.

Proposition 1. Let M1 and M2 be structures which have the same domain

and assign the same interpretations to the predicates and constant symbols

in a w¬ P. Let g1 and g2 be variable assignments that assign the same objects

to the free variables in P. Then M1 |= P[g1] i¬ M2 |= P[g2 ].

The proof of this proposition, which uses induction on w¬s, is a good

exercise to see if you understand the de¬nition of satisfaction. Consequently,

we ask you to prove it in Exercise 10.

Once we have truth, we can de¬ne the important notions of ¬rst-order

consequence and ¬rst-order validity, our new approximations of the intuitive

notions of logical consequence and logical truth. In the following de¬nitions,

we assume that we have a ¬xed ¬rst-order language and that all sentences

come from that language. By a structure, we mean any ¬rst-order structure

that interprets all the predicates and individual constants of the language.

De¬nition[First-order consequence] A sentence Q is a ¬rst-order consequence de¬nition of

FO consequence

of a set T = {P1 , . . . } of sentences if and only if every structure that makes

all the sentences in T true also makes Q true.

You can see that this de¬nition is the exact analogue of our de¬nition of

tautological consequence. The only di¬erence is that instead of rows of a truth

table (or truth value assignments), we are using ¬rst-order structures in the

de¬nition. We similarly modify our de¬nition of tautology to get the following

de¬nition of ¬rst-order validity. de¬nition of

FO validity

De¬nition (First-order validity) A sentence P is a ¬rst-order validity if and

only if every structure makes P true.

Section 18.2

506 / Advanced Topics in FOL

We will also use other notions analogous to those introduced in proposi-

tional logic in discussing ¬rst-order sentences and sets of sentences. For exam-

ple, we will call a sentence fo-satis¬able if there is a ¬rst-order structure that

makes it true, and call a set of sentences fo-satis¬able if there is a structure

FO-satis¬able

that makes all the members of the set true. Sometimes we will leave out the

“fo” if the context make it clear what kind of satis¬ability we are referring to.

You may have wondered why Tarski™s World is so named. It is our way of

paying tribute to Alfred Tarski, the logician who played the pivotal role in the

development of the semantic conception of logic. It was Tarski who developed

the notion of a ¬rst-order structure, the notion of satisfaction, and who gave

the ¬rst analysis of truth, ¬rst-order validity, and ¬rst-order consequence along

the lines we have sketched here.

One ¬nal note. If you go on to study logic further, you will discover that our

treatment of satisfaction is a bit more general that most. Tarski, and most

of those who have followed him, have restricted attention to total variable

assignments, that is, to variable assignments that are de¬ned on all variables.

Then, to de¬ne truth, they pick out one of these total assignments and use it,

since they cannot use the empty assignment. The two approaches agree on the

resulting notion of truth, and hence on the notion of logical consequence. The

approach adopted here using partial assignments is more general, seems to us

more natural, and ¬ts in better with our implementation of Tarski™s World. It

is easy to represent ¬nite partial assignments in the computer™s memory, but

not so easy to deal with in¬nite assignments.

Remember

1. First-order structures are mathematical models of the domains about

which we make claims using fol.

2. Variable assignments are functions mapping variables into the domain

of some ¬rst-order structure.

3. A variable assignment satis¬es a w¬ in a structure if, intuitively, the

objects assigned to the variables make the w¬ true in the structure.

4. Using the notion of satisfaction, we can de¬ne what it means for a

sentence to be true in a structure.

5. Finally, once we have the notion of truth in a structure, we can model

the notions of logical truth, and logical consequence.