SQL and Relational Theory, 2nd Edition

MORE ON QUANTIFICATION

There are a number of further issues I need to discuss regarding quantification in particular.

We Don’t Need Both Quantifiers

It’s easy to see that any predicate that can be expressed in terms of EXISTS can be expressed in terms of FORALL instead and vice versa. By way of example, consider the following predicate once again:

     EXISTS x ( x is taller than Steve )

(“Somebody is taller than Steve”; of course, this predicate is in fact a simple proposition). 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 predicate

     EXISTS x ( p ( x ) )

is logically equivalent to the predicate

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

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

     FORALL x ( p ( x ) )

is logically equivalent to the predicate

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

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

It follows from all of the above that a formal language doesn’t need to support both EXISTS and FORALL explicitly. But it’s very desirable to support them both in practice. The reason is that some problems are “more naturally” formulated in terms of EXISTS, while others are “more naturally” formulated in terms of FORALL instead. For example, SQL supports EXISTS but not FORALL, as we know; as a consequence, certain queries are quite awkward ...