Predicate logic

Core idea

Propositional logic treated whole sentences as atoms and combined them with five connectives. That is enough for many arguments, but too coarse for any inference that depends on what is inside a sentence — on whether the subject is universal or particular, on whether the same individual is being talked about across sentences. Predicate logic (also called first-order logic or quantification theory) refines the resolution. It breaks each atomic sentence into a predicate applied to one or more individuals, introduces variables to range over individuals, and adds two quantifiers to bind those variables.

The two quantifiers are the universal quantifier ∀x ("for all x") and the existential quantifier ∃x ("there exists at least one x"). With predicates P(x), Q(x, y), and these two quantifiers on top of the five propositional connectives, you have a system powerful enough to express almost every argument in mathematics, science, law, and philosophy. The system pioneered by Frege in 1879 and refined by Russell, Whitehead, and others is still the standard formal language of academic logic.

Why it matters

Why this is the culmination

Predicate logic is the unifying system that swallows both categorical and propositional logic. Aristotle's syllogisms become special cases. Propositional reasoning continues to work unchanged inside quantified statements. And the new resolution — being able to talk about individuals, predicates, and relations — is what mathematics needs to formalize claims like "every integer has a successor" or "for every epsilon there exists a delta".

Why translation is where the work is

The rules of inference in predicate logic are not significantly harder than in propositional logic. The hard part is translation: turning an ordinary-language sentence into the right formal expression. Most beginner errors are translation errors, not inference errors.

Mental model

The new vocabulary

Four kinds of symbol replace propositional logic's atomic letters:

• Individual constants — a, b, c — refer to specific individuals. (s for Socrates.)
• Individual variables — x, y, z — range over individuals.
• Predicates — uppercase letters with arguments. M(x) = "x is mortal". L(x, y) = "x loves y".
• Quantifiers — ∀x ("for all x") and ∃x ("there exists x").

Copy sourceZoom

The two quantifiers

The universal quantifier ∀x reads "for all x"; the existential quantifier ∃x reads "there exists at least one x such that". They behave like generalized conjunction and disjunction over the domain of individuals: ∀x P(x) is "P holds of every individual" and ∃x P(x) is "P holds of at least one individual".

Copy sourceZoom

Quantifier scope and order

Quantifier order encodes dependency. ∀x ∃y L(x, y) means "every x loves some y (possibly a different one for each x)". ∃y ∀x L(x, y) means "there exists some single y that every x loves". The two say very different things.

Copy sourceZoom

The four quantifier inference rules

Natural deduction extends with four new rules — two for each quantifier, one introduction and one elimination.

• Universal instantiation (∀-elimination): from ∀x P(x), infer P(a) for any individual a.
• Universal generalization (∀-introduction): if you proved P(a) for an arbitrary a, infer ∀x P(x).
• Existential instantiation (∃-elimination): from ∃x P(x), introduce a fresh name a and assume P(a).
• Existential generalization (∃-introduction): from P(a), infer ∃x P(x).

These rules let you prove validity for quantified arguments by reducing them, line by line, to propositional manipulations on instantiated formulas.

Practical application

To evaluate any ordinary-language argument involving "every", "all", "some", or "there is", the workflow is:

1. Choose a domain of individuals (people, numbers, events).
2. Define predicates for each property and relation mentioned. Be precise — is-tall(x) is one predicate; is-taller-than(x, y) is a two-place relation.
3. Translate each sentence into a predicate-logic formula. Watch for scope — does "every X has a Y" mean a different Y per X, or a single Y for all X?
4. Verify with semantics or natural deduction. Either show no interpretation makes the premises true and conclusion false, or derive the conclusion using the quantifier inference rules on top of propositional rules.

Example

A real argument from a policy debate:

• "Every regulation creates some compliance cost. There is no compliance cost we can ignore. Therefore, there is no regulation we can ignore."

Choose a domain: actions taken by a government. Define predicates:

• R(x) = "x is a regulation"
• C(x) = "x is a compliance cost"
• Creates(x, y) = "x creates y"
• Ignore(x) = "x can be ignored"

Translate the three sentences:

• Premise 1: ∀x (R(x) → ∃y (C(y) ∧ Creates(x, y)))
• Premise 2: ∀y (C(y) → ¬Ignore(y))
• Conclusion: ∀x (R(x) → ¬Ignore(x))

The argument appears valid by analogy with categorical reasoning, but is it? Test with natural deduction:

1. Assume an arbitrary regulation r, so R(r) (for ∀-introduction setup).
2. From premise 1 and universal instantiation: R(r) → ∃y (C(y) ∧ Creates(r, y)).
3. By modus ponens with step 1: ∃y (C(y) ∧ Creates(r, y)).
4. Existential instantiation: introduce c, with C(c) ∧ Creates(r, c).
5. From premise 2 and universal instantiation: C(c) → ¬Ignore(c).
6. From step 4 and conjunction elimination: C(c).
7. Modus ponens on 5 and 6: ¬Ignore(c).

Now look at where we are. We proved that the compliance cost c cannot be ignored. But the conclusion claims the regulation r cannot be ignored. The argument equivocates between "the regulation" and "the cost it creates". The argument is invalid — ¬Ignore(c) does not give us ¬Ignore(r).

This is exactly the kind of slippage that predicate logic catches but the earlier systems could not. The argument trades on a confusion between an object and a property of an object — categorical logic could not see it because both sides looked like universals about classes; propositional logic could not see it because both sides looked like simple sentences. Only when you decompose each sentence into predicates over individuals does the fallacy become visible. That is the payoff of the full machinery.

Related lessons