Skip to main content

Section 1.12 Quantifiers

Sometimes a statement tells us about a number of things satisfying a certain property. For example, consider the two statements “\(x^2=4\)” and “there is an integer \(x\) so that \(x^2=4\text{.}\)” The first statement asserts some condition about a particular \(x\text{,}\) whereas the second statement says there is at least one \(x\) satisfying this condition. Words like “there is,” “there exists,” and “for some” are called existential quantifiers, and we write \(\exists\) for short. So the statement

“there is a natural number \(n\) such that \(n^2=4\)”
can be written more succinctly as

\begin{equation*} (\exists x\in\NN_0)(x^2=4)\text{.} \end{equation*}

(Some authors will write this a little more informally, as “\(\exists x \in \NN_0 \text{ st } x^2 = 4\text{,}\)” where the “st” is shorthand for “such that.” )

To prove an existentially quantified sentence \((\exists x\in S)(\phi(x))\text{,}\) you generally have to construct or find an \(x\in S\) for which \(\phi(x)\) holds.

To prove the statement \((\exists n\in\NN_0)(x^2=4)\text{,}\) we have to construct an \(n \in \NN_0\) whose square is \(4\text{.}\) But this is not too hard: \(n = 2\) has this property.

Note that this sentence didn't say anything about the question of whether \(n=2\) is the only natural that satisfies this condition.

If \(S\) is a set, and \(\phi(x)\) is a statement with free variable \(x\text{,}\) then the sentence \((\exists x \in S)(\phi(x))\) is equivalent to the sentence

\begin{equation*} \{x \in S : \phi(x)\} \neq \varnothing\text{.} \end{equation*}

Some statements assert that every \(x \in S\) satisfies some condition. Terms like “for every” and “for all” are called universal quantifiers. Symbolically, we just write \(\forall\) to mean any one of these. So the statement

“every positive natural number is less than or equal to its square”
can be written

\begin{equation*} (\forall n\in\NN)(n\leq n^2)\text{.} \end{equation*}

To prove a universally quantified sentence \((\forall x \in S)(\phi(x))\text{,}\) you generally have to contemplate an arbitrary element \(x\) of \(S\) and to prove that \(\phi(x)\) holds for it.

To prove the statement \((\forall n \in \NN)(n \leq n^2)\text{,}\) we start with the word “let.” Let \(n \in \NN\text{.}\) Then \(n-1\in \NN_0\text{.}\) Thus \(n^2-n = n(n-1) \geq 0\text{.}\) Consequently, \(n^2 \geq n\text{,}\) as desired.

Most mathematical statements involve many quantifiers at once. For example, the statement that “every positive real number is the square of some negative real number” has two quantifiers. To write it, let \(P\) be the set of positive real numbers, and let \(N\) be the set of negative real numbers. (We haven't actually defined these sets yet, but we'll get to that!) Now our sentence can be written:

\begin{equation*} (\forall x \in P)(\exists y \in N)(y^2 = x)\text{.} \end{equation*}

Let's define the successor to a natural number \(n\) as the smallest natural number that is larger than \(n\text{.}\) Let's consider the sentence “every natural number has a successor.”

Let's unpack this sentence in stages. First, we have

\begin{equation*} (\forall n \in \NN)(\text{ there is a natural number \(k\) such that \(k\) is a successor to \(n\) } )\text{.} \end{equation*}

What we have there in parentheses can itself be unpacked; now our sentence is

\begin{equation*} (\forall n \in \NN)(\exists k \in \NN)(\text{ \(k\) is a successor to \(n\) } )\text{.} \end{equation*}

Going even farther, this becomes

\begin{equation*} (\forall n \in \NN)(\exists k \in \NN)(\forall m \in \NN)((m>n) \implies (n\lt k\leq m))\text{.} \end{equation*}

This is about as unpacked as you can get.

The advantage of unpacking sentences like this is that you can now prove this claim by following the order of the quantifiers, from left to right:

  1. The first quantifier is universal, so the first sentence of our proof has to be: “Let \(n \in \NN\text{.}\)”

  2. The second quantifier is existential, so we have to specify or construct the successor \(k\text{.}\) We are free to use \(n\) in our definition of \(k\) (in this case we'll have to), and our \(k\) will be defined so that the condition that “for any natural number \(m>n\text{,}\) one has \(n\lt k\leq m\)” holds.

  3. Finally, we have to prove that condition, which is our third quantifier, which is universal. So that means we have to begin this portion of the proof with the words: “Let \(m \in \NN\text{.}\)”

Follow that recipe to write a proof of this statement.

Solution.

Let \(n \in \NN\text{.}\) We aim to construct a successor \(k\text{;}\) so define \(k\) as \(n+1\text{.}\) Now we aim to prove that the condition holds. So let \(m \in \NN\text{.}\) Assume \(m > n\text{.}\) Thus \(m - n\) is an integer and \(m-n>0\text{.}\) That implies that \(m-n\geq 1\text{.}\) Thus \(m \geq n+1=k\text{.}\) Also, \(n\lt n+1=k\text{,}\) so we deduce that \(n\lt k \leq m\text{,}\) just as we wanted.

It's a good idea to reflect on what happened here. Often, the hardest part about proving a statement is getting precise control over what the statement actually is. In particular, it should always be possible for you to convert a mathematical statement into a series of \(\forall\)'s and \(\exists\)'s with logical connectives relating simple statements. Doing this in the right order, and manipulating the resulting expressions carefully, is at the heart of doing pure mathematics.

Let \(\phi(x)\) be a statement with free variable \(x\text{.}\) The phrase there is a unique \(x\) such that \(\phi(x)\) — sometimes written \((\exists ! x)(\phi(x))\) — is a helpful shorthand for the longer sentence

\begin{equation*} (\exists x)(\phi(x)) \wedge ((\forall y)(\forall z)((\phi(y)\wedge \phi(z))\implies(y=z)))\text{.} \end{equation*}

Notice that this is the conjunction of two sentences: the first says that there exists an \(x\) with the property \(\phi\text{.}\) The second sentence says that if \(y\) and \(z\) each have property \(\phi\text{,}\) then they are equal. Thus the first part of the sentence says that there is at least one \(x\) with the property \(\phi\text{,}\) and the second part says that there is at most one \(x\) with property \(\phi\text{.}\)

How do we negate a statement with a quantifier? Consider the statement “every person in this room has blue eyes.” What would it take for this statement to be false? You need at least one person in the room to not have blue eyes, and you're in business! That is, the statement “there is some person in this room who does not have blue eyes” is the negation of the statement “every person in this room has blue eyes.” Note that the original statement has the universal quantifier “every” and its negation has the existential quantifier “there is some,” and the last part of the sentence “has blue eyes” become “does not have blue eyes.”

So to negate a statement with a quantifier, we can “push” the negation past the quantifier, and as we do, \(\forall\) turns into \(\exists\text{,}\) and \(\exists\) turns into a \(\forall\text{.}\) It's maybe a little easier to see this if we use the \(\neg\) notation for negation. Thus,

\begin{equation*} \neg(\forall x \in S)(\phi(x)) \iff (\exists x \in S)(\neg \phi(x))\text{.} \end{equation*}

Similarly,

\begin{equation*} \neg(\exists x \in S)(\phi(x)) \iff (\forall x \in S)(\neg \phi(x))\text{.} \end{equation*}

Consider the statement

\begin{equation*} (\forall n \in \NN)(\exists m \in \NN)(m^2 = n)\text{.} \end{equation*}

This statement isn't true, so let's write down its negation.

\begin{equation*} \neg(\forall n\in\NN)(\exists m\in\NN)(m^2=n) \end{equation*}
\begin{equation*} \Updownarrow \end{equation*}
\begin{equation*} (\exists n\in\NN)(\neg(\exists m\in\NN)(m^2=n)) \end{equation*}
\begin{equation*} \Updownarrow \end{equation*}
\begin{equation*} (\exists n\in\NN)(\forall m\in\NN)\neg(m^2=n) \end{equation*}
\begin{equation*} \Updownarrow \end{equation*}
\begin{equation*} (\exists n\in\NN)(\forall m\in\NN)(m^2\neq n)\text{.} \end{equation*}

The reason it's important to be able to do this is that if our aim is to disprove the sentence \((\forall n \in \NN)(\exists m \in \NN)(m^2 = n)\text{,}\) then this unpacking shows us what we need to do. We have to specify or construct a natural number \(n\text{;}\) let's take \(n=2\text{.}\) Then we have to show that for every natural number \(m\text{,}\) it is not the case that \(m^2 = n\text{.}\) In this case, we can note that \(1^2 = 1 \lt 2\text{,}\) and for any natural number \(m \geq 2\text{,}\) we have \(m^2 > 2^2 = 4 > 2\text{.}\)

All this work to negate quantifiers! Do we need to show the above individual steps when negating in our homework? No! Don't worry, in your homework you won't be expected to give the full justification of why the negation of some statement is what it is. But, especially for complicated statements, it's important to get keep this straight!