Mathematical Logic

Mathematical logic is the study of reasoning carried out with mathematical precision: formal languages, what they can express, what can be proved in them, and what they can describe.

16 frameworks, from 350 BCE to today · Mathematical Logic · Mathematics

still a working view ended · each leads to its entry below

Overview

Mathematical logic is the study of reasoning carried out with mathematical precision: formal languages, what they can express, what can be proved in them, and what they can describe1. Its practitioners build artificial languages with exact rules, define what counts as a proof, and then ask what those systems can and cannot do1. The stakes are unusually high. Logic is where mathematics examines its own foundations, and several of its results—above all Gödel's incompleteness theorems—changed how mathematicians understand what a formal system can achieve1. This is the story of how a tool for checking arguments became a discipline with its own objects of study: proofs, models, computable functions, and types.

From Aristotle's Syllogistic to Algebraic Logic

Logic begins as a theory of valid argument. Aristotle's Prior Analytics (4th century BCE) set out the syllogistic: patterns of inference built from categorical statements such as "all A are B" and "some A are B," with rules for which conclusions follow23. For over two thousand years this was the dominant framework, taught in universities and refined by medieval logicians, who developed sophisticated theories of terms, modality, and consequence. But syllogistic could not express relations ("every student reads some book") or nest quantifiers, and it treated logic as a catalogue of valid forms rather than a calculus to be manipulated.

The decisive break came in the nineteenth century. George Boole, in The Mathematical Analysis of Logic (1847) and An Investigation of the Laws of Thought (1854), proposed that logical reasoning could be done by algebra: represent propositions by symbols, combine them with operations obeying algebraic laws, and compute4. Augustus De Morgan extended the logic of relations. Later in the century, Charles Sanders Peirce and Ernst Schröder developed a more general algebra of relations1. This algebraic logic recast inference as calculation, and it made logic a subject with theorems rather than merely rules.

Frege, Quantifiers, and the Logicist Programme

Gottlob Frege's Begriffsschrift (1879) is the founding document of modern logic1. Frege introduced a notation for quantifiers—the symbols for "for all" and "there exists"—and with them a logic of predicates that could express relations and nested generality1. He also drew a sharp distinction between an expression and what it refers to, and between a proposition and the assertion of it. Frege's aim was logicism: the thesis that arithmetic is a branch of logic, so that its truths follow from purely logical laws5. In Grundgesetze der Arithmetik (vol. 1, 1893; vol. 2, 1903) he attempted the derivation, using a system with a basic law (Law V) governing the extensions of concepts.

Bertrand Russell's letter to Frege in 1902 pointed out that Law V generates a contradiction—the set of all sets that are not members of themselves—and Frege acknowledged the blow in an appendix to the second volume6. Russell and Alfred North Whitehead responded with Principia Mathematica (1910–1913), a monumental attempt to derive mathematics from logic using a theory of types: a hierarchy in which objects, sets of objects, sets of sets, and so on occupy distinct levels, so that a set can never contain itself178. Logicism in its strong form did not survive, but the work established the notation and standards of rigor that later logic inherited.

Axiomatic Set Theory and the Crisis of Foundations

The paradoxes—Russell's, and earlier the Burali-Forti paradox of the largest ordinal—showed that naive set theory was inconsistent19. Ernst Zermelo's axiomatization of set theory (1908), later extended by Abraham Fraenkel and others into what is now called ZFC, gave set theory a precise foundation: sets exist according to stated axioms, and comprehension is restricted to subsets of already-given sets110. This axiomatic set theory became the standard framework in which mathematics is formalized10. It also opened a research field of its own, but within logic its role was foundational: it supplied the universe of objects that formal theories talk about.

Hilbert's Programme and the Birth of Metamathematics

David Hilbert proposed, in lectures around 1920 and in his 1922 address "Neubegründung der Mathematik," a programme to secure mathematics against the paradoxes. The idea was finitism: to formalize all of mathematics as an axiomatic system, and then prove, using only restricted, "finitary" reasoning that no one could doubt, that the system is consistent and complete111. This required treating proofs themselves as finite combinatorial objects—strings of symbols—and studying them mathematically12. That study, metamathematics or proof theory, was a new discipline: proofs became data13.

Hilbert's school produced substantial results. Wilhelm Ackermann and John von Neumann worked on consistency proofs for fragments of arithmetic14. Paul Bernays collaborated with Hilbert on the Grundlagen der Mathematik (1934, 1939). The programme set the agenda for a generation.

Gödel: Incompleteness and the Limits of Formalism

Kurt Gödel's 1931 paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" destroyed the central hope of Hilbert's programme114. Gödel showed that any consistent formal system strong enough to express basic arithmetic is incomplete: there is a true statement in its language that it cannot prove14. The proof works by arithmetization—encoding statements and proofs as numbers—so that the system can talk about its own provability, and then constructing a sentence that says, in effect, "I am not provable."14 If the system proves it, it is inconsistent; if it does not, the sentence is true but unprovable. A second theorem showed that such a system cannot prove its own consistency14.

The consequences were profound. No single formal system captures all arithmetical truth, and the consistency of a strong system cannot be established within that system14. Hilbert's finitary consistency programme, in its original form, was untenable111. Gödel's work also introduced the technique of arithmetization and the notion of a primitive recursive function, which fed directly into computability theory.

Computability and the Church–Turing Thesis

In 1936, independently, Alonzo Church, Alan Turing, and Emil Post gave precise definitions of what it means for a function to be effectively computable. Church used the lambda calculus, a formal system of functions and application; Turing used abstract machines now called Turing machines; Post used string-rewriting systems. They proved these definitions equivalent, and Church's thesis (the Church–Turing thesis) asserts that they capture the intuitive notion of effective calculability15. Turing's paper also proved the undecidability of the halting problem: no general procedure can decide, for an arbitrary program and input, whether the program will halt116.

Computability theory grew from this117. It studies which sets and functions are decidable or computable, degrees of unsolvability, and reducibilities. Gödel's incompleteness and Turing's undecidability are two faces of the same phenomenon: formal systems and machines have intrinsic limits.

Proof Theory after Gödel

Proof theory did not end with Gödel; it changed direction. Gerhard Gentzen introduced natural deduction and the sequent calculus in the 1930s, systems designed to mirror ordinary reasoning and to make the structure of proofs visible181. In 1936 Gentzen gave a consistency proof for arithmetic using transfinite induction up to a certain ordinal (epsilon-zero), a method that goes beyond finitary reasoning but is still constructive in a broader sense. This founded ordinal analysis: measuring the strength of a formal system by the least ordinal whose well-ordering it cannot prove. Later proof theorists, including Kurt Schütte and others, extended these techniques. Proof theory today also includes proof mining (extracting computational content from proofs) and proof complexity (studying the length of proofs in different systems)112.

Model Theory: Structures and Theories

Where proof theory studies proofs, model theory studies the relationship between formal theories and the structures that satisfy them19. A structure is a set with relations, functions, and distinguished elements; a theory is a set of sentences; a model is a structure in which all sentences of the theory are true. The compactness theorem—a set of sentences has a model if every finite subset does—was proved by Gödel (1930) for countable languages and extended by Anatolii Mal'cev in the 1930s2019. The Löwenheim–Skolem theorems (1915, 1920) show that theories with infinite models have models of various cardinalities, a result with striking consequences: no first-order theory can pin down the natural numbers up to isomorphism.

Alfred Tarski's work in the 1930s and after gave model theory its semantic foundation, including the definition of truth in a structure19. In the 1950s and 1960s, Abraham Robinson developed nonstandard analysis using model-theoretic methods, and the classification theory of Saharon Shelah (from the 1970s) organized theories by the complexity of their models. Model theory became a powerful tool in algebra and geometry, with applications to fields, groups, and valued fields.

Type Theory and the Curry–Howard Correspondence

Russell's type theory was a foundation for mathematics; later type theories became programming languages and proof assistants. Alonzo Church's simply typed lambda calculus (1940) and Per Martin-Löf's intuitionistic type theory (1970s) are central2122. The Curry–Howard correspondence—discovered by Haskell Curry and William Alvin Howard—identifies proofs with programs and propositions with types: a proof of a proposition is a program of the corresponding type23. This correspondence, also called proofs-as-programs, underlies modern proof assistants such as Coq and Agda, and it connects logic, computation, and category theory.

Modal Logic and Categorical Logic

Modal logic extends classical logic with operators for necessity and possibility24. It has ancient roots (Aristotle's modal syllogistic) and a modern flowering: C. I. Lewis's systems in the early twentieth century, Saul Kripke's possible-worlds semantics (1959), and the subsequent development of modal logic as a tool in philosophy, computer science, and linguistics. Kripke semantics gave modal logic a model theory of its own24.

Categorical logic applies category theory to logic25. William Lawvere's work in the 1960s and 1970s showed that theories in logic correspond to categories, and that logical constructions have categorical analogues. Topos theory, developed by Lawvere and Myles Tierney, provides a category-theoretic foundation for mathematics that can model intuitionistic logic. Categorical logic connects logic to algebra, geometry, and computer science.

Constructive and Intuitionistic Logic

Intuitionistic logic, formulated by L. E. J. Brouwer and formalized by Arend Heyting in the 1920s and 1930s, rejects the law of excluded middle (every proposition is either true or false) as a general principle. A proof of "A or B" must exhibit which one holds; a proof of "there exists x such that P(x)" must exhibit such an x. This constructive stance has deep consequences: intuitionistic logic is the internal logic of topoi, the basis of many type theories, and the logic of computation. Its proof theory is particularly well-behaved, and it is the natural logic of the Curry–Howard correspondence1.

Logic and Computation

The twentieth century ended with logic and computer science intertwined. Automata theory, formal languages, and complexity theory all draw on logic. Finite model theory, developed by Boris Trakhtenbrot and others, studies the expressive power of logical languages on finite structures, with direct relevance to databases and verification. Descriptive complexity, pioneered by Ronald Fagin in the 1970s, characterizes complexity classes by the logical languages that define them1. Satisfiability solvers, model checkers, and proof assistants are practical tools built on logical foundations.

The Present

Mathematical logic today is a family of connected research areas. Set theory, model theory, proof theory, computability theory, and type theory each have their own journals, conferences, and open problems. The foundational questions that drove the field—consistency, completeness, the nature of proof—remain, but they are now studied with a rich toolkit: forcing in set theory, stability theory in model theory, ordinal analysis in proof theory, and type-theoretic semantics in computer science. The field's history is one of repeated redefinition: from the syllogism to the quantifier, from the paradoxes to axiomatization, from Hilbert's programme to Gödel's limits, and from logic as a foundation to logic as a computational and mathematical discipline in its own right.

References

  1. Mathematical logic (introduction, 19th century, Set theory and paradoxes, Foundations of mathematics, Symbolic logic, Algorithmically unsolvable problems, Recursion theory, Proof theory and constructive mathematics, Connections with computer science), Wikipedia
  2. Syllogism, Wikipedia
  3. Term logic, Wikipedia
  4. Boolean algebra, Wikipedia
  5. Logicism, Wikipedia
  6. Russell's paradox (introduction, History), Wikipedia
  7. Type theory (History), Wikipedia
  8. Principia Mathematica, Wikipedia
  9. Set theory, Wikipedia
  10. Zermelo–Fraenkel set theory (History, introduction), Wikipedia
  11. Hilbert's program, Wikipedia
  12. Proof theory, Wikipedia
  13. Metamathematics (introduction, History), Wikipedia
  14. Gödel's incompleteness theorems (History, introduction), Wikipedia
  15. Church–Turing thesis, Wikipedia
  16. Halting problem, Wikipedia
  17. Computability theory, Wikipedia
  18. Natural deduction (History), Wikipedia
  19. Model theory (introduction, History), Wikipedia
  20. Compactness theorem (History), Wikipedia
  21. Lambda calculus (History), Wikipedia
  22. Intuitionistic type theory, Wikipedia
  23. Curry–Howard correspondence, Wikipedia
  24. Modal logic, Wikipedia
  25. Categorical logic, Wikipedia

The frameworks of Mathematical Logic

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 350 BCE-1850

    Syllogistic

    Which patterns of inference are valid?

    Fly to its tower in Nousfarer

  2. 1847-1930

    Algebraic Logic

    Can logical reasoning be done by algebraic calculation?

    Fly to its tower in Nousfarer

  3. 1879-1931

    Logicism

    Is arithmetic a branch of logic?

    Fly to its tower in Nousfarer

  4. 1908-Present
  5. 1910-Present

    Type Theory

    How can a hierarchy of types avoid paradox?

    Fly to its tower in Nousfarer

  6. 1920-1931

    Hilbert's program

    Can mathematics be proved consistent by safe means?

    Fly to its tower in Nousfarer

  7. 1920-Present

    Intuitionistic Logic

    What follows from constructive proof alone?

    Fly to its tower in Nousfarer

  8. 1920-Present

    Proof Theory

    What is the structure of a formal proof?

    About Proof Theory
    Proof theory is the branch of mathematical logic that treats proofs themselves as formal mathematical objects. Where model theory asks what a statement means by interpreting it in a structure, proof theory asks how a statement can be derived from axioms using rules of inference. This syntactic perspective makes it possible to study the power and limits of formal systems with mathematical precision. Proof theory emerged from David Hilbert's program to secure the foundations of mathematics, and it has since grown into a rich field with deep connections to computability theory, computer science, and philosophy.
    At its core, proof theory asks: What is a proof? The answer is given by defining proofs inductively from axioms and inference rules. The first systematic formalizations were Hilbert systems—axiomatic calculi with a small number of rules, such as modus ponens. These were the setting for Hilbert's program and for Gödel's incompleteness theorems. But a more natural representation came from Gerhard Gentzen in the 1930s. He introduced natural deduction, where each logical connective has introduction rules (how to prove a formula) and elimination rules (how to use a formula). This mirrors actual mathematical reasoning. He also introduced the sequent calculus, a symmetric system that makes explicit the structural rules of weakening, contraction, and exchange. The sequent calculus is especially powerful because it allows a clean analysis of proofs.
    The central result of structural proof theory is Gentzen's cut elimination theorem (Hauptsatz): any proof that uses the cut rule (a form of transitivity) can be transformed into a cut-free proof. Cut-free proofs have the subformula property—every formula in the proof is a subformula of the conclusion. This makes them easier to analyze. Gentzen used cut elimination to give the first consistency proof for Peano arithmetic, by showing that any proof of a contradiction could be eliminated, using transfinite induction up to the ordinal ε0\varepsilon_0. This launched ordinal analysis, the assignment of proof-theoretic ordinals to theories as a measure of their strength. Other core concepts include provability logic (the modal logic GLGL that captures the provability predicate), reverse mathematics (determining which axioms are needed to prove theorems), and structural proof theory (the study of proof calculi). The concept of analytic proof—a proof that does not rely on hidden lemmas—is central to the field, and normalization is the process of converting a natural deduction proof into a normal form. Proof theory also provides a natural framework for intuitionistic logic, where the constructive content of proofs is made explicit.
    The intellectual history of proof theory begins with Hilbert's program (1900–1931). Hilbert believed that all mathematical truths could be formalized in a complete, consistent system, and that a finitary consistency proof would secure mathematics once and for all. Kurt Gödel's incompleteness theorems (1931) shattered this dream: any consistent system strong enough to encode arithmetic cannot prove its own consistency, and there are true statements it cannot prove. Gentzen responded by developing structural proof theory, showing that consistency could be proved using methods that, while not finitary, were still constructive and transparent. His 1934 paper "Investigations into Logical Deduction" introduced natural deduction and the sequent calculus, and his 1936 consistency proof for arithmetic set the stage for ordinal analysis. Later figures such as Dag Prawitz (normalization), Solomon Feferman (transfinite progressions), and Jean-Yves Girard (linear logic) deepened the structural approach. Proof theory continues to thrive, with applications in automated theorem proving, proof mining, and the analysis of programming languages.
    Proof theory is not a replacement for model theory or computability theory; rather, it complements them. Where model theory studies the semantic interpretation of logical languages, proof theory studies the syntactic structure of derivations. Where computability theory focuses on what can be computed, proof theory focuses on what can be proved and how efficiently. Together, these frameworks give a complete picture of the foundations of mathematics.
    The 10 concepts its tower teaches
    • Consistency proof
    • Cut elimination
    • Hilbert systems
    • Natural deduction
    • Normalization
    • Ordinal analysis
    • Proof-theoretic ordinal
    • Sequent calculus
    • Structural proof theory
    • Subformula property

    Fly to its tower in Nousfarer

  9. 1930-Present

    Model Theory

    Which structures satisfy a given theory?

    Fly to its tower in Nousfarer

  10. 1931-Present
  11. 1936-Present

    Computability Theory

    Which functions can a machine compute?

    Fly to its tower in Nousfarer

  12. 1960-Present

    Logic and Computation

    How does logic underlie computation?

    Fly to its tower in Nousfarer

  13. 1963-Present

    Categorical Logic

    What categorical structure captures logical systems?

    Fly to its tower in Nousfarer

  14. 1969-Present
  15. 1974-Present

    Finite Model Theory and Descriptive Complexity

    What can logical languages express on finite structures?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

SyllogisticAlgebraic LogicLogicismZermelo–Fraenkel set theoryType TheoryModal LogicHilbert's programIntuitionistic LogicProof TheoryModel TheoryIncompleteness and Limitative Metamat…Computability TheoryLogic and ComputationCategorical LogicCurry–Howard CorrespondenceFinite Model Theory and Descriptive C…

Beyond the field

Where Mathematical Logic's ideas came from in other fields, and what they led to there: the strongest 12 of 208 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Mathematical Logic is a planet in Nousfarer

Its city has a tower for each of these 16 frameworks. Land, walk in, and climb one concept at a time.

Land on Mathematical Logic

Related fields

Fields its ideas are linked to

More in Mathematical Logic

See where Mathematical Logic sits on the Map of Human Knowledge