Quantifiers - Quantifiers and Functions - Mathematical Sentences

Mathematical Writing - Vivaldi Franco 2014

Quantifiers - Quantifiers and Functions
Mathematical Sentences

Interesting mathematical statements—such as (4.1)—refer to families of objects rather than to individual objects. The formulation of general statements requires two special symbols, the universal quantifier $$\forall $$ and the existential quantifier $$\exists $$. These symbols translate into words in several equivalent ways:

Expressions with quantifiers have the following syntax:

(4.18)

where $$X$$ is a set and $${\fancyscript{P}}$$ is a predicate over $$X$$. The quantifier is followed by the symbol being quantified, the membership operator, a set, and a predicate. The acronym ’s.t.’ (for ’such that’) is sometimes inserted in the second symbolic expression (4.18) before the predicate:

$$ \exists x\in X\quad \text { s.t.}\quad {\fancyscript{P}}(x). $$

Without a predicate the expression $$\forall x\in X$$ is incomplete and meaningless. The expression $$\exists x\in X$$ is meaningful but not used; one instead writes $$X\not =\emptyset $$.

The meaning of the expressions (4.18) should be clear; in particular, each expression has a logical value. For example, the following sentences are TRUE:

In translating the symbolic expressions we haven’t merely converted symbols into words following (4.18). We have also synthesised meaning, and in doing so the quantified variable $$x$$ has become silent—no explicit reference to it remains in the sentence. This is an intrinsic phenomenon, as we shall see.

If the ambient set is clear from the context, then reference to it may be omitted. This is invariably the case if the quantifier appears in conjunction with an inequality that restricts the variable’s range. Of the following equivalent expressions

$$ \forall n>3,\,\,n!>2^n \quad \qquad \forall n\in \mathbb {N}{\backslash }\{1,2,3\},\,\,n!>2^n \quad \qquad \forall n\in \mathbb {N},\,\,n>3\,\Rightarrow \, n!>2^n $$

the first one is preferable. The presence of the factorial makes it clear that we are dealing with natural numbers.

EXAMPLE. Using quantifiers, it is possible to define relational operators in terms of other operators, thereby reducing the number of primitive operators. The inclusion operator can be defined in terms of the membership operator:

$$\begin{aligned} A\subset B \quad \mathop {\Leftrightarrow }\limits ^\mathrm{def}\quad \forall x\in A,\quad x\in B. \end{aligned}$$

(4.19)

The divisibility operator is defined in terms of multiplication:

$$\begin{aligned} m\vert n \quad \mathop {\Leftrightarrow }\limits ^\mathrm{def}\quad \exists k\in \mathbb {Z},\,\,mk=n. \end{aligned}$$

(4.20)

EXAMPLE. The symbolic sentences (4.18) may be expressed in the language of functions:

(4.21)

These equivalences may give the impression that we have managed to bypass quantifiers altogether. This is not the case. The standard definition of image of a set under a function (2.18) has a hidden quantifier in it, which is revealed when the definition is converted to Zermelo form. Thus if $$\ f:\ A\rightarrow B$$ is a function, then

$$ f(A)=\{f(x)\,:\, x\in A\}=\{y\in B\,:\,\exists x\in A,\quad y=f(x)\}. $$

Of the two definitions, the first one is more intuitive.

Several quantifiers may appear within the same sentence. For illustration, let us consider the following two-variable predicate:

$$ {\fancyscript{L}}(x,y):=(\text {`x loves y'}). $$

This function is defined over the cartesian product $$G\times G$$, where $$G$$ is a set of people. So the lovers and the loved ones belong to the same set.

Now choose $$g\in G$$, say, $$g=$$ George. Then ’everybody loves George’ is a boolean expression, which is spelled out as

For all elements $$x$$ of $$G$$, the value of $${\fancyscript{L}}(x,g)$$ is TRUE.

This expression translates into symbols as follows:

$$ \forall x\in G,\quad {\fancyscript{L}}(x,g). $$

This sentence may be true or false (depending on how charming George is). The following sentences with one or two quantifiers exemplify several possible constructs.

In the sentences 4 and 5, the indeterminate $$x$$ belongs to the set $$G{\backslash }\{g\}$$, to ensure that $$x$$ is distinct from $$g$$. It is possible to transfer this constraint to the predicate, e.g., in item 4:

$$ \exists x\in G,\quad (x\ne g)\wedge {\fancyscript{L}}(g,x). $$

Two-quantifier sentences have implied parentheses, which establish the order of evaluation of the sub-expressions. Thus expression 6 is written in full as

$$ \forall x\in G,\quad (\exists y\in G,\quad {\fancyscript{L}}(x,y)). $$

According to (4.18), the quantity in parentheses must be equal to $$\fancyscript{Q}(x)$$ for some predicate $$\fancyscript{Q}$$ over $$G$$; indeed we see that $$\fancyscript{Q}(x)=$$$$x$$ loves somebody’. From the sentence’s symbolic structure and meaning, it is clear that the choice of $$y$$ depends on $$x$$, in general. Therefore, exchanging the order of the quantifiers alters the meaning of the expression, as confirmed by comparing sentences 6 and 9.

Quantifiers are operators which act on boolean functions, thereby producing new functions. Their effect is to reduce the number of variables by one, a process that calls to mind definite integration. We should think of the two expressions

$$ \forall x \in X \quad \qquad \int \nolimits _X{\mathrm {d}}x $$

as being structurally similar. The operator on the left acts on predicates over the set $$X$$, namely on functions $${\fancyscript{P}}:X\rightarrow \{{\textsc {t}},{\textsc {f}}\}$$. The operator on the right acts, say, on functions $$F:X\rightarrow \mathbb {R}$$, which are integrable over a subset $$X$$ of the real line. (To fix ideas, assume that $$X=[a,b]$$ is an interval.) Inserting the appropriate functions in each expression

$$ \forall x \in X,\,\,{\fancyscript{P}}(x) \quad \qquad \int \nolimits _X\mathrm {d}x\,F(x) $$

we obtain a boolean constant (TRUE or FALSE) on the left, and a numerical constant (a number) on the right. Now suppose that both $${\fancyscript{P}}$$ and $$F$$ are functions of two variables $$x$$ and $$y$$, defined over the cartesian product $$X\times Y$$ of two sets. Then each expression

$$ \forall x \in X,\,\,{\fancyscript{P}}(x,y) \quad \qquad \int \nolimits _X\mathrm {d}x\,F(x,y) $$

produces a function of $$y$$, the variable that is not quantified in one case, and not integrated over in the other. If we quantify/integrate with respect to both variables,

$$ \forall x \in X,\quad \exists y\in Y,\quad {\fancyscript{P}}(x,y) \quad \qquad \int \nolimits _X\mathrm {d}x\int \nolimits _Y\mathrm {d}y\,F(x,y), $$

once again we obtain constants.

Returning to the examples above, we note that $${\fancyscript{L}}(x,g)$$ is a predicate in one variable ($$g$$ is fixed), and so is $${\fancyscript{L}}(x,x)$$. Hence $$\exists x,\, {\fancyscript{L}}(x,g)$$ and $$\forall x,\, {\fancyscript{L}}(x,x)$$ are constants. On the other hand, any expression in which the number of quantifiers is smaller than the number of arguments in the predicate is a predicate with fewer arguments, as the following examples illustrate.

Now, each predicate is the characteristic function of a subset of $$G$$, which we construct with a Zermelo definition.

The sentence ’everybody loves somebody’ is of the form

$$\begin{aligned} \forall x\in X,\quad \exists y\in Y,\quad {\fancyscript{P}}(x,y) \end{aligned}$$

(4.22)

where $$X$$ and $$Y$$ are sets and $${\fancyscript{P}}$$ is a predicate over $$X\times Y$$. Letting $$X=Y=\mathbb {N}$$ and $${\fancyscript{P}}(x,y)=(x<y)$$, we obtain a new statement which has the same formal structure:

Given any integer, one can find a larger integer.

or better,

There is no greatest integer.

It’s useful to think of the interplay between universal and existential quantifiers as a representation of an adversarial system—like a court of law—based on the following rules of engagement:

The quantifiers create a tension between the two contenders, and I should expect to be challenged by my opponent. Accordingly, we rewrite our statement more emphatically:

Given any integer, no matter how large, one can always find a larger integer.

The expressions ’no matter how large’ and ’always’ are inessential to the claim, but they expose the dynamics of the process. This aspect of predicate calculus will be considered again in Chap. 7, when we deal with proofs.

EXAMPLE. The Archimedean property of the real numbers states that

The integer multiples of any positive quantity can be made arbitrarily large.

The symbolic version of this statement requires three quantifiers.

$$ \forall x\in \mathbb {R}^+,\quad \forall y\in \mathbb {R},\quad \exists n\in \mathbb {N},\quad nx>y. $$

In this expression $$x$$ is the positive quantity in question, $$y$$ is the (large) quantity we want to exceed, and $$n$$ is the multiple of $$x$$ needed to achieve this. Note that $$n=n(x,y)$$. Clearly, the Archimedean property is better expressed with words than with symbols, and the large number of quantifiers hidden within this sentence may be taken as an indication of the concept’s logical depth.

4.4.1 Quantifiers and Functions

Invariably, statements about functions will refer to the elements of the domain or co-domain, and quantifiers may be made to act on these elements. For instance, a function is injective if it maps distinct points to distinct points (Sect. 2.2). This concise statement unfolds as follows:

Given any two points in the domain of the function, if they are distinct, then so are their images under the function.

This sentence has a universal quantifier (’given any’) and an implication operator (’if $$\ldots $$ then’). Let $$f:A\rightarrow B$$. A literal translation into symbols is

$$ \forall x,y\in A,\quad (x\not =y)\Rightarrow (f(x)\not =f(y)) $$

where $$\forall x,y\in A$$ is a shorthand for $$\forall x\in A,\,\forall y\in A$$. Replacing the implication by its contrapositive [Theorem 4.1 (iv)] we obtain a neater expression:

$$ \forall x,y\in A,\quad (f(x)=f(y))\Rightarrow (x=y). $$

The original definition (’distinct points have distinct images’) restricts the ambient set to pairs of distinct points. This can be done symbolically:

$$ \forall x\in A,\quad \forall y\in A{\backslash }\{x\},\quad f(x)\not =f(y). $$

Now the predicate is simpler but the set is more complicated. It is always possible to transform an implication by absorbing the hypothesis into the ambient set (Exercise 4.10.3).

A function $$f$$ is surjective if image and co-domain coincide: $$f(A)=B$$. This high-level expression hides two quantifiers; we first spell it out:

Given any point in the co-domain, we can find a point in the domain which maps to it.

and then we rewrite it symbolically:

$$ \forall y\in B,\quad \exists x\in A, \quad f(x)=y. $$

This expression is of the form (4.22).

In Sect. 3.1 we noted that a sequence of elements of a set $$A$$ may be interpreted as a function:

$$ a:\mathbb {N}\rightarrow A \qquad k\mapsto a_k. $$

Characterising sequences is then analogous to characterising functions.

For example, consider the set $$\mathbb {Z}^\mathbb {N}$$ of all integer sequences (this notation was developed in Sect. 3.5.1). To isolate sequences with certain properties—a subset of $$\mathbb {Z}^\mathbb {N}$$—we use a Zermelo definition. For example, the set

$$ \{a\in \mathbb {Z}^\mathbb {N}\,:\,a_1\in 2\mathbb {Z}\} $$

consists of all integer sequences whose first term is even. By applying the quantifier $$\forall $$ to the subscript $$k$$ (which is the variable in our functions), we can deal with all terms of the sequences at once. So the set of integer sequences with only even terms is given by

$$\begin{aligned} \{a\in \mathbb {Z}^\mathbb {N}\,:\, \forall k\in \mathbb {N},\,\,a_k\in 2\mathbb {Z}\}=(2\mathbb {Z})^\mathbb {N}. \end{aligned}$$

(4.23)

There seems to be something wrong here. The quantifier ’integrates out’ the indeterminate $$k$$: does this mean that the predicate is just a constant? No, because the Zermelo variable is actually $$a=(a_k)$$, an element of the ambient set $$\mathbb {Z}^\mathbb {N}$$. If we write (4.23) as $$\{a\in \mathbb {Z}^\mathbb {N}\,:\,{\fancyscript{P}}(a)\}$$, then we see the structure of the predicate:

$$ {\fancyscript{P}}:\mathbb {Z}^\mathbb {N}\rightarrow \{{\textsc {t}},{\textsc {f}}\}\qquad a\mapsto (\forall k\in \mathbb {N},\,\,a_k\in 2\mathbb {Z}). $$

Likewise, the set

$$ \{a\in \mathbb {Z}^\mathbb {N}\,:\, \exists k\in \mathbb {N},\,\,a_k\in 2\mathbb {Z}\} $$

is

The set of integer sequences with an even term.

The above expression reflects the very literal interpretation of what’s written, which is what mathematicians—and lawyers—are notorious for. A mathematical geek would be entertained by the fact that the statement ’In London there is an underground station’, is true; a normal person would instead perceive this as a puzzling understatement (’Where do they go from there?’). So a characterisation of the type

The set of integer sequences with at least one even term.

is preferable to the one given before. The qualifier ’at least’ is superfluous, but helps the reader note an essential point.

The set

$$ \{a\in \mathbb {Z}^\mathbb {N}\,:\, \forall n\in \mathbb {N},\,\,n>2\Rightarrow 2|a_n\} $$

is described as

The set of integer sequences whose terms, after the second, are even.

No information is given about the first two terms, yet this statement could be misinterpreted as meaning that these terms are odd. A more eloquent description of this set is

The set of integer sequences whose terms are all even, with the possible exception of the first two terms.

These examples show how much can be done to improve the clarity of a definition; this will be our concern in Chap. 6.