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 represent it by a single propositional symbol $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 (individuals) 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: the truth value of $P(x)$ depends on what is substituted for the variable.
The domain of discourse is the set, fixed in advance, over which the variables range. The "all" of $\forall x$ and the "there exists" of $\exists x$ always refer to that domain, and until it is fixed a formula has no truth value at all.
For instance $\exists x\, (x^2 = 2)$ is true when the domain is the reals $\mathbb{R}$, but false over the rationals $\mathbb{Q}$ and false over the natural numbers $\mathbb{N}$. Since one and the same formula changes its truth value with the domain, "what the claim is about" matters just as much as the formula itself. By convention the domain is often left unwritten when it is clear from context, but it is only omitted, never absent.
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.
- $\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 (taking the domain to be the reals; false over $\mathbb{Q}$ or $\mathbb{N}$)
- $\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.
One point: quantifiers and negation. Pushing a negation inside a quantifier swaps $\forall$ and $\exists$: $$\neg \forall x\, P(x) \iff \exists x\, \neg P(x), \qquad \neg \exists x\, P(x) \iff \forall x\, \neg P(x)$$ "Not everything is $P$" becomes "something is not $P$," and "nothing is $P$" becomes "everything fails to be $P$." These are De Morgan's laws of propositional logic extended to quantifiers. The everyday practice of refuting a universal claim by exhibiting a counterexample is exactly this equivalence.
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.
This article is about first-order predicate logic. Every variable $x$ we have quantified so far denotes an individual (a person, a number — an element of the domain of discourse). A system that quantifies only over individuals is called first-order predicate logic. By contrast, a system that can quantify over predicates and properties themselves, writing things like $\forall P\,(P(a) \rightarrow P(b))$ ("for every property, if $a$ has it then so does $b$"), is called higher-order predicate logic. Being able to say "for every property" raises the expressive power — mathematical induction becomes a single axiom, for instance — but the completeness theorem — the property, valid for first-order logic, that whatever is semantically true is provable — is lost in exchange. See Simple type theory = HOL for details.
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
References
- Frege, G. (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle: Nebert. (the first decomposition into predicate and argument, with quantifiers and bound variables)
- Peirce, C. S. (1885). "On the Algebra of Logic: A Contribution to the Philosophy of Notation". American Journal of Mathematics, 7(2), 180–202. (an independent formulation of quantification)
- Hilbert, D., & Ackermann, W. (1928). Grundzüge der theoretischen Logik. Berlin: Springer. (first-order logic formulated as an independent system)
- Enderton, H. B. (2001). A Mathematical Introduction to Logic (2nd ed.). Academic Press. (standard treatment of domains of discourse and satisfaction)
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).