FOL 02 · Quantifiers
Quantifiers say for how many elements a predicate is true (“all”, “some”, “none”, …). The second way (besides plugging in values) to turn a predicate into a proposition.
Domain of discourse
The domain (universe of discourse) is the set of values the variable can take.
A quantified statement has no meaning without a domain — and its truth value can change with the domain.
Example: is T over the positive integers (x = 1) but F over . Same formula, different domain, different answer.
Universal quantifier ∀
: “P(x) for all values of x in the domain.” English: for all x / for every x / for each x / for any x / all of x.
| ∀x P(x) is… | when |
|---|---|
| TRUE | P(x) is true for every x in the domain |
| FALSE | there is at least one x with P(x) false — a counterexample |
Counterexamples
- , domain positive integers → F (counterexample x = 5)
- , domain integers → F (x = 1: 2 > 2 is false) One counterexample is enough to kill a ∀.
Finite domain: if the domain is :
Existential quantifier ∃
: “there exists an element x in the domain such that P(x).” English: there is an x such that / there is at least one x / for some x.
| ∃x P(x) is… | when |
|---|---|
| TRUE | P(x) is true for at least one x — a witness |
| FALSE | P(x) is false for every x |
Finite domain:
Slide examples
- , domain {1,2,3,4} → T (x = 4)
- , integers → T (x = 1)
- , integers → T (x = −1: 0 > −2)
- , reals → T (x = −1)
- , reals → T (x = ½: 1/16 < 1/4)
Memory: ∀ is a big AND, ∃ is a big OR.
∀ needs all (one counterexample kills it). ∃ needs one witness.
Restricted domains (quantifier with a condition)
Shorthand: put the condition right after the quantifier.
| Shorthand | Meaning | Expanded |
|---|---|---|
| square of any negative real is positive | ||
| 2 has a positive square root |
The golden rule (shows up everywhere)
Restriction on ∀ becomes →. Restriction on ∃ becomes ∧. More in FOL 05 Translating English.
Expressing quantifications in English
- P(x): “x spends more than five hours every weekday in class”, domain students → : “Every student spends more than five hours every weekday in class.”
- N(x): “x has visited North Korea”, domain students in your school → : “All students in your school have visited North Korea.”
🏠 Slide homework — solved
R(x): x² ≥ 0, S(x): x² ≥ x, T(x): x² < 0. Domain: integers. Truth values of ∀x R(x), ∀x S(x), ∀x T(x)?
- → T (squares are never negative)
- → T for integers (x ≤ 0 ⇒ x² ≥ 0 ≥ x; x ≥ 1 ⇒ x² ≥ x). ⚠️ False over reals (x = ½: ¼ ≥ ½ fails) — domain matters!
- → F (even is F)
∀x P(x), P(x): "x is perfect", domain: people in your locality.
“Everyone in your locality is perfect.” (Almost certainly false — one imperfect neighbour is a counterexample.)
Domain: reals. (a) ∃x(x² = 2) (b) ∃x(x² = −1) (c) ∃x(x² < 0)
(a) T (x = √2) (b) F (no real square is negative) (c) F
Q1. ∀x<0 (x² = 1), domain reals.
F — counterexample x = −2 (4 ≠ 1).
Q2. Domain integers. (a) ∃x≠2 (x² = 4) (b) ∃x (x < 0 → x² − 2 ≥ 1)
(a) T — x = −2. (b) T — x = −2 gives 4 − 2 = 2 ≥ 1. (As written with →, even x = 5 works vacuously, since x < 0 is false. ⚠️ This is exactly why ∃ should be paired with ∧, not →.)
Prev ← FOL 01 Predicates · Next → FOL 03 Quantifier Equivalences