Mathematics needed a rigorous foundation to avoid paradoxes (like Russell’s paradox) and to formalize what constitutes a valid proof. Natural language proofs were ambiguous and sometimes incorrect.
Mathematical logic uses formal languages with precise syntax and semantics to study mathematical reasoning, proof, and computation. It provides the foundation for computability theory and theoretical computer science.
Mathematical logic consists of:
- Propositional logic — simple true/false statements connected by AND, OR, NOT
- First-order logic — adds quantifiers (∀, ∃) and predicates over objects
- Proof theory — formal systems for deriving theorems
- Model theory — relationships between formal languages and their interpretations
- Recursion theory — what is computable (directly led to computability theory)
Church’s lambda calculus and Turing’s machines both emerged from mathematical logic investigations.
- Soundness — only true statements can be proved
- Completeness — all true statements can be proved (for first-order logic, Gödel proved this)
- Decidability — is there an algorithm to determine if a statement is provable? (answer: no, for first-order logic)
- Builds into: Theory of Computation — computability emerged from logic
- Builds into: Lambda Calculus — logical foundation for functional programming
- Builds into: Turing Machine — Turing’s work was in mathematical logic
- Builds into: Algorithm — formal procedures for computation
- Related: Formal Language Theory — languages defined by logical grammars
- Related: Rice's Theorem — all non-trivial semantic properties are undecidable
- Gödel’s incompleteness theorems — any sufficiently powerful logical system cannot be both consistent and complete
- First-order logic is undecidable (no algorithm can determine truth of arbitrary statements)
- Second-order logic is even more expressive but loses completeness