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 all persons, in the example). I’ll come back to this latter point in the section RELATIONAL CALCULUS, later.

The term used in logic for constructs like EXISTS x and FORALL x is quantifiers (the term derives from the verb to quantify, which simply means to express as a quantity—that is, to say how much of something there is or how many somethings there are). Quantifiers of the form EXISTS ... are said to be existential; quantifiers of the form FORALL ... are said to be universal. And in logic texts, EXISTS is usually represented by a backward E (“∃”) and FORALL by an upside down A (“∀”). I use the keywords EXISTS and FORALL here for readability.

Aside: At this point, one reviewer asked whether a quantifier is just another connective. No, it isn’t. Let p(x) and q(x) be predicates, each with a single parameter x. Then p(x) and q(x) can be combined in various ways by means of connectives (as in, e.g., p(x) AND q(x)), but the result is always just another predicate with that same single parameter x. By contrast, quantifying over x—that is, forming an expression such as EXISTS x (p(x)) or FORALL x (q(x))—has the effect of converting the predicate concerned into a proposition. Thus, there’s a clear logical difference between the two concepts. (Though I should add that in the database context, at least, the quantifiers can be defined in terms of certain connectives. I’ll explain this point later, in the section MORE ON QUANTIFICATION.) End of aside.

By way of another example, consider the dyadic predicate “x is taller than y.” If we quantify existentially over x, we obtain:

EXISTS x ( x is taller than y )

This statement isn’t a proposition, because it isn’t unequivocally either true or false; in fact, it’s a monadic predicate—it has a single parameter, y. Suppose we invoke this predicate with argument Steve. We obtain:

EXISTS x ( x is taller than Steve )

This statement is a proposition (and if there exists at least one person—Arnold, say—who’s taller than Steve, then it evaluates to TRUE). But another way to obtain a proposition from the original predicate is to quantify over both parameters. For example:

EXISTS x ( EXISTS y ( x is taller than y ) )

This statement is indeed a proposition; it evaluates to FALSE only if nobody is taller than anybody and to TRUE otherwise (think about it!).

There are several lessons to be learned from this example:

  • To obtain a proposition from an n-adic predicate by quantification alone, it’s necessary to quantify over every parameter. More generally, if we quantify over m parameters (m ≤ n), we obtain a k-adic predicate, where k = n- m.

  • Let’s focus on existential quantification only for the moment. Then there are apparently two different propositions we can obtain in the example by “quantifying over everything”:

    EXISTS x ( EXISTS y ( x is taller than y ) )

EXISTS y ( EXISTS x ( x is taller than y ) )

    It should be clear, however, that these two propositions both say the same thing: “There exist persons x and y such that x is taller than y.” More generally, in fact, it’s easy to see that a series of like quantifiers (all existential or all universal) can be written in any sequence we choose without changing the overall meaning. By contrast, with unlike quantifiers, the sequence matters (see the point immediately following).

  • When we “quantify over everything,” each individual quantifier can be either existential or universal. In the example, therefore, there are six distinct propositions that can be obtained by fully quantifying, and I’ve listed them below. (Actually there are eight, but two of them can be ignored by virtue of the previous point.) I’ve also shown a precise natural language interpretation in each case. Note that those interpretations are all logically different!—in particular, some of them evaluate to TRUE and some to FALSE. Please note, however, that I’ve had to assume in connection with certain of those evaluations that there does exist at least one person “in the universe,” as it were. I’ll come back to this assumption in the section MORE ON QUANTIFICATION, later.

    EXISTS x ( EXISTS y ( x is taller than y ) )

    Meaning: Somebody is taller than somebody; TRUE, unless everybody is the same height.

    EXISTS x ( FORALL y ( x is taller than y ) )

    Meaning: Somebody is taller than everybody (that particular somebody included!); clearly FALSE.

    FORALL x ( EXISTS y ( x is taller than y ) )

    Meaning: Everybody is taller than somebody; clearly FALSE.

    EXISTS y ( FORALL x ( x is taller than y ) )

    Meaning: Somebody is shorter than everybody (that particular somebody included); clearly FALSE. Note: Actually I’m cheating a little bit here, because I haven’t said what I mean by “shorter.” But I could have done—i.e., I could have stated explicitly, somehow, that the predicates “x is taller than y” and “y is shorter than x” are logically equivalent—and I’ll assume for the rest of this section that I’ve done so.

    FORALL y ( EXISTS x ( x is taller than y ) )

    Meaning: Everybody is shorter than somebody; clearly FALSE.

    FORALL x ( FORALL y ( x is taller than y ) )

    Meaning: Everybody is taller than everybody; clearly FALSE.

Last (I apologize for the repetition, but the point is important): Even though five out of six of the foregoing propositions do all evaluate to the same truth value, FALSE, it doesn’t follow that they all mean the same thing, and indeed they don’t; in fact, no two of them do.

Free and Bound Variables

What I’ve so far been calling parameters are more usually known in logic as free variables—and quantifying over a free variable, using either EXISTS or FORALL, converts that free variable into what’s called a bound variable. For example, consider again the 2-place predicate from the previous section:

x is taller than y

Here x and y are free variables. If we now quantify existentially over x,[140] we obtain:

EXISTS x ( x is taller than y )

Now y is free (still) but x is bound. And if we now quantify existentially over y as well, we obtain:

EXISTS x EXISTS y ( x is taller than y )

Now x and y are both bound, and there are no free variables at all (the predicate has degenerated to a proposition).

Now, we already know that free variables correspond to parameters, in conventional programming terms. Bound variables, by contrast, don’t have an exact counterpart in conventional programming terms; instead, they’re just a kind of dummy—they serve only to link the predicate inside the parentheses to the quantifier outside. For example, consider the simple predicate (actually a proposition):

EXISTS x ( x > 3 )

This proposition merely asserts that there exists some integer greater than three. (I’m assuming here that x is constrained to “range over” the set of integers. Again, I’ll come back to this question of “ranges” later.) Note, therefore, that the meaning of the proposition would remain totally unchanged if the two x’s were both replaced by some other variable y. In other words, the proposition

EXISTS y ( y > 3 )

is semantically identical to the one just shown.

Now consider the predicate:

EXISTS x ( x > 3 ) AND x < 0

Here there are three x’s—but they don’t all mean the same thing. The first two are bound, and can be replaced by (say) y without changing the overall meaning; but the third is free and can’t be replaced with impunity. Thus, of the following two predicates, the first is equivalent to the one just shown and the second isn’t:

EXISTS y ( y > 3 ) AND x < 0

EXISTS y ( y > 3 ) AND y < 0

As this example demonstrates, the terminology of free vs. bound “variables” doesn’t really refer to variables per se, but rather to variable occurrences—occurrences of references to variables within some predicate, to be precise. In the predicate EXISTS y (y > 3) AND y < 0, for example, it’s the first two occurrences of the reference to y that are bound, and the third such occurrence that’s free. Despite this state of affairs, it’s usual (perhaps regrettably) to talk about free and bound variables as such,[141] even though such talk is really quite sloppy. Be on your guard for confusion in this area!

To close this section, I remark that we can now (re)define a proposition to be a predicate in which all of the variables are bound: equivalently, one that involves no free variables.


[140] Existentially just to be definite. Quantifying universally instead would make no difference to the point I’m making here.

[141] Even, sometimes, in logic textbooks, where the practice really ought to be deprecated.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.119.104.160