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:
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:
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:
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:
And similarly, "mutatis mutandis" (as mathematicians say;
i.e., changing what needs to be changed), for the existential quantifier.