<<

. 91
( 107 .)



>>

free variables, that is, for sentences, but not for w¬s with free variables.

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.

<<

. 91
( 107 .)



>>