The Anatomy of Logic: Quantification Theory and the Microstructure of Arguments

*Translated and adapted from a Chinese forum post on zhichai.net.*

From Black Box to Microscope: A Cognitive Revolution in Logic

Consider a medical paper that reasons: "All cancer patients need chemotherapy, therefore this patient's cancer cells need to be attacked by chemotherapy drugs." To most readers the inference sounds obvious—but a logician immediately asks: what actually happens between "all cancer patients" and "this patient's cancer cells"?

Traditional propositional logic is helpless here. It treats "all cancer patients need chemotherapy" as an indivisible atomic proposition—a black box. It can say "if P then Q," but cannot explain what hides inside P.

This is where first-order logic (predicate logic) enters.

Dissecting Sentences: The Three Components of First-Order Logic

The core insight of first-order logic: sentences are not atoms but molecules, decomposable into more basic parts.

1. Individuals

The objects we talk about: Socrates in "Socrates is human," the number 3 in "3 is prime," the Earth in "Earth orbits the Sun." First-order logic uses constant symbols for specific individuals (e.g., s for Socrates) and variables (x, y, z) for arbitrary individuals.

2. Predicates

Predicates describe properties and relations, taking individuals as input and truth values as output:

| Natural language | First-order notation | |---|---| | Socrates is human | Human(s) | | 3 is prime | Prime(3) | | Earth orbits the sun | Orbits(earth, sun) |

Predicates have different arity: unary predicates describe properties (Human(x)), binary predicates describe relations (Loves(x,y), GreaterThan(x,y)), and ternary-or-higher predicates describe more complex relations (Between(x,y,z)).

3. Quantifiers

The most crucial innovation:

• Universal quantifier ∀ ("for all"):
> ∀x (Human(x) → Mortal(x)) > > "For all x, if x is human, then x is mortal."
• Existential quantifier ∃ ("there exists"):
> ∃x (Human(x) ∧ Wise(x)) > > "There exists at least one x that is human and wise."

Note the connective distinction: universal statements use implication (→)—we don't claim everything is human—while existential statements use conjunction (∧)—both conditions must hold simultaneously.

Reconstructing Classical Arguments: The Syllogism Modernized

Why is "all horses are animals, therefore horses' heads are animals' heads" valid?

Aristotle's syllogism (the *Barbara* form) certifies validity but doesn't explain it deeply. First-order logic makes the reasoning transparent:

• Premise: ∀x (Horse(x) → Animal(x))
• Using a function symbol headOf(x) for "the head of x":
• Conclusion: ∀x (Horse(x) → Animal(headOf(x)))

Key insight: first-order logic can discuss part–whole relations, territory propositional logic cannot reach.

Quantifier inference rules that license this reasoning:

• Universal Instantiation: from ∀x P(x), infer P(a) for any individual a
• Existential Generalization: from P(a), infer ∃x P(x)
• Universal Generalization: if P holds for arbitrarily chosen individuals, infer ∀x P(x)

What First-Order Logic Can Do

Foundation of mathematics

The ZFC set theory axioms underlying modern mathematics are stated in first-order logic, e.g., the axiom of infinity:

> ∃x (∅ ∈ x ∧ ∀y (y ∈ x → y∪{y} ∈ x))

Computer science

• SQL is essentially a first-order logic variant. SELECT name FROM Students WHERE age > 18 corresponds to {name | ∃age (Student(name, age) ∧ age > 18)}
• Program verification proves correctness using first-order logic
• Knowledge representation (semantic web, ontologies) describes world knowledge with it

Natural language analysis

The ambiguous sentence "Every boy loves a girl" has distinct readings:

1. *Same girl*: all boys love one and the same girl 2. *Possibly different girls*: ∀x (Boy(x) → ∃y (Girl(y) ∧ Loves(x,y)))

First-order logic precisely distinguishes such ambiguities—a foundation for natural language processing.

Limits and Beyond

• Gödel's incompleteness theorems (1931): any consistent formal system containing basic arithmetic has propositions that can be neither proved nor refuted—first-order logic cannot capture all mathematical truth.
• Expressive boundaries: cannot directly express modal concepts ("necessarily P"), tense ("future P"), higher-order quantification ("for all properties P..."), or infinite conjunctions—these require modal, temporal, higher-order, or infinitary logics.
• Undecidability: unlike propositional logic, there is no general algorithm deciding validity of arbitrary first-order formulas. But this is a sign of strength: the logic is powerful enough to express undecidable mathematical problems.

A Learning Path

1. Foundations: syntax (constants, variables, functions, predicates, quantifiers); semantics (models, interpretations, satisfiability, validity); translation practice 2. Intermediate: natural deduction (quantifier introduction/elimination rules), model-theoretic proofs, axiomatization 3. Applications: relational algebra and database theory, description logic (a restricted fragment of first-order logic), Hoare logic and weakest preconditions for program verification

Conclusion: Logic as a Way of Thinking

Studying first-order logic trains precision (sharp conceptual boundaries), analysis (decomposing complex propositions), and systematicity (rule-governed inference without intuitive leaps). When we see why "all horses are animals, therefore horses' heads are animals' heads" holds, we witness a precise dance among quantifiers, predicates, and individuals—an anatomy that cuts beneath language's surface to reveal the microstructure of argument.

Further Reading

• Enderton, H. B. (2001). *A Mathematical Introduction to Logic*
• Hodges, W. (1997). *A Shorter Model Theory*
• Wang Hao (1993). *A Logical Journey: From Gödel to Philosophy*

Exercises

1. Translate "no horse can fly" into first-order logic (at least two equivalent ways) 2. Prove: ∀x (P(x) → Q(x)) ∧ ∀x (Q(x) → R(x)) ⊢ ∀x (P(x) → R(x)) 3. Discuss: can first-order logic express "most students passed the exam"? If not, why?