More on Quantification

This section discusses a number of miscellaneous issues regarding quantification.

We Don't Need Both Quantifiers

You might already know that we don't actually need both EXISTS and FORALL. The reason is that any statement that can be expressed in terms of EXISTS can always be expressed in terms of FORALL instead and vice versa. By way of example, consider again the predicate:

     EXISTS x ( x is taller than Steve ) 

("Somebody is taller than Steve"). Another way to say the same thing is:

     NOT ( FORALL x ( NOT ( x is taller than Steve ) ) ) 

("It is not the case that nobody is taller than Steve"). More generally, in fact, the statement:

     EXISTS x ( p ( x ) ) 

is logically equivalent to the following statement:

     NOT ( FORALL x ( NOT ( p ( x ) ) ) 

(where the predicate p might legitimately involve other parameters in addition to x). Likewise, the statement:

     FORALL x ( p ( x ) ) 

is logically equivalent to the statement:

     NOT ( EXISTS x ( NOT ( p ( x ) ) ) 

(where, again, the predicate p might legitimately involve other parameters in addition to x).

It follows from the foregoing that a formal language need not explicitly support both EXISTS and FORALL. But it's very desirable to support both in practice. The reason is that some problems are "more naturally" formulated in terms of EXISTS and others are "more naturally" formulated in terms of FORALL. For example, SQL supports EXISTS but not FORALL; as a consequence, certain queries are quite awkward to formulate in SQL. For example, consider the query "Get suppliers who supply all parts," which can be expressed in logic quite simply as follows:

     s WHERE FORALL p EXISTS sp ( s.SNO = sp.SNO AND sp.PNO = p.PNO ) 

("Get suppliers s such that, for all parts p, there exists a shipment sp linking that supplier s to that part p"; the variables s, p, and sp are to be understood as ranging over the current values of relvars S, P, and SP, respectively). In SQL, by contrast, the query looks something like this:

     SELECT s.*     FROM   S AS s     WHERE  NOT EXISTS          ( SELECT p.*            FROM   P AS p            WHERE  NOT EXISTS                 ( SELECT sp.*                   FROM   SP AS sp                   WHERE  s.SNO = sp.SNO                   AND    sp.PNO = p.PNO ) ) 

("Get suppliers s such that there does not exist a part p such that there does not exist a shipment sp linking that supplier s to that part p"). Well, single negation is bad enough (many users have difficulty with it); double negation, as in this SQL query, is much worse!

Empty Ranges

Consider again the fact that the statements:

     EXISTS x ( p ( x ) ) 

and:

 NOT ( FORALL x ( NOT ( p ( x ) ) ) 

are logically equivalent. As I've indicated several times already, the bound variable x in each of these statements must "range over" some set of permissible values. Suppose now that the set in question is empty (it might, for example, be the set of people over 50 feet tall). Then:

• The quantifier EXISTS x clearly evaluates to FALSE (because no such x exists).

• The statement EXISTS x (p(x)) "There exists an x that makes p(x) evaluate to TRUE" thus evaluates to FALSE as well, regardless of what p(x) happens to be. For example, the statement "There exists a person over 50 feet tall who works for IBM" evaluates to FALSE (unsurprisingly).

• It follows that the negation NOT EXISTS x (p(x)), which is equivalent to the statement FORALL x (NOT (p(x)), evaluates to TRUE again, regardless of what p(x) happens to be. For example, the statement "All persons over 50 feet tall don't work for IBM" or, more idiomatically, "No person over 50 feet tall works for IBM" evaluates to TRUE (again unsurprisingly).

• But if the predicate p(x) is arbitrary, then so is the predicate NOT (p(x)). And therefore we have the following possibly surprising result: the statement FORALL x ( . . . ) evaluates to TRUE if there are no x's, regardless of what appears inside the parentheses. For example, the statement "All persons over 50 feet tall do work for IBM" also evaluates to TRUE(!) because, to say it again, there aren't any persons over 50 feet tall.

One implication of this state of affairs is that certain queries produce a result that you might not expect (if you don't know logic, that is). For example, the following query:

     s WHERE FORALL p           ( IF p.COLOR = 'Purple'             THEN EXISTS sp ( s.SNO = sp.SNO AND sp.PNO = p.PNO ) ) 

("Get suppliers who supply all purple parts") will return all suppliers if there aren't any purple parts. Exercise: Show an SQL formulation of this query.

Defining EXISTS and FORALL

You might have already realized that EXISTS and FORALL can be defined as an iterated OR and an iterated AND, respectively. I'll consider EXISTS first. Let p(x) be a predicate with a parameter x and let x range over the set X = {x1, x2, . . . , xn}. Then:

     EXISTS x ( p ( x ) ) 

is a predicate, and it's defined to be equivalent to (and hence shorthand for) the predicate:

     FALSE OR p ( x1 ) OR p ( x2 ) OR ... OR p ( xn ) 

Observe in particular that this expression evaluates to FALSE if X is empty (as we already know). By way of example, let p(x) be "x has a moon" and let X be the set {Mercury, Venus, Earth, Mars}. Then the predicate EXISTS x (p(x)) becomes "EXISTS x (x has a moon)," and it's shorthand for:

     FALSE OR ( Mercury has a moon ) OR ( Venus has a moon )           OR ( Earth has a moon )   OR ( Mars has a moon ) 

which evaluates to TRUE because (for example) "Mars has a moon" is true. Similarly:

     FORALL x ( p ( x ) ) 

is a predicate, and it's defined to be equivalent to (and hence shorthand for) the predicate:

     TRUE AND p ( x1 ) AND p ( x2 ) AND ... AND p ( xn ) 

And this expression evaluates to TRUE if X is empty (again, as we already know). By way of example, let p(x) and X be as in the EXISTS example above. Then the predicate FORALL x (p(x)) becomes "FORALL x (x has a moon)," and it's shorthand for:

     TRUE AND ( Mercury has a moon ) AND ( Venus has a moon )          AND ( Earth has a moon )   AND ( Mars has a moon ) 

which evaluates to FALSE because (for example) "Venus has a moon" is false.

As an aside, let me remark that as the examples clearly demonstrate defining EXISTS and FORALL as iterated OR and AND, respectively, means that every predicate that involves quantification is equivalent to one that doesn't. Thus, you might be wondering, not without some justification, just what this business of quantification is really all about. Why all the fuss? The answer is as follows: we can define EXISTS and FORALL as iterated OR and AND only because the sets we have to deal with are thankfully always finite (because we're operating in the realm of computers, and computers in turn are finite, of course). In pure predicate logic, where there's no such restriction, those definitions aren't valid.

Perhaps I should add that, even though we're always dealing with finite sets and EXISTS and FORALL are thus merely shorthand, they're extremely useful shorthand! For my part, I certainly wouldn't want to have to formulate queries and the like purely in terms of AND and OR, without being able to use the quantifiers.

Other Kinds of Quantifiers

While it's true that EXISTS and FORALL are the most important quantifiers in practice, they aren't the only ones possible. There's no a priori reason, for example, why we shouldn't allow quantifiers of the form:

     there exist at least three x's such that 

or:

     a majority of x's are such that 

or:

     an odd number of x's are such that 

(and so on). One fairly important special case is there exists exactly one x such that. I'll use the keyword UNIQUE for this one. Here are some examples:

     UNIQUE x ( x is taller than Arnold ) 

Meaning: Exactly one person is taller than Arnold; probably FALSE.

     UNIQUE x ( x has social security number y ) 

Meaning: Exactly one person has social security number y (y is a parameter, of course). We can't assign a truth value to this example, because it's a predicate, not a proposition.

     FORALL y UNIQUE x ( x has social security number y ) 

Meaning: Everybody has a unique social security number. (I'm assuming here that y ranges over the set of all social security numbers actually assigned, not all possible ones. Incidentally, does this predicate which is in fact a proposition, of course evaluate to TRUE?)

As another exercise, what does the following predicate mean?

     FORALL x UNIQUE y ( x has social security number y )