Propositional and First-Order Logic

Propositional and first-order logic are the workhorse formal systems of classical logic, expressive enough to regiment most ordinary and mathematical reasoning.

Definition

Propositional logic studies inference among whole sentences combined by truth-functional connectives; first-order logic extends it with quantifiers ranging over a domain of individuals and with predicates and relations, while keeping quantification restricted to individuals rather than properties.

Scope

This topic covers the syntax, semantics, and proof theory of the classical propositional calculus (truth-functional connectives) and first-order predicate logic (quantifiers, variables, and relations). It includes the central metatheoretic results — soundness, completeness, compactness, and the Lowenheim-Skolem theorems — and the philosophical significance of first-order logic's standing as the canonical framework for regimenting argument and for the foundations of mathematics.

Core questions

• What is the expressive reach of first-order logic, and what cannot be expressed in it?
• Why is first-order logic often regarded as the privileged logic for regimentation?
• What do completeness and compactness tell us about the relation between syntax and semantics?
• What are the philosophical costs and benefits of going second-order?

Key concepts

• truth-functional connectives
• quantifiers and variables
• satisfaction and models
• completeness and compactness
• Lowenheim-Skolem theorems
• first-order vs. second-order logic

Key theories

Completeness of first-order logic

Godel's completeness theorem establishes that every first-order semantic consequence is provable in a standard deductive system, so derivability and model-theoretic validity coincide for first-order logic.

First-order orthodoxy

Quine defends restricting canonical logic to first order, on the grounds that it is complete, ontologically perspicuous, and free of the set-theoretic commitments and incompleteness of second-order logic.

History

Frege's 1879 Begriffsschrift introduced quantifier-variable notation and the first system of predicate logic, independently anticipated by Peirce. The metatheory was settled in the early twentieth century with Godel's completeness theorem (1929) and the compactness and Lowenheim-Skolem results, after which Quine and others promoted first-order logic as the canonical logical framework.

Debates

Is first-order logic the right canonical logic?

Whether logic should be confined to first order, given its completeness and ontological clarity, or extended to second-order logic for greater expressive power at the cost of completeness and heavier mathematical commitments.

Key figures

• Gottlob Frege
• Kurt Godel
• W. V. O. Quine
• Charles Sanders Peirce
• Herbert Enderton

Seminal works

• frege1879
• quine1986

Frequently asked questions

What is the difference between first-order and second-order logic?

First-order logic quantifies only over individual objects in a domain. Second-order logic also allows quantification over properties, relations, and functions of those objects. Second-order logic is far more expressive but lacks a complete proof system and carries stronger mathematical commitments, which is why many philosophers treat first-order logic as canonical.