Martin-Löf type theory

Martin-Löf type theory
Name	Martin-Löf type theory
Developer	Per Martin-Löf
Introduced	1970s
Paradigm	Constructivism, Intuitionism, Proof theory, Type theory
Influenced by	Ludwig Wittgenstein, Brouwer, Alonzo Church, Bertrand Russell, Kurt Gödel, Per Martin-Löf
Influenced	Homotopy type theory, Coq, Agda, Lean, Isabelle, Idris, NuPRL, Curry–Howard correspondence, Category theory, Dependent type theory

Martin-Löf type theory is a system of formal Type theory developed to formalize constructive mathematics and intuitionistic logic with a direct computational interpretation. It integrates proofs as programs via the Curry–Howard correspondence and supports dependent types to express precise specifications and proofs within a unified calculus. The theory has shaped modern proof assistants, influenced homotopy theory via homotopy type theory, and connects to category theory through semantic models.

History and motivation

Per Martin-Löf introduced the system during the 1970s in response to foundational debates involving Ludwig Wittgenstein, L.E.J. Brouwer, Arend Heyting, Alonzo Church, and Bertrand Russell. Early motivations linked to developments by Gerhard Gentzen in sequent calculus and natural deduction, and to concerns raised by Kurt Gödel and Alan Turing about formalization and computability. Martin-Löf aimed to reconcile constructive intuitionism with a flexible type discipline influenced by Church's lambda calculus, Haskell prototypes, and the lambda calculus work of Alonzo Church and Henk Barendregt. Subsequent dissemination involved collaborations and comparisons with systems such as Automath, NuPRL, Edinburgh Logical Framework, and Girard's System F. Interest from researchers at institutions like Institute for Advanced Study, University of Gothenburg, University of Cambridge, and Carnegie Mellon University helped spread the theory into proof assistant projects such as Coq, Agda, Lean, and Isabelle.

Core syntax and rules

The syntax organizes expressions into terms, types, and judgments resembling rules from natural deduction and sequent calculus. Rules include formation rule, introduction rule, elimination rule, and computation rule families that echo work by Gerhard Gentzen, Dag Prawitz, and Jean-Yves Girard. The calculus features dependent function types (Π-types), dependent pair types (Σ-types), identity types, and universe hierarchies; these design choices parallel constructions in Category theory and inspirations from Per Martin-Löf's earlier work. Typing judgments relate to notions studied by Robin Milner, Dana Scott, John Reynolds, and Gordon Plotkin in programming-language semantics. Structural rules such as weakening, contraction, and exchange mirror principles analyzed by Gerhard Gentzen and Jean-Yves Girard.

Type formers and universes

Martin-Löf type theory formalizes a rich collection of type formers: Π-types (dependent functions), Σ-types (dependent pairs), identity types, finite types, natural numbers, W-types for inductive families, and universes stratified to avoid paradoxes related to Russell's paradox addressed by Bertrand Russell and Errett Bishop. Universe hierarchies reflect ideas from Grothendieck-style universes in algebraic geometry and are related to cumulative universes used in Coq and Agda. Inductive and coinductive types connect to work on recursive types by Dana Scott and Christopher Strachey, while Π and Σ correspond to constructions studied in Category theory by Saunders Mac Lane and Samuel Eilenberg.

Semantics and categorical models

Semantic interpretations draw on category theory including Cartesian closed category, topos theory, locally cartesian closed category, and model category frameworks developed by Quillen. Categorical semantics relate to models by William Lawvere and Lawvere, and to realizability models stemming from Stephen Kleene. Homotopical interpretations leading to homotopy type theory employ constructions inspired by Vladimir Voevodsky, J. Peter May, and Andrei Suslin, while set-theoretic models reference ZF set theory and variations studied by Kurt Gödel and Paul Cohen. Connections to Kripke models and forcing bring in names like Saul Kripke and Paul Cohen.

Computational interpretation and normalization

The computational content follows the Curry–Howard correspondence linking proofs to programs noted by William Alvin Howard and operational semantics explored by Robin Milner and Gordon Plotkin. Reduction strategies and normalization theorems connect to work by Henk Barendregt, Jean-Yves Girard, and Geoffrey Plotkin. Confluence, strong normalization, and decidability of type-checking have been studied in relation to systems like System F and dependently typed implementations in Coq, Agda, and Idris. Extraction of executable code relates to projects at Microsoft Research and contributions from researchers such as Robert Harper and Philip Wadler.

Applications and influence

Martin-Löf type theory underpins many proof assistants including Coq, Agda, Lean, Isabelle, and NuPRL, influencing formalization efforts at institutions like University of Cambridge, Princeton University, Stanford University, and ETH Zurich. It has driven research in homotopy type theory with programs like the Univalent Foundations Program at the Institute for Advanced Study, and applications in formal verification used by industry partners such as Microsoft and Google. Connections to category theory, programming language theory, and constructive mathematics have engaged researchers including Per Martin-Löf, Vladimir Voevodsky, Thierry Coquand, Gordon Plotkin, and Robert Harper.

Variants and extensions

Variants include intensional and extensional presentations, cubical type theories developed by CISPA Helmholtz Center groups and Ahrens, and extensions for higher inductive types central to homotopy type theory championed by Vladimir Voevodsky, Peter LeFanu Lumsdaine, and Michael Shulman. Practical implementations expand with universe polymorphism in Coq and computational cubical models in Cubical Agda and Cubical Type Theory research projects associated with Carnegie Mellon University, University of Gothenburg, and IMDEA researchers. Ongoing work explores connections to modal type theory and linear type theory studied by Gordon Plotkin and Philip Wadler.

Category:Type theory