From One Variable to Several
In Negating Existential Statements, we completed the two single-quantifier negation rules. A universal claim fails when there is a counterexample; an existential claim fails when every possible witness is ruled out. These rules still apply when the condition following a quantifier contains another quantifier.
For example, “Every real number has an additive inverse” involves two numbers: an arbitrary real number \(x\), and a real number \(y\) whose sum with \(x\) is zero. Written with explicit quantifiers, the statement is
This is not a new kind of quantifier. It is an ordinary universal statement whose condition is itself an existential statement. Understanding that nesting is the main task of this tutorial.
Conditions, Scope, and Nested Statements
Let \(D\) and \(E\) be domains, and let \(A(x,y)\) be a condition that has a definite truth value whenever \(x\in D\) and \(y\in E\) are specified. For example, \(A(x,y)\) could mean \(x+y=0\) when both domains are \(\mathbb R\).
When parentheses are omitted from a string of quantifiers, we read it with this nesting:
An occurrence of a variable is bound if it lies within the scope of a quantifier for that variable; otherwise it is free. In \(\exists y\in\mathbb R,\ x+y=0\), the occurrence of \(y\) is bound, but \(x\) remains free. This formula expresses a condition on \(x\). Adding \(\forall x\in\mathbb R\) binds \(x\) as well and produces a statement with no free variables.
A useful way to read a longer formula is to treat everything after the first quantifier as one condition. For instance, define \(B(x)\) to mean “\(\exists y\in E,\ A(x,y)\).” Then the nested formula becomes simply \(\forall x\in D,\ B(x)\).
Four Basic Two-Quantifier Forms
The following table gives the literal reading of each two-quantifier form. Each row must be read in its written order.
| Formula | What it asserts |
|---|---|
| \(\forall x\in D,\ \forall y\in E,\ A(x,y)\) | For every \(x\in D\), every \(y\in E\) satisfies the condition with that \(x\). |
| \(\exists x\in D,\ \exists y\in E,\ A(x,y)\) | There is an \(x\in D\) for which there is a \(y\in E\) satisfying the condition. |
| \(\forall x\in D,\ \exists y\in E,\ A(x,y)\) | For every \(x\in D\), at least one \(y\in E\) satisfies the condition with that \(x\). |
| \(\exists x\in D,\ \forall y\in E,\ A(x,y)\) | There is an \(x\in D\) for which every \(y\in E\) satisfies the condition. |
When the domains agree, \(\forall x,y\in D,\ A(x,y)\) is standard shorthand for two universal quantifiers over \(D\). Likewise, \(\exists x,y\in D,\ A(x,y)\) abbreviates two existential quantifiers. We will usually keep the individual quantifiers visible.
Matching a Proof to Its Quantifiers
A universal quantifier asks for an argument covering an arbitrary allowed input. An existential quantifier asks for a verified witness. With multiple quantifiers, apply these requirements one layer at a time.
Worked Example: Two Universal Quantifiers
Let \(D=\{0,1\}\) and \(E=\{2,3\}\). Prove
Let \(x\in D\) and \(y\in E\) be arbitrary. Since \(x\leq1\) and \(y\geq2\), we have \(x\leq1<2\leq y\), so \(x<y\). This proves the claim for every allowed pair.
Checking only \(x=0,y=2\) would not have proved the statement. The universal quantifiers also cover the other combinations, including \(x=1,y=2\).
Worked Example: Two Existential Quantifiers
Prove
Choose \(x=2\). For this value of \(x\), choose \(y=3\). Both numbers belong to \(\mathbb R\), both are positive, and \(2+3=5\). Thus \(y=3\) verifies the inner existence claim for \(x=2\), and \(x=2\) verifies the outer one.
There is no need to describe all possible witnesses. One verified pair suffices.
Worked Example: An Existential Condition for Each Input
Return to the statement
Let \(x\in\mathbb R\) be arbitrary. Choose \(y=-x\). This is a real number, and \(x+y=x+(-x)=0\). Thus the inner existential statement is true for this arbitrary \(x\). Since the argument applies to every real \(x\), the full statement is true.
The witness has been supplied after \(x\) was fixed. A single example such as \(x=2,y=-2\) would verify only one instance of the universal claim.
For a statement beginning with an existential quantifier followed by a universal one, first exhibit the outer witness and then verify the entire universal condition. For example,
is true: choose \(x=0\). For every real \(y\), the identity \(0+y=y\) holds. The witness \(x=0\) therefore satisfies the complete condition following its quantifier.
Record which values are allowed for each variable.
For “every,” begin with an arbitrary allowed input. For “there exists,” supply an allowed witness.
Apply the same requirements to each remaining quantifier without rearranging the formula.
Check all its requirements and ensure the argument covers every universal choice.
Negating Two Quantifiers
The earlier negation rules apply even when the condition being negated contains a quantifier. The key is to move the negation inward one layer at a time.
Proof. For the first equivalence, apply the negation rule for a universal statement to the condition \(B(x)\) given by \(\exists y\in E,\ A(x,y)\). This gives
For each fixed \(x\in D\), the negation rule for an existential statement gives \(\neg(\exists y\in E,\ A(x,y))\equiv\forall y\in E,\ \neg A(x,y)\). Replacing the inner condition by this equivalent condition proves the first formula.
For the second equivalence, apply the existential negation rule first:
The last step uses the universal negation rule for each fixed \(x\). Both single-quantifier rules were established for arbitrary domains, including empty ones, so these deductions need no nonemptiness assumptions. This proves both equivalences.
The same procedure handles two quantifiers of the same kind:
A Counterexample May Require a Universal Argument
Worked Example: One Input with No Successful Witness
Let \(D=\{0,1,2\}\). Consider
This says that each element of \(D\) has a larger element in \(D\). Its negation is
Choose \(x=2\). Each allowed value of \(y\), namely \(0,1,2\), satisfies \(2\geq y\). Therefore the negation is true and the original statement is false.
The pair \(x=0,y=0\) also fails \(x<y\), but it does not disprove the original statement: when \(x=0\), the value \(y=1\) succeeds. To refute the original claim, we need an \(x\) for which every allowed \(y\) fails, not merely one failed pair.
This is an important extension of the previous tutorial. A counterexample to an outer universal statement must make its entire inner condition false. When that inner condition asserts existence, its failure requires excluding all its possible witnesses.
Three Quantifiers and Compound Conditions
Nothing fundamentally changes when a third quantifier appears. For example,
says that for every real \(x\), and for every real \(y\), there is a real \(z\) equal to their sum. To prove it, let \(x,y\) be arbitrary real numbers and choose \(z=x+y\). The sum is real, and the required equality holds.
Applying the single-quantifier negation rules three times gives its negation:
This claims there are two real inputs whose sum equals no real number. It is false: for any proposed inputs \(x,y\), the real number \(z=x+y\) violates the final condition.
Worked Example: Negating the Whole Final Condition
Negate
First negate the nested quantifiers, then apply De Morgan’s Laws:
The original statement is true. For arbitrary real \(x\), choose \(y=x+1\); then \(x<x+1<x+2\). Consequently its negation is false. Both inequalities must be negated, and the conjunction must become a disjunction.
Empty Domains: Evaluate One Layer at a Time
Consider again the general form
If \(D=\varnothing\), the statement is true by vacuous truth, regardless of \(E\). There is no outer input for which the inner condition must be checked.
If \(D\neq\varnothing\) but \(E=\varnothing\), the statement is false. Choose any \(x\in D\). For that \(x\), the inner existential statement is false because there is no \(y\in E\).
For the form \(\exists x\in D,\ \forall y\in E,\ A(x,y)\), an empty \(D\) makes the statement false. If \(D\neq\varnothing\) and \(E=\varnothing\), it is true: choose any \(x\in D\), and the inner universal statement is vacuously true.
Check Your Understanding
Read each formula as a nested statement. In proofs and disproofs, explain which inputs are arbitrary and which values serve as witnesses.
- In \(\exists y\in\mathbb R,\ x+y=3\), which variable is free? Add a universal quantifier for it, translate the resulting statement into words, and prove it.
- Let \(D=\{1,2\}\) and \(E=\{3,4\}\). Determine the truth of \(\forall x\in D,\ \forall y\in E,\ x+y\geq4\) and \(\exists x\in D,\ \exists y\in E,\ x+y=6\). Justify each answer.
- Negate \(\forall x\in\{0,1,2\},\ \exists y\in\{0,1,2\},\ x+y=2\). Determine the truth of both statements. Why does the failed pair \(x=0,y=0\) not settle the original claim?
- Negate \(\exists x\in\mathbb R,\ \forall y\in\mathbb R,\ x+y=y\). Prove the original statement and explain why your negation is false.
- Negate \(\forall x\in\mathbb R,\ \forall y\in\mathbb R,\ \exists z\in\mathbb R,\ (z>x)\land(z>y)\). Preserve every domain and simplify the negation of the final condition.
- Determine the truth of \(\forall x\in D,\ \exists y\in E,\ x=y\) and \(\exists x\in D,\ \forall y\in E,\ x=y\) when \(D=E=\varnothing\), and then when \(D=\{0\}\) and \(E=\varnothing\).