Quantifiers

Predicates

Not all mathematical statements are propositions; that is, not every mathematical statement can be given a truth value of true or false. Consider the following statements:

1. x2 = 4 2. For every real number x, x2 = 4. 3. There exists a real number x, such that x2 = 4. 4. For all x in {-2, 2}, x2 = 4. 5. For all real numbers x such that x2 = 4, |x| = 2. 6. For any real number x, x2 = 4 if and only if |x| = 2.

With a little thought, we see that 2. is false while 3., 4., 5., and 6. are true. On the other hand, statement 1. is neither true nor false. Thus, it is not a proposition even though it is a clearly useful mathematical statement and an important component in interesting propositions. Statement 1. is an example of a predicate in that it is true for some values of x and false for other values of x. The statement (|x| = 2) is another predicate. Here is a semi-formal definition.

DEFINITION: A variable is a symbol representing an unspecified element of some set that is refered to as the scope of the variable. A predicate is a statement P(x₁,...,x_n) involving variables x₁, ..., x_n with the property that when x₁, ..., x_n are given specific values, the resulting statement is either true or false.

Thus, a predicate is a statement that could be a proposition, except for ambiguity that exists because the scope or range of possibilities for the variables in the statement is not specified. The scope is usually specified by the use of quantifiers. These are phrases such as for every, there exists, for all, for some, etc., combined with a phrase putting the variable(s) in some set.

It should be pointed out that the scope of a variable is often understood from context and left unspecified in a proposition. For example, in a course where the natural field of numbers under consideration is always the real numbers, a statement like "x⁴ = 1 ==> x = 1 or -1" would be considered a proposition with the quantifier, "for any real number x", understood. If all calculations in the course in question are over the complex field, then the quantifier, "for any complex number x", would be understood and the statement still qualifies as a proposition.

As it turns out "for any real number x, x⁴ = 1 ==> x = 1 or -1" is true while "for any complex number x, x⁴ = 1 ==> x = 1 or -1" is false.

Universal Quantifiers

Universal quantifiers are those that are used to specify the scope to which a variable is restricted and indicating that the predicate which follows should be considered for variables in that scope. In the following examples, the universal quantifier is in quotation marks. .

1. "For every" positive integer n, 1 + 2 + ... +n = n(n+1)/2.
2. "For any" real number x, x² > 0.
3. "For all" triangles T, if a, b and c are the lengths of the sides of T, with c the longest, then T is a right angled triangle iff a² + b² = c².

Each of for every, for any, and for all have the same logical meaning. This universal quantifier has a symbol " that is a convenient shorthand for taking notes. Thus 2. above could be written " x in R, x² > 0.

A statement of the form "" x in S, P(x)" means S is a set giving the scope of the variable x and the predicate P(x) is meant for every member x of S. To say " x in S, P(x) is true means P(x) is true no matter which x from S is used. On the other hand " x in S, P(x) is false means there is at least one x in S for which P(x) is false.

Existential Quantifiers

This leads us to consider existential quantifiers which are used to indicate that the predicate which follows applies to at least one value of the variable within the indicated scope. The existential quantifier is expressed as there exists, for some, for at least one or similar phrases usually combined with such that after the scope of the variable and just before the predicate. The symbol that is often used for the existential quantifier is $.

Forming negations of statements with quantifiers is often necessary. A little thought will convince you of the following rules:

	In words	In symbols
Proposition Q	For all x in S, P(x) holds	" x in S, P(x)
Negation of Q	It is not the case that for all x in S, P(x) holds	~(" x in S, P(x))
Equivalent negation of Q	There exists an x in S such that P(x) does not hold	$ x in S, ~P(x)
Proposition R	There exists an x in S such that P(x) holds	$ x in S, P(x)
Negation of R	It is not the case that there exists an x in S such that P(x) holds	~($ x in S, P(x))
Equivalent negation of R	For all x in S, P(x) does not hold	" x in S, ~P(x)

Notice how moving the negation across a quantifier switches it from universal to existential and vice-versa. This is an absolutely crucial point.

---