Predicates and Quantifiers

Why does Aristotle's syllogism 'All humans are mortal. Socrates is a human. Therefore Socrates is mortal' work? Propositional logic cannot explain it: for propositional logic, 'All humans are mortal' and 'Socrates is mortal' are simply different letters P and Q. Predicate logic exposes the internal structure of statements.

• **Databases:** the SQL query `SELECT * FROM users WHERE age > 18 AND country = 'RU'` is a combination of predicates. `EXISTS` and `ALL` are quantifiers
• **Programming:** the methods `every()`, `some()`, `filter()`, `find()` implement quantifiers and predicates from first-order logic
• **Mathematics:** definitions and theorems are written with quantifiers. '∀ε>0 ∃δ>0: |x-a|<δ → |f(x)-f(a)|<ε' is the definition of continuity

Predicate

In propositional logic we worked with **whole statements** as indivisible units: P, Q, R. But the sentence 'Socrates is mortal' has structure: a **subject** (Socrates) and a **property** (mortal). **A predicate** is a property or relation that can be applied to objects.

**A predicate** is a function that takes one or more objects and returns true or false. Notation: P(x), where P is the predicate and x is a variable. Examples: Mortal(x), Greater(x, y), Between(x, y, z).

In programming, predicates are **boolean-returning functions**. The method `isEven(n)` is a predicate. The filter `array.filter(x => x > 0)` uses the predicate `x => x > 0`. The SQL condition `WHERE age > 18` is also a predicate.

Quantifiers

Predicates become truly powerful with **quantifiers**, operators that say **how many** objects satisfy the predicate. Two main quantifiers: **universal** (∀, 'for all') and **existential** (∃, 'there exists').

**∀x P(x)** reads as 'for all x, P(x) holds' or 'every x has property P'. **∃x P(x)** reads as 'there exists x such that P(x)' or 'at least one x has property P'.

Quantifiers can be combined, and the order matters. '∀x ∃y Loves(x, y)' means 'everyone loves someone' (each person has someone to love, possibly different). And '∃y ∀x Loves(x, y)' means 'there is someone whom everyone loves' (a single universally loved object).

Universal quantifier

**The universal quantifier ∀** (read 'for all' or 'for any') claims that a property holds for **every** object in the domain under consideration. This is the strongest kind of claim: a single counterexample is enough to refute it.

**The domain** is the set of objects the variable ranges over. 'All swans are white' is false in the domain {Australian swans} but was held true for centuries in the domain {European swans}.

**Vacuous truth:** the statement ∀x (P(x) → Q(x)) is true when **no objects satisfy P**. 'All unicorns are pink' is true (there are no unicorns to check). This is often counterintuitive but mathematically correct.

Existential quantifier

**The existential quantifier ∃** (read 'there exists' or 'for some') claims that a property holds for **at least one** object. This is a weak claim: one example is enough to prove it.

**Linking quantifiers through negation (De Morgan for quantifiers):** ¬(∀x P(x)) ≡ ∃x ¬P(x) and ¬(∃x P(x)) ≡ ∀x ¬P(x). 'Not all students passed' = 'There exists one who did not pass'. 'No immortal exists' = 'All are mortal'.

**Uniqueness:** sometimes you need 'there exists exactly one'. Notation: ∃! (read 'there exists a unique'). ∃!x P(x) means: ∃x P(x) ∧ ∀y∀z (P(y) ∧ P(z) → y = z). Exists and is unique.

Key Ideas

• **Predicate:** a function of objects returning true or false, P(x), Q(x, y)
• **∀ (for all):** a claim about every object, refuted by one counterexample
• **∃ (there exists):** an existence claim, proved by one example
• **De Morgan:** ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
• **Quantifier order matters:** ∀x∃y ≠ ∃y∀x in general

Related Topics

Predicate logic is the foundation of formal systems:

• Normal forms — Predicate logic has its own normal forms (Skolem, Prenex)
• Deduction — Aristotelian syllogisms are formalized in predicate logic
• Sets — Sets are defined via predicates: {x | P(x)}

Вопросы для размышления

• How would you formalize 'Every programmer makes mistakes sometimes' using quantifiers?
• Why does SQL have both `EXISTS` and `NOT EXISTS` rather than just negation?
• Give an example of a statement that changes meaning when the quantifiers are reordered.

Связанные уроки

• comp-18-type-checking
• ml-02