Last Update: 4 March 2005
Note: or material is highlighted |

In case my explanation in lecture of the definition of satisfaction for a quantified wff wasn't clear, here it is at greater length (for a finite case, which may make it easier to understand, and can be done "wolog", i.e. "without loss of generality").

Suppose our domain, , contains the following items:

Suppose our language has these variables:

The definition of satisfaction for a universally quantified wff is:

E.g., suppose is the variable:

and is the wff: "
"

Consider the set of all variables:

Consider what set of members of we get by applying a variable
assignment to all the members of this set:

Let's say that this set = .

Now consider all that differ from at most on . Suppose they are .

(It may be that differ from on other variables, too, so we don't consider these at all!)

Note that our above is one of these 300
(because all the differ **at most** on ,
meaning that they might not differ on at all).
For convenience, let's say that our above is .

So consider what all these do to the set of all variables; they map them into sets of elements of as follows:

Note, in particular, that gives us: . What about the others? Well, each differs from (or ) at most on what it does to , so we get the following:

I.e., they are all alike on the first 49 variables and on the last 50 variables, but they can vary wildly on good old .

Now, according to the definition, if all of these satisfy " ", then our original will satisfy " ".

But to decide if a given satisfies " ", we can ignore what it does to everything except .

(We can do this for 2 reasons: First, they **don't** differ on the other
variables. Second, our wff only contains that one variable, so that's
the only one we care about.)

On , each differs. Does each one satisfy " "? Sure! Here's the proof:

So: all the that differ from mu at most on satisfy " ", so satisfies " ".

And similarly, "mutatis mutandis" (as mathematicians say;
i.e., changing what needs to be changed), for the existential quantifier.

Copyright © 2005 by William J. Rapaport (rapaport@cse.buffalo.edu)

file: 563S05/satisfaction/satisfaction-2005-03-04.html