Subsection 3.8.4 Multiple Quantifiers
If a proposition has more than one variable, then you can quantify it more than once. For example,
\(p(x, y):x^2 - y^2 = (x + y)(x - y)\) is a tautology over the set of all pairs of real numbers because it is true for each pair
\((x, y)\) in
\(\mathbb{R} \times \mathbb{R}\text{.}\) Another way to look at this proposition is as a proposition with two variables. The assertion that
\(p(x,y)\) is a tautology could be quantified as
\((\forall x)_{\mathbb{R}} ((\forall y) _{\mathbb{R}}(p(x, y)))\) or
\((\forall y)_{\mathbb{R}} ((\forall x) _{\mathbb{R}}(p(x, y)))\)
In general, multiple universal quantifiers can be arranged in any order without logically changing the meaning of the resulting proposition. The same is true for multiple existential quantifiers. For example,
\(p(x, y) : x + y = 4 \textrm{ and } x - y = 2\) is a proposition over
\(\mathbb{R} \times \mathbb{R}\text{.}\) \((\exists x)_{\mathbb{R}} ((\exists y) _{\mathbb{R}} (x + y = 4 \textrm{ and } x - y = 2))\) and
\((\exists y)_{\mathbb{R}}\textrm{ } ((\exists x) _{\mathbb{R}} (x + y = 4 \textrm{ and } x - y = 2))\) are equivalent. A proposition with multiple existential quantifiers such as this one says that there are simultaneous values for the quantified variables that make the proposition true. A similar example is
\(q(x, y) : 2x - y = 2 \textrm{ and }4x - 2y = 5\text{,}\) which is always false; and the following are all equivalent:
\begin{equation*}
\begin{split}
\neg ((\exists x)_{\mathbb{R}}((\exists y)_{\mathbb{R}}(q(x, y))))
& \Leftrightarrow \neg (\exists y)_{\mathbb{R}}((\exists x)_{\mathbb{R}}(q(x, y))) \\
& \Leftrightarrow (\forall y)_{\mathbb{R}} (\neg ((\exists x)_{\mathbb{R}}(q(x,y)))) \\
& \Leftrightarrow ((\forall y)_{\mathbb{R}} ((\forall x)_{\mathbb{R}} (\neg q(x, y))))\\
& \Leftrightarrow ((\forall x)_{\mathbb{R}} ((\forall y)_{\mathbb{R}} (\neg q(x, y))))
\end{split}
\end{equation*}
When existential and universal quantifiers are mixed, the order cannot be exchanged without possibly changing the meaning of the proposition. For example, let
\(\mathbb{R}^+\) be the positive real numbers,
\(x : (\forall a)_{\mathbb{R}^+} ((\exists b)_{\mathbb{R}^+} (a b = 1))\) and
\(y : (\exists b)_{\mathbb{R}^+} ((\forall a)_{\mathbb{R}^+}(a b = 1))\) have different logical values;
\(x\) is true, while
\(y\) is false.
Tips on Reading Multiply-Quantified Propositions. It is understandable that you would find propositions such as
\(x\) difficult to read. The trick to deciphering these expressions is to “peel” one quantifier off the proposition just as you would peel off the layers of an onion (but quantifiers shouldn’t make you cry!). Since the outermost quantifier in
\(x\) is universal,
\(x\) says that
\(z(a) : (\exists b)_{\mathbb{R}^+}(a b = 1)\) is true for each value that
\(a\) can take on. Now take the time to select a value for
\(a\text{,}\) like 6. For the value that we selected, we get
\(z(6) : (\exists b)_{\mathbb{R}^+}(6b = 1)\text{,}\) which is obviously true since
\(6b = 1\) has a solution in the positive real numbers. We will get that same truth value no matter which positive real number we choose for
\(a\text{;}\) therefore,
\(z(a)\) is a tautology over
\(\mathbb{R}^+\) and we are justified in saying that
\(x\) is true. The key to understanding propositions like
\(x\) on your own is to experiment with actual values for the outermost variables as we did above.
Now consider
\(y\text{.}\) To see that
\(y\) is false, we peel off the outer quantifier. Since it is an existential quantifier, all that
\(y\) says is that some positive real number makes
\(w(b)\) :
\((\forall a) _{\mathbb{R}^+} (a b = 1)\) true. Choose a few values of
\(b\) to see if you can find one that makes
\(w(b)\) true. For example, if we pick
\(b = 2\text{,}\) we get
\((\forall a) _{\mathbb{R}^+}(2a = 1)\text{,}\) which is false, since
\(2a\) is almost always different from 1. You should be able to convince yourself that no value of
\(b\) will make
\(w(b)\) true. Therefore,
\(y\) is false.
Another way of convincing yourself that \(y\) is false is to convince yourself that \(\neg y\) is true:
\begin{equation*}
\begin{split}
\neg ((\exists b)_{\mathbb{R}^+} ((\forall a)_{\mathbb{R}^+}(a b = 1)))
&\Leftrightarrow (\forall b)_{\mathbb{R}^+}\neg ((\forall a)_{\mathbb{R}^+}(a b = 1))\\
& \Leftrightarrow (\forall b)_{\mathbb{R}^+} ((\exists a)_{\mathbb{R}^+}(a b \neq 1))
\end{split}
\end{equation*}
In words, for each value of \(b\text{,}\) there is a value for \(a\) that makes \(a b \neq 1\text{.}\) One such value is \(a=\frac{1}{b}+1\text{.}\) Therefore, \(\neg y\) is true.
One final example that serves as a preview to how quantifiers appear in calculus.
Example 3.8.9. The Limit of a Sequence.
What does it mean that 0.999… = 1? The ellipsis (\(\dots\)) implies that there are an infinite number of 9’s on the left of the equals sign. Any way to try to justify this equality boils down to the idea of limits. After many years of struggling with what this means, mathematicians have come up with a universally accepted interpretation involving quantifiers. It is that
\begin{equation*}
(\forall \epsilon)_{\mathbb{R}^+} ((\exists N)_{\mathbb{P}})(n\geq N \Rightarrow |1- 0.\underbrace{99..9}_{n\,9’s}| \lt \epsilon))
\end{equation*}
In calculus, the symbol \(\epsilon\) is usually reserved for small positive real numbers. Let’s pick a value for \(\epsilon\) and peel the universal quantifier off the statement above. Let’s try \(\epsilon\) equal to \(\frac{1}{2^{10}}=\frac{1}{1024}\text{.}\) In addition we note that \(0.\underbrace{99..9}_{n\,9’s}=1-\frac{1}{10^n}\text{.}\) With our choice of \(\epsilon\) we get
\begin{equation*}
(\exists N)_{\mathbb{P}}(n\geq N \Rightarrow |1- 0.\underbrace{99..9}_{n\,9’s}| \lt \frac{1}{1024})
\end{equation*}
or
\begin{equation*}
(\exists N)_{\mathbb{P}}(n\geq N \Rightarrow \frac{1}{10^n} \lt \frac{1}{1024})
\end{equation*}
This last statement is true - one value of \(N\) that would work is \(11\text{.}\) You just have to convince yourself that any positive value of \(\epsilon\text{,}\) no matter how small, will produce a true statement. If you see that, you’ve convinced yourself that \(0.999\dots = 1\text{!}\)
