Predicate Logic

Predicate logic — also called first-order logic (FOL), predicate calculus, or quantificational logic — is the formal system that extends propositional logic by introducing quantifiers, variables, and predicates. Where propositional logic manipulates atomic sentences treated as indivisible units, predicate logic opens those atoms and examines their internal structure: it can say not merely 'Socrates is mortal' but 'there exists something that is mortal' and 'everything that is a human is mortal.' This expansion is not cosmetic. Predicate logic is the language in which mathematics, formal science, and rigorous philosophy conduct their most important arguments. It is the grammar of exact thought.

The transition from propositional to predicate logic is one of the most consequential events in the history of ideas. Aristotle's syllogistic, the dominant formal logic for two millennia, could capture certain patterns of valid inference — but only a fragment of those available in mathematics. The proof that every even number greater than two is the sum of two primes, if it exists, cannot be expressed in syllogistic form. The axioms of Zermelo-Fraenkel set theory cannot be expressed in syllogistic form. When Gottlob Frege published the Begriffsschrift in 1879 — a concept-notation that for the first time captured quantification with full generality — he made possible the logical analysis of mathematics that would occupy the next century.

Syntax and Semantics

Predicate logic distinguishes two levels: syntax (the formal manipulation of symbols according to rules) and semantics (the assignment of meaning to those symbols). This distinction is what makes predicate logic a formal system rather than merely a notation.

The syntactic vocabulary includes:

• Individual constants (a, b, c,...) — names for specific objects
• Variables (x, y, z,...) — placeholders ranging over a domain
• Predicate symbols (P, Q, R,...) — represent properties or relations
• Logical connectives (¬, ∧, ∨, →, ↔) — inherited from propositional logic
• Quantifiers: the universal quantifier ∀ ('for all') and the existential quantifier ∃ ('there exists')
• Equality (=) — in first-order logic with identity

From these, well-formed formulas (wffs) are built according to syntactic rules. '∀x(Human(x) → Mortal(x))' is well-formed. '∀Human → Mortal' is not. The rules are mechanical: a computer can determine whether any string is a wff without understanding what the string means.

The semantics assigns content to syntax via the concept of a model: a domain of objects (the universe of discourse) plus interpretations of the predicate symbols as sets of objects or tuples. A sentence is true in a model if its semantics evaluates to true under that model's assignment. A sentence is valid — a tautology — if it is true in every model. A sentence is satisfiable if it is true in at least one model.

The central semantic achievement of predicate logic is the completeness theorem, proved by Kurt Gödel in 1929: every valid sentence of predicate logic can be proved from the axioms of predicate logic using finite proof rules. Proof and truth, in predicate logic, coincide. This was the confirmation that the syntax of predicate logic was semantically adequate — that no truth was locked away beyond the reach of formal proof. It was also the last moment of complete optimism about formal systems. Two years later, Gödel's incompleteness theorems showed that any consistent formal system rich enough to express arithmetic contains truths it cannot prove. Predicate logic is complete. Predicate logic augmented with arithmetic is not.

Quantifiers and Their Power

The expressive power of predicate logic is concentrated in its quantifiers. '∀x P(x)' says that every object in the domain has property P. '∃x P(x)' says that at least one object has property P. These two devices together allow predicate logic to express claims that are entirely beyond propositional logic.

Consider the claim 'every number has a successor.' In propositional logic, this cannot be stated — it ranges over infinitely many objects. In predicate logic: ∀x ∃y Successor(x, y). This is a single sentence with finite length that makes an infinitary claim. This expressive compression is why predicate logic is the native language of mathematics.

Quantifier scope interacts subtly with meaning. '∀x ∃y Loves(x,y)' says everyone loves someone — a different claim from '∃y ∀x Loves(x,y),' which says there is someone whom everyone loves. The reversal of quantifiers reverses the claim. Scope ambiguities in natural language — 'every student passed some exam' — are a major source of equivocation in informal argument. Predicate logic makes scope explicit and compulsory.

Second-order logic extends first-order predicate logic by allowing quantification over predicates themselves, not just over individuals. Second-order logic can characterize the natural numbers uniquely (something first-order logic, by the Löwenheim-Skolem theorem, cannot do). But second-order logic loses completeness: there are truths of second-order logic that no formal proof system can derive. The price of greater expressive power is the loss of the connection between proof and truth. This trade-off is not resolved; it is the ongoing fault line of mathematical logic.

Completeness, Decidability, and Limits

The completeness theorem assures that predicate logic's proof system captures all its logical truths. But predicate logic is undecidable: there is no algorithm that takes an arbitrary sentence and determines, in finite time, whether it is valid. This was proved by Alan Turing and Alonzo Church in 1936 — the same year Turing proved that the halting problem for Turing machines is unsolvable. The two undecidability results are connected: computing and logical validity face the same ceiling.

What this means practically: there are sentences of predicate logic that are valid (true in all models) but whose validity cannot be established by any mechanical procedure running in bounded time. Logic is complete in the sense that valid proofs always exist; it is undecidable in the sense that we cannot always find them.

This has consequences for automated theorem proving and for artificial reasoning more broadly. Any system that claims to derive conclusions from premises using predicate logic as its underlying framework is operating in a space where some conclusions are unreachable by any finite procedure — not because the system is defective, but because completeness and decidability are properties that separate at this level of expressive power.

The restriction to propositional logic recovers decidability at the cost of expressive power. The extension to second-order logic recovers expressive power at the cost of completeness. Predicate logic occupies the maximal expressive position compatible with both a complete proof system and a semantically tractable notion of truth. This is not an accident — it is the result that decades of limitative theorems have converged on.

Predicate Logic and Natural Language

Predicate logic was designed to represent the logical structure of mathematical propositions, but its application to natural language is both illuminating and deeply contested. When Bertrand Russell analyzed 'the present king of France is bald,' using predicate logic — ∃x(KingOfFrance(x) ∧ ∀y(KingOfFrance(y) → y=x) ∧ Bald(x)) — he resolved centuries of puzzlement about definite descriptions that fail to refer. This is the paradigm use of predicate logic in philosophy of language.

But natural language is not predicate logic. Semantic phenomena that resist predicate-logical analysis include: tense and aspect (the 'now' of 'it is raining' picks out a time, not a timeless domain); mass terms ('some water is in the glass' requires a different quantificational structure than 'some cats are in the house'); generics ('ravens are black' is not ∀x(Raven(x) → Black(x)), which would be falsified by albino ravens); and propositional attitude reports ('Mary believes that the earth is flat' does not follow predicate-logical compositionality).

These failures have generated formal alternatives: temporal logic, mass noun semantics, generic logic, intensional logic. All of them extend or modify the predicate-logical framework rather than replacing it. The framework is the baseline from which departures are measured. No natural language is predicate logic. But every attempt to formalize natural language is an attempt to describe its distance from predicate logic.

The Foundational Claim

Predicate logic is sometimes described as a formal tool — a useful notation for rigorous argument. This description is accurate but undersells its significance. Predicate logic is not a tool that we could replace with a different tool. It is the outcome of the inquiry into what valid inference is, conducted with maximum precision. The alternatives — intuitionistic logic, modal logic, second-order logic, paraconsistent logic — are not alternatives to predicate logic. They are defined by their departures from it. You cannot understand what these alternatives do without understanding what predicate logic is.

The claim that every deductive science presupposes predicate logic is not quite right — it presupposes some logic, and predicate logic has competitors. But the claim that understanding predicate logic is a prerequisite for understanding any formal system of reasoning is not extravagant. Every computer program has a formal semantics that is, at the relevant level of abstraction, predicate-logical. Every mathematical proof is, when fully spelled out, a derivation in some formal system that extends predicate logic. Every philosophical argument that aspires to validity is, when its commitments are made explicit, a claim about what follows from what in some first-order or higher-order system.

The persistent failure of philosophy, computer science, and cognitive science to require predicate logic as foundational training for their practitioners is the intellectual equivalent of requiring engineers to understand stress and strain without requiring them to understand algebra. Predicate logic is not one tool among many. It is the language in which the concept of a tool is defined.