## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required