Mathematical Logic: Propositional Logic, Predicate Logic, and Gödel's Theorems
Introduction
Mathematical logic is the study of the principles of reasoning itself. Where other branches of mathematics take certain methods of proof for granted and apply them to specific domains, logic turns the microscope inward and examines the very nature of mathematical proof. What does it mean for a statement to be true? What does it mean for a proof to be valid? Are there truths that cannot be proved? These questions are the domain of mathematical logic.
The subject emerged from crises in mathematics at the turn of the twentieth century. The discovery of paradoxes in naive set theory — Russell’s paradox being the most famous — led mathematicians to question the foundations of their discipline. Hilbert proposed a program to prove that mathematics is consistent and complete. Gödel’s incompleteness theorems showed that Hilbert’s program cannot be carried out, establishing permanent limits on what formal systems can achieve.
Propositional Logic
Propositional logic deals with logical connectives — and, or, not, implies, if and only if — applied to atomic propositions. A propositional formula is built from atomic propositions using these connectives. The truth value of a compound formula is determined by the truth values of its components.
Truth Tables and Semantic Entailment
Truth tables provide a systematic method for determining the truth value of any propositional formula given the truth values of its atomic constituents. A formula is valid (a tautology) if it is true under every assignment of truth values to its atoms. It is satisfiable if it is true under at least one assignment.
Semantic entailment Γ ⊨ φ means that whenever all formulas in Γ are true, φ is also true. The deduction theorem connects entailment to implication: Γ ∪ {ψ} ⊨ φ if and only if Γ ⊨ ψ → φ. The compactness theorem states that if every finite subset of Γ is satisfiable, then Γ is satisfiable.
Predicate Logic
Predicate logic extends propositional logic with quantifiers — for all (∀) and there exists (∃) — and predicates that express properties of and relations between objects. First-order logic allows quantification over individuals but not over predicates or functions.
Completeness and Compactness
Gödel’s completeness theorem states that for first-order logic, the syntactic notion of provability coincides with the semantic notion of logical consequence. A formula is provable from a set of axioms if and only if it is true in every model of those axioms. This theorem shows that first-order proof systems capture the full power of semantic reasoning.
The Löwenheim-Skolem theorem states that any first-order theory with an infinite model has models of every infinite cardinality. This theorem reveals that first-order logic cannot uniquely characterize infinite structures. The connections between logic and set theory clarify which structures can and cannot be uniquely described.
Gödel’s Incompleteness Theorems
Gödel’s first incompleteness theorem states that any consistent formal system capable of expressing arithmetic contains statements that can be neither proved nor disproved within the system. The system is essentially incomplete: no matter how many axioms are added, as long as they are recursively enumerable and consistent, there will remain undecidable statements.
Gödel Numbering
Gödel’s proof uses an ingenious encoding — Gödel numbering — that assigns numbers to formulas and proofs. This encoding allows arithmetic statements to talk about provability itself. The statement G that says “G is not provable” is expressible in the language of arithmetic and is true but unprovable in any consistent system.
The second incompleteness theorem states that a consistent system capable of arithmetic cannot prove its own consistency. This shattered Hilbert’s program of proving the consistency of mathematics from within mathematics. Any proof of consistency must use methods stronger than those being justified.
Computability Theory
Computability theory, also called recursion theory, studies which functions can be computed by mechanical procedures. A function is computable if there exists an algorithm — a finite list of instructions — that computes its value for any input. The Church-Turing thesis identifies computable functions with those computable by a Turing machine.
Undecidability
The halting problem asks whether there exists an algorithm that determines whether a given Turing machine halts on a given input. Turing proved that the halting problem is undecidable — no algorithm exists. This result is the foundation of undecidability theory, showing that there are well-defined mathematical problems that cannot be solved by any mechanical procedure.
Rice’s theorem states that any nontrivial property of the behavior of Turing machines is undecidable. For further examples of what cannot be proved or computed, see mathematical proof techniques.
Model Theory
Model theory studies the relationship between formal languages and their interpretations — models. A theory is a set of sentences in a formal language. A model of a theory is a structure in which all sentences of the theory are true.
Classical Theorems
The compactness theorem — if every finite subset of a theory has a model, then the whole theory has a model — is one of the most powerful tools in model theory. It allows the construction of nonstandard models of arithmetic and analysis that contain infinite and infinitesimal elements.
The Löwenheim-Skolem theorems control the sizes of models. Upward Löwenheim-Skolem states that any theory with an infinite model has models of arbitrarily large cardinalities. Downward Löwenheim-Skolem states that any countable theory with a model has a countable model. These theorems reveal the limits of first-order expressiveness.
Second-Order Logic and Type Theory
Second-order logic extends first-order logic by allowing quantification over predicates and functions. This additional expressiveness allows categorical axiomatizations of many mathematical structures — the natural numbers, the real numbers — that first-order logic cannot capture uniquely. However, second-order logic has no complete proof system: the set of valid second-order formulas is not recursively enumerable.
Type theory provides an alternative foundation for mathematics based on the concept of types rather than sets. In type theory, every mathematical object has a type, and functions are primitive rather than being defined as sets of ordered pairs. The Curry-Howard correspondence identifies types with propositions and programs with proofs, providing a computational interpretation of logic.
Homotopy Type Theory
Homotopy type theory (HoTT) unifies type theory with homotopy theory. In HoTT, types are interpreted as spaces, and the identity type between two elements corresponds to the space of paths between two points. Voevodsky’s univalence axiom states that equivalent types are identical, providing a foundation for mathematics where isomorphic structures can be treated as equal.
HoTT has implications for the foundations of mathematics, computer science, and the formalization of mathematics in proof assistants like Coq and Agda. The connection between type theory and category theory provides a rich framework for understanding mathematical structure.
Proof Theory
Proof theory studies proofs as mathematical objects. The sequent calculus, developed by Gentzen, provides a formal framework for analyzing the structure of proofs. The cut-elimination theorem states that any proof can be transformed into one without the cut rule, making all formulas in the proof subformulas of the conclusion.
Proof theory connects logic to category theory through the Curry-Howard correspondence: proofs correspond to programs, and formulas correspond to types. This correspondence underlies modern type theory and the foundations of programming language semantics.
Categorical Logic
Categorical logic studies the relationship between category theory and logic. A Boolean topos provides a model of higher-order logic with the law of excluded middle. An elementary topos models intuitionistic higher-order logic. The internal language of a topos allows reasoning about objects in the topos as if they were sets.
The Curry-Howard correspondence identifies propositions with types, proofs with programs, and normalization of proofs with evaluation of programs. This correspondence underlies modern type theory and the design of proof assistants like Coq and Lean.
Algebraic Logic
Algebraic logic represents logical systems as algebraic structures. Boolean algebras correspond to classical propositional logic. Heyting algebras correspond to intuitionistic propositional logic. The Lindenbaum-Tarski algebra of a logical system is the quotient of the set of formulas by logical equivalence.
The study of algebraic logic connects logic to universal algebra and category theory. The representation theorems for Boolean and Heyting algebras provide connections between logic, topology, and algebra.
What is the difference between completeness and soundness? Soundness means that every provable formula is true. Completeness means that every true formula is provable. Soundness is easy; completeness is deep.
Can a computer prove mathematical theorems? Yes, within limits. Automated theorem provers can find proofs in restricted domains. But Gödel’s theorems show that no computer can prove all true statements of arithmetic.
What is a Turing machine? A Turing machine is a simple abstract model of computation consisting of a tape, a read/write head, and a finite set of states. Despite its simplicity, it can compute any function that any computer can compute.
How does logic relate to set theory? Set theory provides the mathematical universe in which logical statements are interpreted. Logic provides the proof theory that justifies set-theoretic reasoning.
Set Theory Guide — Mathematical Proof Techniques — Category Theory