Universal and Existential Quantifiers

Quantifiers are not a notational curiosity confined to introductory logic; they are the load-bearing grammar of essentially every field that makes precise claims. In analysis, the $\varepsilon$–$\delta$ definition of a limit,

is a triply-nested quantified statement, and correctly understanding the order of $\forall$ and $\exists$ here (rather than swapping them) is precisely what distinguishes ordinary continuity from uniform continuity — a distinction explored further in Nested and Multiple Quantifiers. In algebra and number theory, group axioms, definitions of divisibility, and statements like "every integer greater than 1 has a prime factor" are universal or existential claims whose proofs follow exactly the templates of Examples 1 and 2 above. In computer science, quantifiers appear in formal specification languages (e.g., Hoare logic preconditions/postconditions), in database query languages (SQL's `EXISTS` and `NOT EXISTS` are literal implementations of $\exists$ and its negation), and in complexity theory, where the polynomial hierarchy is defined by counting alternations of $\forall$ and $\exists$ over Boolean formulas. In cryptography, security definitions are often stated as: "for all probabilistic polynomial-time adversaries, there exists a negligible function such that..." — a direct nested-quantifier structure whose logical order is what makes the security guarantee meaningful rather than vacuous. In statistics and formal verification, universally quantified invariants ("for all reachable states, the safety property holds") are the backbone of model checking, while existential quantifiers underlie satisfiability problems (SAT solvers answer exactly the question $\exists$ an assignment making a formula true).

Ask the tutor: How do the rules for negating and proving quantified statements change once two or more quantifiers are nested together, as in the definition of a limit?

The cleanest way to think about $\forall$ and $\exists$ is as generalizations of the ordinary logical connectives $\land$ (and) and $\lor$ (or). If the domain $D = \{a_1, a_2, \dots, a_n\}$ is finite, then

This is not merely an analogy for finite $D$; it is a literal logical equivalence, since a finite conjunction is true exactly when every conjunct is true, and a finite disjunction is true exactly when at least one disjunct is true — precisely the defining conditions above. When $D$ is infinite, we cannot literally write out an infinite conjunction or disjunction as a formula, but the quantifiers are defined to preserve exactly this behavior: $\forall$ demands universal success, $\exists$ demands only a single success. This "infinite AND / infinite OR" picture immediately explains why $\forall$ is a strong, fragile claim (one bad case ruins it) while $\exists$ is a weak, robust claim (one good case secures it). It also explains, without any further argument, why negating $\forall$ should produce $\exists$ of the negation: negating "$P(a_1)$ and $P(a_2)$ and $\dots$" by De Morgan's law gives "not $P(a_1)$ or not $P(a_2)$ or $\dots$," which is exactly $\exists x\, \lnot P(x)$. We make this rigorous in the theorem below. A second useful picture is geometric: think of $D$ as a set of points on a number line or in a plane, and shade the subset $T = \{x \in D : P(x) \text{ is true}\}$. Then $\forall x \in D,\ P(x)$ says $T = D$ (the shaded region is everything), while $\exists x \in D,\ P(x)$ says $T \neq \varnothing$ (the shaded region is nonempty).

Example 1 (a universal statement over an infinite domain, proved directly). Claim: $\forall n \in \mathbb{Z},\ n^2 \geq n$. Proof. Let $D = \mathbb{Z}$ (an infinite domain, so we cannot check cases one by one; we argue for an arbitrary representative). Let $n$ be an arbitrary integer; we must show $n^2 \geq n$, equivalently $n^2 - n \geq 0$, equivalently $n(n-1) \geq 0$. We split into three cases based on the sign of $n$, which exhaust $\mathbb{Z}$:

• If $n \geq 1$: then $n > 0$ and $n - 1 \geq 0$, so $n(n-1) \geq 0$ as a product of a positive number and a nonnegative number.
• If $n = 0$: then $n(n-1) = 0 \cdot (-1) = 0 \geq 0$.
• If $n \leq -1$: then $n < 0$ and $n - 1 \leq -2 < 0$, so $n(n-1)$ is a product of two negative numbers, hence positive, hence $\geq 0$.

Every integer $n$ falls into exactly one of these three cases (since either $n\ge1$, $n=0$, or $n\le -1$ partitions $\mathbb Z$), and in each case $n(n-1)\ge 0$, i.e. $n^2 \ge n$. Since $n$ was an arbitrary element of $\mathbb{Z}$, and $P(n): n^2\ge n$ held in every case, the definition of the universal quantifier is satisfied: $\forall n \in \mathbb{Z},\ n^2 \geq n$ is true. $\blacksquare$ This illustrates the standard strategy for proving a $\forall$-statement over an infinite domain: introduce an arbitrary, unspecified element (never a specific number, since that would only check one instance), and derive the predicate using only properties shared by all elements of the domain.

Example 2 (an existential statement, with an explicit witness, over a domain requiring care). Claim: $\exists x \in \mathbb{Q},\ 1 < x^2 < 2$. Proof. Take $x = \frac{6}{5} = 1.2$, which is a rational number since it is a ratio of integers with nonzero denominator, so $x \in \mathbb{Q}$. We compute

Since $1 < 1.44 < 2$, we have $1 < x^2 < 2$ for this particular $x$. By the definition of the existential quantifier, exhibiting one element of the domain ($\mathbb{Q}$) satisfying the predicate ($1 < x^2 < 2$) is sufficient to establish $\exists x \in \mathbb{Q},\ 1 < x^2 < 2$. $\blacksquare$ Note the asymmetry with Example 1: here a single, concrete witness fully proves the statement, and no case analysis over all of $\mathbb{Q}$ is needed or possible — this is the defining asymmetry between $\forall$-proofs (must handle every case, typically via an arbitrary generic element) and $\exists$-proofs (need only one case, typically via a specific constructed or guessed element). It is also worth noting the domain matters: the same predicate over $D = \mathbb{Z}$ instead of $\mathbb{Q}$ gives $\exists x \in \mathbb{Z},\ 1 < x^2 < 2$, which is false, since the only integers with $x^2$ near $1$–$2$ are $x = 1$ (giving $x^2=1$, not $>1$) and $x=-1$ (same), with no integer square strictly between $1$ and $2$. This shows explicitly why the domain is not a decorative detail: changing $D$ from $\mathbb{Q}$ to $\mathbb{Z}$ changes the truth value of the exact same open sentence from true to false.