Predicate Logic and Quantifiers
Handling "for all" and "there exists"
Introduction (high school to first-year university)
Goal of this page
Move on to predicate logic, which handles the "for all" and "there exists" that propositional logic could not express. Understand predicates and variables, the quantifiers $\forall, \exists$, and the difference between bound and free variables.
1. The limits of propositional logic
Propositional logic treats a proposition as an indivisible atom. But the claim "every natural number is at least $0$" bundles together infinitely many propositions about individual natural numbers, and propositional logic can only crush it into a single letter $p$. That cannot express the structure "as $n$ changes, the claim changes."
So we enter the inside of a proposition and treat objects (variables) and properties/relations (predicates) separately; this is predicate logic (first-order predicate logic).
History note: who started predicate logic?
Modern predicate logic was effectively founded by Gottlob Frege. In his book Begriffsschrift (1879), he decomposed propositions into predicate and argument and first systematically introduced the quantifiers ($\forall, \exists$) and bound variables — the very idea, in this article, of "entering the inside of a proposition."
At nearly the same time, Charles S. Peirce (and his student O. H. Mitchell, around 1883–85) independently developed quantifier notation and spread the idea of quantification. The symbols close to those used today were arranged by Giuseppe Peano.
First-order predicate logic — the kind treated in this article — was first clearly formulated as an independent system by Hilbert and Ackermann (Principles of Mathematical Logic, 1928). A distant ancestor that partly handled quantification is Aristotle's syllogistic (term logic), but full predicate logic with quantifiers and bound variables begins with Frege.
2. Predicates and variables
A predicate is an expression that takes objects as arguments and returns a truth value. $P(x)$ means "$x$ has property $P$," and $Q(x, y)$ means "$x$ and $y$ are in the relation $Q$." The number of arguments is the predicate's arity.
- $\mathrm{Even}(x)$: "$x$ is even" ($\mathrm{Even}(4)$ is true, $\mathrm{Even}(3)$ is false)
- $\mathrm{Less}(x, y)$: "$x < y$" ($\mathrm{Less}(2, 5)$ is true)
Until concrete objects are substituted, the truth value is undetermined: $P(x)$ may be true or false depending on the value of $x$.
3. Quantifiers: $\forall$ and $\exists$
Universal quantification $\forall x\, P(x)$: "$P(x)$ holds for all $x$."
Existential quantification $\exists x\, P(x)$: "there exists at least one $x$ with $P(x)$."
Instead of substituting objects into a predicate one by one, quantifiers bundle a claim "over all objects." This lets us go beyond the limits of propositional logic and write mathematical sentences directly. The notation and handling of quantifiers is also covered with examples in Proof: Quantifiers.
- $\forall n\, (\mathrm{Even}(n) \lor \mathrm{Odd}(n))$: every natural number is even or odd
- $\exists x\, (x^2 = 2)$: a square root of $2$ exists
- $\forall \varepsilon\, \exists \delta\, \dots$: the $\varepsilon$-$\delta$ definition of continuity
The order of quantifiers changes the meaning. $\forall x\, \exists y\, P(x,y)$ (for each $x$ there is a $y$ for it) and $\exists y\, \forall x\, P(x,y)$ (there is a single $y$ common to all $x$) are different claims. In the $\varepsilon$-$\delta$ argument, "$\delta$ may depend on $\varepsilon$" because of this order.
4. Bound and free variables
A variable $x$ within the scope of a quantifier $\forall x$ or $\exists x$ is a bound variable. The name of a bound variable may be replaced by any other unused letter without changing the meaning ($\forall x\, P(x)$ and $\forall z\, P(z)$ are the same).
A variable bound by no quantifier is a free variable. A free variable's truth value is undetermined until its value is fixed.
The free renaming of bound variables ($\alpha$-conversion) is important when handling proofs mechanically. The mechanism of treating formulas with the same meaning as the same also plays a central role in the λ-calculus.
Summary
Key points
- Predicate logic: enter the inside of a proposition and separate objects (variables) from properties/relations (predicates)
- Quantifiers: $\forall$ (for all) and $\exists$ (there exists) express claims over all objects
- The order of quantifiers changes the meaning ($\forall\exists$ and $\exists\forall$ differ)
- Bound variables can be renamed; free variables have truth values depending on their value
Frequently asked questions
How does predicate logic differ from propositional logic?
Propositional logic treats a proposition as an indivisible atom, but predicate logic enters its inside, distinguishing objects (variables) from properties and relations (predicates). It also introduces $\forall$ and $\exists$, so it can express claims like "for every natural number $n$, ...".
What is the difference between bound and free variables?
A variable $x$ within the scope of a quantifier $\forall x$ or $\exists x$ is bound, and renaming it does not change the meaning. A variable bound by no quantifier is free, and its truth value is undetermined until its value is fixed. In $\forall x\, P(x,y)$, $x$ is bound and $y$ is free.
May the order of $\forall$ and $\exists$ be swapped?
In general no. $\forall x\,\exists y\,P(x,y)$ means "for every $x$ there is a corresponding $y$," while $\exists y\,\forall x\,P(x,y)$ means "there is a single $y$ common to all $x$" — a different claim. The order governs the strength of the statement.
Who started predicate logic?
Modern predicate logic was effectively founded by Gottlob Frege, who in his Begriffsschrift (1879) decomposed propositions into predicate and argument and first systematically introduced the quantifiers ($\forall$, $\exists$) and bound variables. Around the same time Charles S. Peirce independently developed quantifier notation, and the symbols were later refined by Giuseppe Peano. First-order predicate logic was first clearly formulated as an independent system by Hilbert and Ackermann (1928).