Quantified Statements
Where logical-connectives and conditional-statements deal with whole statements, predicates let us talk about statements whose truth depends on a variable, and quantifiers turn those predicates back into statements that are definitely true or false.
Predicates
A predicate is a sentence with a finite number of variables that becomes a statement when particular values are assigned to those variables.
- Predicates: \(x > 0\), “\(x\) divides \(y\)”.
- Not predicates: “Is it raining?” (a question), “She is happy.” (no objective truth value).
A predicate is written \(P(x)\), and the set of values \(x\) may take is its domain \(D\).
Common domains
| Symbol | Set |
|---|---|
| \(\mathbb{R}\) | real numbers |
| \(\mathbb{Q}\) | rational numbers |
| \(\overline{\mathbb{Q}}\) | irrational numbers (\(\mathbb{R} \setminus \mathbb{Q}\)) |
| \(\mathbb{Z}\) | integers, \(\{\dots, -2, -1, 0, 1, 2, \dots\}\) |
| \(\mathbb{N}\) | natural numbers |
| \(\mathbb{Z}^+\) | positive integers, \(\{1, 2, 3, \dots\}\) |
| \(\mathbb{Z}^{\text{nonneg}} = \mathbb{Z}^{\geq 0}\) | \(\{0, 1, 2, 3, \dots\}\) |
| \(\mathbb{Z}^{\text{even}}\) | \(\{\dots, -4, -2, 0, 2, 4, \dots\}\) |
Nesting: \(\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}\), with \(\overline{\mathbb{Q}}\) sitting alongside \(\mathbb{Q}\) inside \(\mathbb{R}\).
Take care with \(\mathbb{N}\) — different sources define it as \(\{0, 1, 2, \dots\}\) or \(\{1, 2, 3, \dots\}\). Prefer the unambiguous \(\mathbb{Z}^+\) or \(\mathbb{Z}^{\geq 0}\) in your own writing.
\(\in\) means “belongs to” / “is an element of”; \(\notin\) means “is not an element of”. Note that \(\{\mathbb{Z}\} \neq \mathbb{Z}\) — writing \(x \in \{\mathbb{Z}\}\) says \(x\) is the set \(\mathbb{Z}\), not that \(x\) is an integer.
The two quantifiers
| Symbol | Reads | Associated English words |
|---|---|---|
| \(\forall\) | “for all” | all, every, any, each, none, no |
| \(\exists\) | “there exists” | there is, some, at least one, not all |
- Universal: \(\forall x \in D, P(x)\) — “for all \(x\) in \(D\), \(P(x)\)”.
- Existential: \(\exists x \in D\) such that \(P(x)\) — “there exists an \(x\) in \(D\) such that \(P(x)\)”. “such that” is commonly abbreviated s.t.
Note the punctuation convention: \(\forall\) takes a comma, \(\exists\) takes “such that”.
Translating English to symbols
| English | Symbolic |
|---|---|
| Every rational number is a real number. | \(\forall x \in \mathbb{Q}, x \in \mathbb{R}\) |
| No integer is an irrational number. | \(\forall x \in \mathbb{Z}, x \notin \overline{\mathbb{Q}}\) |
| Some real numbers are rational. | \(\exists x \in \mathbb{R}\) s.t. \(x \in \mathbb{Q}\) |
| Not all rational numbers are integers. | \(\exists x \in \mathbb{Q}\) s.t. \(x \notin \mathbb{Z}\) |
| All prime numbers are odd. | \(\forall x \in P, x\) is odd |
| If an integer is divisible by 2 then it is divisible by 4. | \(\forall x \in \mathbb{Z},\) if \(2 \mid x\) then \(4 \mid x\) |
Two things to watch:
- “No …” is universal, not existential — “no integer is irrational” becomes \(\forall\), with the predicate negated.
- Sometimes the quantifier is implicit. “If an integer is a square, then it is nonnegative” carries a hidden \(\forall\): \(\forall n \in \mathbb{Z},\) if \(n\) is a square then \(n \geq 0\).
Determining truth
- \(\forall x \in D, P(x)\) is shown false by one counterexample.
- \(\exists x \in D\) s.t. \(P(x)\) is shown true by one example.
The asymmetry matters: a single value can settle a universal statement only in the negative, and an existential statement only in the positive.
\(\exists y \in \mathbb{Z}\) s.t. \(y^2 - y = 0\) is true — choose \(y = 0\) or \(y = 1\). That some other choice (\(y = 2\)) fails is irrelevant; \(\exists\) only asks for one witness. The corresponding universal statement \(\forall y \in \mathbb{Z}, y^2 - y = 0\) is false, and \(y = 2\) is exactly the counterexample that shows it.
\(\forall x \in \mathbb{Z}\), if \(6\) is divisible by \(x\) then \(x = 2\) is false — take \(x = 3\): it’s an integer, \(6\) is divisible by \(3\), but \(3 \neq 2\). (The corrected true statement is \(\forall x \in \mathbb{Z}\), if \(6\) is divisible by \(x\) then \(x = \pm 1, \pm 2, \pm 3\) or \(\pm 6\).)
Negation
Negating a quantified statement flips the quantifier and negates the predicate:
\[\sim\big(\forall x \in D, P(x)\big) \equiv \exists x \in D \text{ s.t. } \sim P(x)\]
\[\sim\big(\exists x \in D \text{ s.t. } P(x)\big) \equiv \forall x \in D, \sim P(x)\]
If the negation of a statement is true, the original is false — so proving the negation is a legitimate way to disprove a statement (see proof-techniques).
When the predicate is itself conditional, negate it with \(\sim(p \to q) \equiv p \land \sim q\) (see logical-equivalence-laws). So the negation of
\[\forall x \in \mathbb{Z}, \text{ if } x^2 > 3 \text{ then } x > 3\]
is \(\exists x \in \mathbb{Z}\) s.t. \(x^2 > 3\) and \(x \leq 3\) — not “if … then …” with an \(\exists\) in front, and not the converse.
A negation is not just “the opposite-sounding statement”
For \(S = \{1, 3, 5, 7\}\), \(\{1,2,3,4\}\), \(\{2,4,6,8\}\):
| \(S\) | \(\forall x \in S, x\) is odd | \(\forall x \in S, x\) is not odd | \(\exists x \in S\) s.t. \(x\) is not odd |
|---|---|---|---|
| \(\{1,3,5,7\}\) | T | F | F |
| \(\{1,2,3,4\}\) | F | F | T |
| \(\{2,4,6,8\}\) | F | T | T |
The first and third columns are exact negations of each other (they disagree in every row). The middle column — “all are not odd” — is not the negation: for \(S = \{1,2,3,4\}\) both it and the original are false.
Worked negations
| Statement | Negation | Which is true |
|---|---|---|
| \(\exists y \in \mathbb{R}\) s.t. \(y^2 < 0\) | \(\forall y \in \mathbb{R}, y^2 \geq 0\) | negation |
| All dogs are white. | Some dog is not white. | negation |
| \(\forall x \in \mathbb{Z}^+, x\) is prime or \(x\) is composite | \(\exists x \in \mathbb{Z}^+\) s.t. \(x\) is neither prime nor composite | negation (\(x = 1\)) |
| \(\forall x \in \mathbb{R}\), if \(x > 2\) then \(x^2 > 4\) | \(\exists x \in \mathbb{R}\) s.t. \(x > 2\) and \(x^2 \leq 4\) | original |
| \(\forall x \in \mathbb{R}\), if \(x^2 > 9\) then \(x \geq 2\) | \(\exists x \in \mathbb{R}\) s.t. \(x^2 > 9\) and \(x < 2\) | negation (\(x = -4\)) |
Multiple quantifiers
Order matters. Read the statement left to right as a game:
- \(\forall x \in X, \exists y \in Y\) s.t. \(P(x,y)\) — “someone gives me an \(x\); can I always then find a \(y\)?” The choice of \(y\) may depend on \(x\).
- \(\exists x \in X\) s.t. \(\forall y \in Y, P(x,y)\) — “is there a single \(x\) that works for every \(y\)?” The \(x\) must be chosen before seeing \(y\).
Both of these happen to be true for \(xy \geq y\) over \(\mathbb{Z}\), but for different reasons:
- \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) s.t. \(xy \geq y\) — given \(x\), choose \(y = x\) (since \(x^2 \geq x\) for every integer), or more simply \(y = 0\).
- \(\exists x \in \mathbb{Z}\) s.t. \(\forall y \in \mathbb{Z}, xy \geq y\) — take \(x = 1\), since \(y \geq y\) always.
Where order really bites: \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) s.t. \(y = 2x\) is true (given \(x\), take \(y = 2x\)), but \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) s.t. \(x = 2y\) is false — take \(x = 3\), and \(y = \tfrac{3}{2} \notin \mathbb{Z}\).
Writing two of the same quantifier
\(\exists x \in D\) and \(\exists y \in E \dots\) is the clearest form; \(\exists x \in D\) and \(y \in E \dots\) is common shorthand, and \(\exists x, y \in D \dots\) is shorthand when both range over the same domain.
Negating multiple quantifiers
Flip every quantifier in order, and negate the predicate at the end:
\[\sim\big(\forall x \in X, \exists y \in Y \text{ s.t. } P(x,y)\big) \equiv \exists x \in X \text{ s.t. } \forall y \in Y, \sim P(x,y)\]
Worked examples:
| Statement | Negation | Which is true |
|---|---|---|
| \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\) s.t. \(x + y = 0\) | \(\exists x \in \mathbb{R}\) s.t. \(\forall y \in \mathbb{R}, x + y \neq 0\) | original (take \(y = -x\)) |
| \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\) s.t. \(xy = 1\) | \(\exists x \in \mathbb{R}\) s.t. \(\forall y \in \mathbb{R}, xy \neq 1\) | negation (\(x = 0\)) |
| \(\exists x \in \mathbb{R}\) s.t. \(\forall y \in \mathbb{R}, xy = 0\) | \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\) s.t. \(xy \neq 0\) | original (take \(x = 0\)) |
| \(\exists x \in \mathbb{Z}^+\) s.t. \(\forall y \in \mathbb{Z}^+, x \geq y\) | \(\forall x \in \mathbb{Z}^+, \exists y \in \mathbb{Z}^+\) s.t. \(x < y\) | negation (take \(y = x+1\)) |
| \(\forall x, y \in \mathbb{Z}, \exists z \in \mathbb{Z}\) s.t. \(z = x - y\) | \(\exists x, y \in \mathbb{Z}\) s.t. \(\forall z \in \mathbb{Z}, z \neq x - y\) | original |
| \(\forall r, s \in \mathbb{R}\), if \(rs \in \mathbb{Q}\) then \(r \in \mathbb{Q}\) and \(s \in \mathbb{Q}\) | \(\exists r, s \in \mathbb{R}\) s.t. \(rs \in \mathbb{Q}\) and (\(r \notin \mathbb{Q}\) or \(s \notin \mathbb{Q}\)) | negation (\(r = s = \sqrt{2}\)) |
A negation trap: the negation of “\(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) s.t. \(x + y\) is odd” is “there exists an integer \(x\) such that for every integer \(y\), \(x + y\) is even”. (The original is true: if \(x\) is odd take \(y = 0\), if \(x\) is even take \(y = 1\).)
See also
- logical-connectives · logical-equivalence-laws · conditional-statements
- proof-techniques — proving and disproving quantified statements
- practice-problems — §6 Quantified Statements, with full worked solutions
- practice-problems — §7 Negation of Quantified Statements, with full worked solutions
- practice-problems — §8 Statements with Multiple Quantifiers, with full worked solutions