3.4: Quantifiers

Let \(P(x)\) be a formula in one variable. If we substitute a constant, \(a \in U\), for \(x\) we arrive at a statement \(P(a)\). However, suppose that we are interested in \(P(x)\) with regard to some set \(X \subseteq U\), rather than a particular element of \(U\). In particular, we ask if \(P(a)\) is a true statement for all \(a \in X\). Recall that one of the roles of a formula is to define sets. For any formula \(P(x)\), universe \(U\) and \(X \subseteq U, P(x)\) partitions \(X\) into two sets - those elements of \(X\) for which \(P\) is true, and those for which \(P\) is false. In this sense, asking whether \(P\) holds for all \(x \in X\), or whether it holds for some \(x \in X\) (which is complementary to asking whether \(\neg P\) holds for all \(x \in X)\) is asking whether \(P\) defines a new or interesting subset of \(X\).

Just as propositional connectives were introduced to formalize the linguistic behavior of certain widely employed natural language connectives (and, or, implies, not), we shall also formalize "quantification" over sets.

Definition. Universal quantifier, \((\forall x \in X) P(x)\) Let \(P(x)\) be a formula in one variable, with universe \(U\). Let \(X \subseteq U\). Let \(Q\) be the statement \[(\forall x \in X) P(x)\] Then \(Q\) is true if for every \(a \in X, P(a)\) is true. Otherwise \(Q\) is false.

The notation \[(\forall x \in X) P(x)\] is a shorthand for \[(\forall x)([x \in X] \Rightarrow[P(x)])\] The statement " \((\forall x \in X) P(x) "\) is read "for all \(x\) in \(X, P(x) "\). We have \[(\forall x \in X) P(x) \Longleftrightarrow X \subseteq \chi_{P}\] DefinITION. Existential quantifier, \((\exists x \in X) P(x)\) Let \(P(x)\) be a formula in one variable with universe \(U .\) Let \(X \subseteq U, X \neq \emptyset\). Let \(Q\) be the statement \[(\exists x \in X) P(x) .\] Then \(Q\) is true if there is some \(a \in X\), for which \(P(a)\) is true. Otherwise \(Q\) is false.

The expression \[(\exists x \in X) P(x)\] is a shorthand for \[(\exists x)[(x \in X) \wedge P(x)] \text {. }\] The statement " \((\exists x \in X) P(x)\) " is read "there exists \(x\) in \(X\), such that \(P(x)\) ". The quantifier " \(\nabla\) " is the formal equivalent of the natural language expression "for all" or "every". The quantifier " \(\exists\) " is the formal equivalent of "for some" or "there exists ... such that ...".

Provided that the universe of a variable is clear, or not relevant to the discussion, it is common to suppress the universe in the expression of the statement. For instance, if \(P(x)\) is a formula with universe \(U\), we may write \[(\forall x) P(x)\] instead of \[(\forall x \in U) P(x) .\]

3.4.1. Multiple Quantifiers.

Let \(P\left(x_{1}, \ldots, x_{n}\right)\) be a formula in \(n \geq 2\) variables. Then the formula \[\left(\forall x_{1}\right) P\left(x_{1}, \ldots, x_{n}\right)\] is a formula in the \(n-1\) variables \(x_{2}, \ldots, x_{n}\). Similarly, the formula \[\left(\exists x_{1}\right) P\left(x_{1}, \ldots, x_{n}\right)\] is a formula in \(n-1\) variables.

EXAMPLE 3.10. Consider the formula in five variables \[P\left(x, x_{0}, L, \varepsilon, \delta\right):=\left(0<\left|x-x_{0}\right|<\delta\right) \Rightarrow(|\sin (x)-L|<\varepsilon)\] with all variables having universe \(\mathbb{R}\). Then \(\left(\forall x_{0}\right) P\left(x, x_{0}, L, \varepsilon, \delta\right)\) is a formula in four variables, \(\left(\forall x_{0}\right)(\exists L) P\left(x, x_{0}, L, \varepsilon, \delta\right)\) is a formula in three variables, and \[\left(\forall x_{0}\right)(\exists L)(\forall \varepsilon) P\left(x, x_{0}, L, \varepsilon, \delta\right)\] is a formula in two variables.

Definition. Open variable, Bound variable In the formula \(P(x)\), \(x\) is an open variable. In the formulas \[(\forall x) P(x), \quad(\exists x) P(x), \quad(\forall x) Q(x, y), \quad(\exists x) Q(x, y)\] \(x\) is a bound or quantified variable, and in the last two, \(y\) is an open variable.

3.4.2. Quantifier Order.

In the discussion below, we need to discuss quantifiers generically, that is without regard to whether the quantifier under discussion is universal or existential. So we shall introduce some convenient notation just for this section.

Notation. \((\mathcal{Q} x) P(x)\) We use the notation \[\text { (Q } \mathcal{Q} x) P(x)\] to generically represent \[(\forall x) P(x)\] and \[(\exists x) P(x) \text {. }\] Let \(\mathcal{Q}_{1}, \ldots, \mathcal{Q}_{n}\) be logical quantifiers and \(P\left(x_{1}, \ldots, x_{n}\right)\) be a formula with open variables \(x_{1}, \ldots, x_{n}\). Then \[\left(\mathcal{Q}_{1} x_{1}\right)\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] is a statement.

EXAMPLE 3.11. Consider a statement \(S\) in the form \[S=(\forall x \in X)(\exists y \in Y) P(x, y) .\] \(S\) is true if for each \(a \in X\), \[(\exists y \in Y) P(a, y)\] is true. This is satisfied provided that for each \(a \in X\), there is an element of \(Y\) (let’s call it \(b_{a}\) to remind us that this particular element of \(Y\) is associated with the previous choice, a) such that \[P\left(a, b_{a}\right)\] is true. So \(b_{a}\) is selected with \(a\) in mind. Statements in this form are especially important in mathematics because the definition of the limit in calculus is a statement in the form of this example.

Let’s return to the statement \[\left(\mathcal{Q}_{1} x_{1}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] The order of the quantifiers is significant. If \(1 \leq i<j \leq n, x_{i}\) behaves like a parameter from the point of view of \(x_{j}\) (that is, \(x_{i}\) is fixed from the point of view of \(x_{j}\) ). Put another way, \(x_{j}\) is chosen with respect to the substitutions of \(x_{1}, \ldots, x_{j-1}\), but without consideration for \(x_{j+1}, \ldots, x_{n}\).

One always reads from the left. The statement \[\left(\forall x_{1}\right)\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] is the same as \[\left(\forall x_{1}\right)\left[\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\right] \text {, }\] or, in other words, for every choice of \(x_{1}\), the statement \[\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] is true. Similarly, the statement \[\left(\exists x_{1}\right)\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] is the same as \[\left(\exists x_{1}\right)\left[\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\right] \text {, }\] or in other words that there is some choice of \(x_{1}\) for which the statement \[\left(\mathcal{Q}_{2} x_{2}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)\] about the \(n-1\) variables \(x_{2}, \ldots, x_{n}\) is true.

EXAMPLE 3.12. Order of quantifiers is important, as you can see from the following: \[(\forall x \in X)(\exists y \in Y) P(x, y)\] is not equivalent to \[(\exists y \in Y)(\forall x \in X) P(x, y) .\] For instance, the statement \[(\forall x \in \mathbb{R})(\exists y \in \mathbb{R})\left(y=x^{2}\right)\] is true. But \[(\exists y \in \mathbb{R})(\forall x \in \mathbb{R})\left(y=x^{2}\right)\] is false. The statement \[[(\exists y \in Y)(\forall x \in X) P(x, y)] \Rightarrow[(\forall x \in X)(\exists y \in Y) P(x, y)]\] is true. The converse clearly fails.

3.4.3. Negation of Quantifiers.

In an important sense, \(\wedge\) and \(\vee\) are complementary. By de Morgan’s identities (3.3) and (3.4), the negation of a simple conjunction is a disjunction of negations. Similarly, the negation of a simple disjunction is a conjunction of negations. Universal and existential quantifiers are also complementary. We observe that \[[\neg(\forall x) P(x)] \equiv[(\exists x) \neg P(x)]\] for any formula, \(P(x)\). Similarly \[[\neg(\exists x) P(x)] \equiv[(\forall x) \neg P(x)] .\] Of course, \(P(x)\) itself may be a formula which has numerous quantifiers and bound variables. Let’s suppose that \[P(x)=(\exists y) Q(x, y) .\] Then the following statements are equivalent (for any choice of \(P\) and \(Q\) satisfying the identity (3.13)): \[\begin{gathered} \neg(\forall x) P(x) \\ (\exists x) \neg P(x) \\ \neg(\forall x)(\exists y) Q(x, y) \\ (\exists x) \neg(\exists y) Q(x, y) \\ (\exists x)(\forall y) \neg Q(x, y) . \end{gathered}\] This example suggests that it is permissible to permute a negation and a quantifier by changing the type of quantifier, and indeed this is so.

Let \(\mathcal{Q}_{i}\) be a quantifier, for \(1 \leq i \leq n\). For each \(\mathcal{Q}_{i}\), let \(\mathcal{Q}_{i}^{*}\) be the complementary quantifier. That is, if \(\mathcal{Q}_{i}=\forall\), then let \(\mathcal{Q}_{i}^{*}=\exists\); if \(\mathcal{Q}_{i}=\exists\), then let \(\mathcal{Q}_{i}^{*}=\forall\). Then, \[\neg\left(\mathcal{Q}_{1} x_{1}\right)(\ldots)\left(\mathcal{Q}_{n} x_{n}\right) P(\bar{x}) \equiv\left(\mathcal{Q}_{1}^{*} x_{1}\right)(\ldots)\left(\mathcal{Q}_{n}^{*} x_{n}\right) \neg P(\bar{x}) .\]