SQL and Relational Theory, 2nd Edition

QUANTIFICATION

I showed in the previous section that one way to get a proposition from a predicate is to invoke it with an appropriate set of arguments. But there’s another way, too, and that’s by means of quantification. Let p(x) be a monadic predicate (I show the single parameter x explicitly for clarity). Then:

• The expression

  EXISTS x ( p ( x ) )

  is a proposition, and it means: “There exists at least one possible argument value a that can be substituted for the parameter x such that p(a) evaluates to TRUE” (in other words, the argument value a satisfies predicate p). For example, if p is the predicate “x is a logician,” then

  EXISTS x ( x is a logician )

  is a proposition—one that evaluates to TRUE, as it happens (for example, take a to be Bertrand Russell).

• The expression

  FORALL x ( p ( x ) )

  is a proposition, and it means: “All possible argument values a that can be substituted for the parameter x are such that p(a) evaluates to TRUE” (in other words, all such argument values a satisfy predicate p). For example, if again p is the predicate “x is a logician,” then

  FORALL x ( x is a logician )

  is a proposition—one that evaluates to FALSE, as it happens (for example, take a to be George W. Bush).

Observe that it’s sufficient to produce a single example to show the truth of the EXISTS proposition and a single counterexample to show the falsity of the FORALL proposition. Observe too in both cases that the parameter must be constrained to “range over” some set of permissible values (the set of ...