Proofs With Multiple Quantifiers

Read Each Quantifier in Order

In the previous tutorial, set proofs began by taking an arbitrary element and translating membership into a logical condition. Statements with multiple quantifiers use the same discipline, but require careful attention to the order of the choices. A statement that says “for every $x$, there is a $y$” may allow the choice of $y$ to depend on $x$. A statement that says “there is a $y$ such that for every $x$” requires one fixed $y$ to work for all $x$.

The order can determine whether a claim is true. To prove a universal statement, start with an arbitrary object from its domain and establish the required conclusion. To prove an existential statement, provide a particular witness and check that it satisfies the condition. When the two kinds of quantifier occur together, use these steps in their stated order.

Definition. Let $A$ be a set and let $P(x,y)$ be a condition on elements $x,y\in A$. The statement $\forall x\in A\,\exists y\in A\,P(x,y)$ means that for every $x\in A$, there is at least one $y\in A$ for which $P(x,y)$ holds. The statement $\exists y\in A\,\forall x\in A\,P(x,y)$ means that there is one $y\in A$ for which $P(x,y)$ holds for every $x\in A$.

The domains matter: an existential witness must belong to the stated set, and a universal claim covers every element of its stated set. It is often useful to say the domains aloud before beginning a proof. For example, $\forall n\in\mathbb{N}\,\exists m\in\mathbb{N}\,P(n,m)$ asks us first to take an arbitrary natural number $n$, and then to find a natural number $m$, possibly chosen using $n$.

Worked Example: A Witness Chosen for Each Input

We prove that for every positive integer $n$, there is an even positive integer greater than $n$. Let $n$ be an arbitrary positive integer. Choose $m=2n$. Because $n$ is an integer, $m$ is an integer, and $m$ is even since $m=2n$. Also $m$ is positive because $n>0$, and

$$ m-n=2n-n=n>0. $$

Thus $m>n$, so this choice of $m$ has all the required properties. Since the argument works for every positive integer $n$, the original statement holds. The witness $m=2n$ is selected after $n$ is given; its value depends on $n$.

Quantifier Order Can Change the Claim

A reliable way to understand a quantified statement is to describe the choices it permits. In $\forall x\,\exists y\,P(x,y)$, the proof begins with an arbitrary $x$; it may then choose a suitable $y$ for that $x$. In $\exists y\,\forall x\,P(x,y)$, a single $y$ must be chosen before considering all the $x$'s. The latter requirement is generally stronger.

Theorem (A Universal-Existential Statement Need Not Reverse). For integers, $\forall n\in\mathbb{Z}\,\exists m\in\mathbb{Z}\,(m>n)$ is true, whereas $\exists m\in\mathbb{Z}\,\forall n\in\mathbb{Z}\,(m>n)$ is false.

Proof. For the first statement, let $n\in\mathbb{Z}$ be arbitrary and choose $m=n+1$. Since $n$ is an integer, $m$ is an integer, and $m-n=(n+1)-n=1>0$. Hence $m>n$. This proves the statement for every integer $n$.

For the second statement, suppose there were an integer $m$ such that $m>n$ for every integer $n$. In particular, the condition would have to hold for $n=m$. It would then assert $m>m$, which is false because $m-m=0$, not a positive number. Thus no such $m$ exists. The two statements differ because the first permits a new witness for each input, while the second demands one integer larger than every integer. $\square$

Worked Example: Negating a Statement with Two Quantifiers

Consider the statement $S$: “For every real number $x$, there is a real number $y$ such that $x+y=0$.” To negate it, the universal claim must fail for at least one $x$; for that $x$, there must be no $y$ satisfying the equation. The result is

\neg S \quad\Longleftrightarrow\quad \exists x\in\mathbb{R}\,\forall y\in\mathbb{R},\ x+y\ne 0.

In fact, $S$ is true: for an arbitrary real $x$, choose $y=-x$. Then $y\in\mathbb{R}$ and $x+y=x+(-x)=0$. Its negation is false. To check this directly, suppose an $x\in\mathbb{R}$ were a witness to the negation. The real number $y=-x$ would then satisfy $x+y=0$, contradicting the requirement that $x+y\ne 0$ for every real $y$.

This example also shows why negation does not simply mean “change the equation.” It changes each quantifier: “for every” becomes “there is,” and “there is” becomes “for every.” The condition itself is negated as well.

Theorem (Negation of Quantified Statements). For a condition $P(x)$ on a set $A$, $$ \neg(\forall x\in A\,P(x)) \Longleftrightarrow \exists x\in A\,\neg P(x), \qquad \neg(\exists x\in A\,P(x)) \Longleftrightarrow \forall x\in A\,\neg P(x). $$

Proof. The statement $\forall x\in A\,P(x)$ says that every element of $A$ satisfies $P$. Its negation says that this is not the case: at least one element of $A$ fails to satisfy $P$. That is exactly the meaning of $\exists x\in A\,\neg P(x)$, proving the first equivalence.

The statement $\exists x\in A\,P(x)$ says that at least one element of $A$ satisfies $P$. Its negation says that no element of $A$ satisfies $P$, which means that every element of $A$ fails to satisfy $P$. This is exactly $\forall x\in A\,\neg P(x)$, proving the second equivalence. These arguments also apply when $A$ is empty: there is no element witnessing an existential claim, and every element of the empty set satisfies any universal claim vacuously. $\square$

For a statement with two quantifiers, apply these equivalences one quantifier at a time. For instance, the negation of $\forall x\in A\,\exists y\in B\,P(x,y)$ is $\exists x\in A\,\forall y\in B\,\neg P(x,y)$. The first quantifier changes from universal to existential; the second changes from existential to universal; and $P$ is replaced by its negation.

Existence and Uniqueness Use Different Tasks

An existence claim asks for at least one object satisfying a condition. A uniqueness claim asks that no two distinct objects satisfy it. When a theorem says that an object exists and is unique, its proof has two parts: first produce a witness, then show that any two possible witnesses must be equal. Keeping the parts separate helps ensure that an existence proof is not mistaken for a uniqueness proof.

Definition. The statement “there exists a unique $x\in A$ such that $P(x)$,” written $\exists!x\in A\,P(x)$, means that there is an $x\in A$ satisfying $P(x)$, and any two elements of $A$ satisfying $P$ are equal.

Theorem (Existence and Uniqueness as Two Claims). For a condition $P(x)$ on a set $A$, $$ \exists!x\in A\,P(x) \Longleftrightarrow \bigl(\exists x\in A\,P(x)\bigr) \text{ and } \bigl(\forall u,v\in A,\ (P(u)\text{ and }P(v))\Rightarrow u=v\bigr). $$

Proof. Suppose $\exists!x\in A\,P(x)$. By the definition of unique existence, there is an element $x\in A$ satisfying $P(x)$, so the existential claim holds. The same definition says that any two elements of $A$ satisfying $P$ must be equal. Thus the universal condition on $u$ and $v$ holds.

Conversely, suppose there is an $x\in A$ satisfying $P(x)$, and suppose any two elements of $A$ satisfying $P$ are equal. The first assumption supplies at least one such element. The second ensures that if $u,v\in A$ both satisfy $P$, then $u=v$. Therefore exactly one element of $A$ satisfies $P$, which is $\exists!x\in A\,P(x)$. $\square$

Worked Example: Proving a Solution Is Unique

Fix a real number $a$. We show that there is a unique real number $y$ satisfying $y+4=a$. For existence, choose $y=a-4$, which is real. Substitution gives

$$ y+4=(a-4)+4=a. $$

For uniqueness, suppose $u$ and $v$ are real numbers satisfying the equation. Then $u+4=a$ and $v+4=a$. Subtracting $4$ from both equalities gives

u=a-4 \qquad\text{and}\qquad v=a-4.

Consequently $u=v$. We have supplied a solution and proved that any two solutions agree, so the solution $y=a-4$ is unique.

A Practical Proof Plan

The quantifiers in a claim indicate what to do in a proof. When proving a universal-existential claim, begin with an arbitrary input and then construct or identify a witness. When proving that an existential-universal claim is false, assume a proposed witness and find an input for which it fails. Negations are particularly useful in that second situation: they turn a claim of nonexistence into a universal condition that can be contradicted.

Write the domains.
Record which set each variable belongs to, so that every chosen witness meets the required condition.

Follow the quantifier order.
For a universal quantifier, begin with an arbitrary element. For an existential quantifier, give a witness after the preceding choices are known.

For uniqueness, compare two candidates.
Assume both candidates satisfy the condition and prove they are equal, in addition to establishing existence.

For a negation, change each quantifier.
Replace “for every” by “there exists,” replace “there exists” by “for every,” and negate the final condition.

A common pitfall is to find a witness for one input and treat that as proof of a universal-existential statement. One example of a suitable pair does not establish that a suitable witness can be found for every input. Another is to prove existence and stop when the claim asks for a unique object. In both cases, matching each part of the proof to the quantifiers prevents a gap.

Key takeaway. With multiple quantifiers, order controls who may depend on whom: a witness chosen after an arbitrary input may depend on that input. Negation reverses each quantifier in turn, and a unique-existence proof must establish both a witness and agreement between any two candidates.

Check Your Understanding

For each question, identify the choices required by the quantifiers before deciding how to prove the claim.

In $\forall x\in A\,\exists y\in B\,P(x,y)$, which variable is chosen first, and may the witness depend on it?
Write the negation of $\exists x\in A\,\forall y\in B\,P(x,y)$.
Why does proving $\forall n\in\mathbb{Z}\,\exists m\in\mathbb{Z}\,(m>n)$ not establish the statement with the quantifiers reversed?
What two separate claims must be established to prove $\exists!x\in A\,P(x)$?
In a uniqueness argument, what should you assume about two proposed solutions before proving they are equal?

Proofs With Multiple Quantifiers

What You'll Learn