CSE 463/563, Spring 2005

Satisfaction of a Quantified WFF

Last Update: 3 March 2005

Note: NEW or UPDATED 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, D, contains the following items:

Suppose our language has these variables:

The definition of satisfaction for a universally quantified wff is:

E.g., suppose v is the variable: x50
and α is the wff: "x50^2 = x50*x50"

Consider the set of all variables: {x1, ..., x50, ..., x100}

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

Let's say that this set = {d1, ..., d50, ..., d100}.

Now consider all mu' that differ from mu at most on x50. Suppose they are mu1,...,mu300.

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

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

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

Note, in particular, that mu1 gives us: {d1, ..., d50, ..., d100}. What about the others? Well, each differs from mu (or mu1) at most on what it does to x50, 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 x50.

Now, according to the definition, if all of these mu' satisfy "x50^2=x50*x50", then our original mu will satisfy Ax50[x50^2=x50*x50].

But to decide if a given mu' satisfies "x50^2=x50*x50", we can ignore what it does to everything except x50.

(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 x50, each mu' differs. Does each one satisfy "x50^2=x50*x50"? Sure! Here's the proof:

So: all the mu' that differ from mu at most on x50 satisfy x50^2=x50*x50, so mu satisfies Ax50[x50^2=x50*x50].

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-2005-03-03.html