1
A predicate becomes a proposition when its variables are bound
P(x) has no truth value; P(5) and ∀x P(x) both do. Binding happens by substitution or by a quantifier.
Lesson · Logic and Proof · Predicate logic
Predicates and Quantifiers
A predicate is a sentence with a free variable. ∀ and ∃ bind that variable and produce something with a truth value — and both depend entirely on the domain, which is why an unstated domain is an unstated claim.
P(x) : "x > 3" a predicate — no truth value yet
∀x P(x) true when P(x) holds for EVERY x in the domain
∃x P(x) true when P(x) holds for AT LEAST ONE x
The domain is part of the statement, not context.
Predicate, then quantifier
Core ideas
What this lesson establishes
Propositional logic cannot express "every integer has a successor". Predicates and quantifiers are what it takes.
2
The domain changes the answer
∃x (x² = 2) is false over the rationals and true over the reals. Stating the domain is not pedantry — without it there is no claim.
3
∀ over an empty domain is true
Vacuous truth again: with nothing to check, nothing fails. Symmetrically, ∃ over an empty domain is false.
The material
Predicates, domains and the two quantifiers
What each quantifier asserts, and what it takes to establish or refute it.
Definition · Predicate
A predicate P(x) is a sentence containing a free variable, which becomes a proposition once a value from the domain is substituted. Predicates may have several variables: Q(x, y).
Definition · Domain of discourse
The domain is the set of values the variables range over. It is part of the statement: ∀x (x² ≥ x) is true over the integers and false over the reals, where x = ½ refutes it.
Definition · Universal quantifier
∀x P(x) ("for all x, P(x)") is true when P(c) is true for every c in the domain, and false as soon as one c makes it false.
Definition · Existential quantifier
∃x P(x) ("there exists x such that P(x)") is true when P(c) is true for at least one c in the domain.
The asymmetry in what it costs to settle these is the heart of the lesson. To prove ∀x P(x) over an infinite domain you need an argument covering every case; to refute it you need one counterexample. For ∃x P(x) it is the reverse: one witness proves it, and refuting it takes a general argument.
to PROVE to REFUTE
∀x P(x) argument over all x one counterexample
∃x P(x) one witness argument over all x
Over a finite domain both quantifiers collapse into connectives. With domain {1, 2, 3}, ∀x P(x) is P(1) ∧ P(2) ∧ P(3) and ∃x P(x) is P(1) ∨ P(2) ∨ P(3). That is exactly why the empty-domain conventions come out as they do: an empty conjunction is T and an empty disjunction is F.
Definition · Bound and free variables
In ∀x P(x, y) the variable x is bound and y is free. A formula with a free variable is still a predicate; only when all variables are bound is it a proposition.
Example · Restricting the domain
"Every even integer greater than 2 is composite" is written ∀x ((x > 2 ∧ Even(x)) → Composite(x)) — the restriction becomes the hypothesis of a conditional. With ∃ the restriction becomes a conjunction instead: ∃x (Even(x) ∧ Prime(x)). Mixing these two patterns up is the standard error.
Theorem · Uniqueness
∃!x P(x) means "there is exactly one x with P(x)", and abbreviates ∃x (P(x) ∧ ∀y (P(y) → y = x)). It is two claims: something exists, and nothing else does.
Interactive
Quantifier order
A finite universe you can edit
Method
Translating into quantifiers
Domain first, predicate second, quantifier last.
1
State the domain explicitly
"All integers", "all real numbers", "all students in this class". Without it the formula is not a claim.
2
Name the predicates
Give each property a symbol with its variables shown: P(x) for "x is prime", L(x, y) for "x likes y".
3
Choose the quantifier
"Every", "all", "each", "any" signal ∀. "Some", "there is", "at least one" signal ∃. Beware "any", which is ∀ in a positive sentence and often ∃ under a negation.
4
Attach restrictions correctly
With ∀, a restriction becomes the hypothesis of →. With ∃, it becomes a conjunct of ∧. Using ∧ under ∀ claims far too much.
Quantifiers
Score 0 / 0Choose the answer you can justify.
Why the restriction pattern differs
Domain: all integers. P(x) = "x is prime", E(x) = "x is even".
"Every prime greater than 2 is odd"
∀x ((P(x) ∧ x > 2) → ¬E(x)) correct
∀x (P(x) ∧ x > 2 ∧ ¬E(x)) WRONG — claims every integer
is an odd prime > 2
"Some prime is even"
∃x (P(x) ∧ E(x)) correct (x = 2)
∃x (P(x) → E(x)) WRONG — satisfied by any
non-prime, e.g. x = 9
The second wrong form is the subtler one. P(9) → E(9) is F → F, which is true, so the existential is satisfied by a number that is neither prime nor even. A conditional under ∃ is almost always a mistake.
Common mistakes
1
Leaving the domain implicit∃x (x² = 2) is false over ℚ and true over ℝ. A quantified statement without a stated domain has no truth value to argue about.
2
Using ∧ under ∀ for a restriction∀x (P(x) ∧ Q(x)) says every element of the domain has both properties, which is far stronger than "every P is a Q".
3
Using → under ∃∃x (P(x) → Q(x)) is satisfied by any x failing P, so it is nearly always vacuously true and almost never what was meant.
Check your understanding
✓
Finish when the two restriction patterns are automatic.
Translate "every positive even integer greater than 2 is composite" and "some composite number is odd" into symbols, and say for each why the connective inside had to be what it is.
Note: The lab uses a four-element domain so that both quantifiers can be checked exhaustively. That is a luxury of finiteness: over ℕ no amount of checking settles a ∀, which is the whole motivation for Induction and Recursion.