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
TRUEP(x) is true for every x in the domain
FALSEthere 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
TRUEP(x) is true for at least one x — a witness
FALSEP(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.

ShorthandMeaningExpanded
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


Prev ← FOL 01 Predicates · Next → FOL 03 Quantifier Equivalences