Quantifiers & First-Order Translation

Render English into and , and read quantifier scope.

The idea

The quantifiers $\forall$ and $\exists$ are how first-order logic expresses "every" and "some". Fix a domain of discourse, the collection of things under discussion. A predicate $P(x)$ is a property an element of the domain may or may not have, and a quantified formula says how widely it holds.

Definition (Quantifiers).

Over a domain of discourse, $\forall x\; \varphi(x)$, read for every $x$, $\varphi(x)$, is true when $\varphi$ holds of every element of the domain; and $\exists x\; \varphi(x)$, read there exists an $x$ such that $\varphi(x)$, is true when $\varphi$ holds of at least one element.

A quantifier ranges over the whole domain, while an English sentence rarely does: "every student is happy" is a claim about students only. We build the restriction into the body, and differently for the two quantifiers. A universal claim restricts with an implication, $\forall x\,(P(x) \to Q(x))$, which stays true on the elements the sentence is not about; an existential claim asserts with a conjunction, $\exists x\,(P(x) \wedge Q(x))$, so that only a genuine example can satisfy it.

When quantifiers nest, the inner one lies inside the scope of the outer, so the element it picks may depend on the element the outer one picked. The order of unlike quantifiers is part of the meaning: as the figure shows, $\forall x\, \exists y$ lets the choice of $y$ vary with $x$, while $\exists y\, \forall x$ commits to a single $y$ that must serve every $x$.

Ways to work on it

• Walkthrough. Translate sentences into quantified formulas, choosing the right quantifier and connective.
• Practice. Translate a sentence into first-order logic.
• Hardest. Negate a quantified sentence and read a nested mixed-quantifier formula.

Not sure where to start? Take the ten-question placement test.