Multiple Quantifiers

Consider the universe $N$ of all integers, along with the open statement

\[ \begin{array}{rl} p(m, n)\text{: } &m + n = 0. \end{array} \]

What happens when we quantify the $m$ variable? With the universal quantifier, we get $\forall m\ [p(m, n)]$, which translates to “For every integer $m$, we have that $m + n = 0$.” Is this true? We’d need to know what value $n$ holds to be sure — we can’t just pick any value of $n$. The statement would be false when $m = 1$ and $n = 2$. We just can’t be sure, so $\forall m\ [p(m, n)]$ doesn’t have a definite truth value.

Now consider the statement $\exists m\ [p(m, n)]$, which translates to “There exists an integer $m$ such that $m + n = 0$.” Again, until a value for $n$ is known, we can’t be sure — though we could figure out what value $n$ would need to be in order for $m + n = 0$ to hold. For example, when $m = 5$, we could set $n = -5$. But the value of $n$ is still unknown, so the statement $\exists m\ [p(m, n)]$ is open, and has no definite truth value.

A basic law of arithmetic is the commutative law — in a sum or product, the two constituent parts can be swapped without affecting the result. In other words, for any two real numbers $x$ and $y$,

$$x + y = y + x.$$

Consider the universe $\mathcal{U}$ of all real numbers. We can express the commutative laws of arithmetic using quantifiers like this:

$$\forall x\ \forall y\ [x + y = y + x] \qquad \forall x\ \forall y\ [x \cdot y = y \cdot x].$$

The order of the quantified variables doesn’t matter, so we could also express the commutative laws of arithmetic like this:

$$\forall y\ \forall x\ [x + y = y + x] \qquad \forall y\ \forall x\ [x \cdot y = y \cdot x].$$

Consider the universe $N$ consisting of all integers, along with the statement

$$\text{The integer 100 is the sum of two perfect squares.}$$

The presence of the definite article “the” suggests that the existential quantifier is implied here. As such, we could express the statement using quantifiers like this:

$$\exists m\ \exists n\ [100 = m^2 + n^2].$$

Again, the order of quantification doesn’t matter in this case, so we could also write $\exists n\ \exists m\ [100 = m^2 + n^2]$.

One more way to write this is to specify which universe each variable belongs to using the $\in$ symbol:

$$\exists m \in N\ \exists n \in N\ [100 = m^2 + n^2].$$

Consider the universe of all real numbers, which we’ll denote $R$. When dealing with real numbers, another commonly used arithmetic law is the distribution of multiplication over addition, typically expressed as “For every real number $x$, $y$, and $z$, $x(y + z) = xy + xz$.”

Here, the quantifier being used is the universal quantifier, applied to every variable, so we can concisely represent this statement with the proposition

$$\forall x\ \forall y\ \forall z\ [x(y + z) = xy + xz].$$

Using the shorthand notation above, we could also write this as

$$\forall x, y, z\ [x(y + z) = xy + xz].$$

Consider the universe of all real numbers. It’s known that every number has an additive inverse:

$$\text{For every real number } x \text{, there exists some other number } y \text{ where } x + y = 0.$$

Notice that we used the phrases “For every…” and “There exists…,” which suggests both a universal quantifier and an existential quantifier. The phrase “For every…” comes first, suggesting it’s the first quantifier, with the existential quantifier coming second. As such, we can rewrite the statement above as

$$\forall x\ \exists y\ [x + y = 0].$$

Since $x$ is universally quantified, we can pick arbitrary values to test. If $x = 3008$, then $y = -3008$ will work. Similarly, taking $x = -\pi^2$, we can set $y = \pi^2$. In fact, as soon as a value of $x$ is selected, we can just take $y = -x$, since $x$ being a real number means $-x$ is too. So no matter what real number we pick for $x$, we can always find an appropriate value for $y$.

Let’s reconsider the additive inverse example. Suppose we swapped quantifiers, like we did when examining repeated quantifiers. Doing so forms the statement

$$\exists y\ \forall x\ [x + y = 0].$$

This can be translated into English as “There exists some real number $y$, such that for every real number $x$, we have $x + y = 0$.” Here, the proposition asserts the existence of some such real number — and supposedly, once it’s found, every real number added to it yields a sum of $0$.

We know $y$ can’t be $17$, because $3 + 17 \neq 0$ (here, $y = 17$ and $x = 3$). Similarly, $y$ can’t be $-0.745$, because $20 - 0.745 \neq 0$ (here, $y = -0.745$ and $x = 20$).

As a matter of fact, no such value of $y$ can exist. As soon as we pick a value for $y$, there are infinitely many ways to pick the value of $x$ — and since $x$ is universally quantified, the statement asserts that every value of $x$ will work, which so far isn’t the case. Out of those infinitely many sums, only one will be $0$: when $x$ is equal to $-y$. Since $x$ is universally quantified, we could also pick the real number $-y + 1$, which yields a sum of $1$, not $0$.

Surprisingly, if this statement were true, every single real number would need to be equal to $0$ — an obviously ridiculous scenario!

Suppose we have a universe $\mathcal{U}$, and open statements $a(x, y)$, $b(x, y)$, and $c(x, y)$ defined on that universe. We want to negate the statement

$$\exists x\ \forall y\ [a(x, y) \land b(x, y) \to c(x, y)].$$

Before we start, we make the following shorthand substitutions to keep things tidy:

$$a(x, y): a \qquad b(x, y): b \qquad c(x, y): c$$

giving us $\exists x\ \forall y\ [(a \land b) \to c]$. Now we perform the negation:

\[ \begin{array}{lll} & \boldsymbol{\neg \exists x\ \forall y\ [(a \land b) \to c]} & \textbf{Reason} \\ \Longleftrightarrow & \forall x\ \exists y\ [\neg[(a \land b) \to c]] & \neg \exists x\ \forall y\ [p(x, y)] \Longleftrightarrow \forall x\ \exists y\ [\neg p(x, y)] \\ \Longleftrightarrow & \forall x\ \exists y\ [\neg[\neg(a \land b) \lor c]] & p \to q \Longleftrightarrow \neg p \lor q \\ \Longleftrightarrow & \forall x\ \exists y\ [\neg \neg (a \land b) \land \neg c] & \text{DeMorgan's Law} \\ \Longleftrightarrow & \forall x\ \exists y\ [(a \land b) \land \neg c] & \text{Law of Double Negation} \\ \Longleftrightarrow & \forall x\ \exists y\ [a \land b \land \neg c] & \text{Associative Law of } \land \end{array} \]

Substituting $a(x, y)$, $b(x, y)$, and $c(x, y)$ back in for $a$, $b$, and $c$ respectively, we find that the negation of

$$\exists x\ \forall y\ [a(x, y) \land b(x, y) \to c(x, y)]$$

is the statement

$$\forall x\ \exists y\ [a(x, y) \land b(x, y) \land \neg c(x, y)].$$