Type Theory

Type theory began as a way to repair a crack in the foundations of mathematics, and it became something much larger: a language in which logic, computation, and the structure of mathematical objects are studied as one subject.

10 frameworks, from 1908 to today · Mathematical Logic · Mathematics

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

Overview

Type theory began as a way to repair a crack in the foundations of mathematics, and it became something much larger: a language in which logic, computation, and the structure of mathematical objects are studied as one subject1. Its central idea is simple to state. Every expression is assigned a type—a label that says what kind of thing it is—and the rules of the system only let you combine expressions whose types fit together1. A function that expects a number cannot be applied to a sentence. This sounds like bookkeeping, but the bookkeeping turns out to encode deep information: which constructions are legitimate, which proofs are valid, and which programs will run without going wrong.

What is at stake is the relationship between three things that were once studied separately. In type theory, a proposition can be a type, a proof of it can be a program of that type, and simplifying that program can be the same act as checking the proof. This is why type theory sits at the crossroads of mathematical logic, the theory of programming languages, and the foundations of mathematics, and why it has repeatedly been reinvented by people coming from each of those directions.

Repairing the Foundations: Russell's Ramified Types

The story starts with a paradox. In 1901 Bertrand Russell found that the naive principle "every property determines a set" leads to contradiction: consider the set of all sets that are not members of themselves12. If it is a member of itself, it is not; if it is not, it is. Russell's Principia Mathematica, written with Alfred North Whitehead and published in three volumes from 1910 to 1913, responded with a ramified theory of types1. Objects were arranged in a hierarchy of levels, and a property could only quantify over objects of lower levels1. This blocked the paradox by forbidding the self-reference that generated it1.

The price was severe. The hierarchy was so fine-grained that ordinary mathematical objects, such as the real numbers, could not be defined at a single level, and Russell had to add an axiom of reducibility to collapse the levels back to something workable13. That axiom was widely felt to be an ad hoc patch, and it undercut the claim that mathematics rested on pure logic. The ramified theory was historically decisive but mathematically awkward, and later type theories largely abandoned its stratification.

Simple Types and the Lambda Calculus

A cleaner response came from splitting the problem in two. In the 1920s and 1930s, Frank Ramsey and others observed that the paradoxes came in two flavours: logical ones, which a simple hierarchy of individuals, properties of individuals, properties of properties, and so on could handle, and semantic ones such as "heterological," which needed more care. The simple theory of types kept only the coarse hierarchy and dropped ramification45. It was enough to avoid the set-theoretic paradoxes while allowing mathematics to be developed naturally.

In parallel, Alonzo Church developed the lambda calculus in the 1930s as a formal system for functions and their application6. The untyped lambda calculus was powerful enough to express all computable functions, but it was also inconsistent as a logic: the self-application that made it expressive also allowed paradoxes. Church's typed lambda calculus, presented in 1940, restricted application so that a function could only take arguments of the appropriate type67. The result was a system in which every well-typed term has a normal form—a canonical simplified value—so computation always terminates. This was the first clear demonstration that typing disciplines computation.

Propositions as Types: The Curry–Howard Correspondence

The next turning point revealed that these two projects were the same project. In the 1930s Haskell Curry noticed a formal resemblance between the axioms of implicational logic and the type schemes of combinatory logic89. In 1969 William Alvin Howard made the connection precise: a proof of a proposition corresponds to a program of a type, and simplifying the proof corresponds to running the program. The Curry–Howard correspondence (also called propositions-as-types) says that logic and computation are two readings of one formal system8.

A concrete case makes it vivid. A proof of "if A then B" is a function that takes a proof of A and returns a proof of B. A proof of "A and B" is a pair consisting of a proof of A and a proof of B. A proof of "A or B" is a tagged value saying which one holds and carrying its proof. Under this reading, the rules for building proofs are exactly the typing rules for a programming language, and the fact that a program cannot get stuck corresponds to the fact that a proof cannot go wrong. Curry–Howard gave type theory a unifying interpretation that later systems would exploit directly.

Intuitionistic Type Theory: Martin-Löf's Dependent Types

The decisive modern step was taken by Per Martin-Löf in the early 1970s10. His intuitionistic type theory introduced dependent types: types that can depend on values9. Instead of a single type "list of numbers," one can have a family of types indexed by a length, so that a list of length three has a different type from a list of length four. This made it possible to express precise specifications inside the type system itself—a sorting function could be given a type guaranteeing that its output is ordered and has the same elements as its input.

Martin-Löf's system was also a foundation for constructive mathematics110. It treated proofs as objects and built logic out of types rather than adding types to a pre-existing logic1. The system went through several revisions, and its treatment of identity—the type of proofs that two things are equal—became a central and contested topic. Martin-Löf distinguished judgmental equality, which is equality built into the rules, from propositional equality, which is a type whose inhabitants are proofs that two terms are equal1. This distinction would later become the seed of homotopy type theory.

Polymorphism and Inference: System F and Hindley–Milner

While logicians were building foundations, computer scientists were building languages, and they arrived at type theory from the other side. In 1971 Jean-Yves Girard, and independently in 1974 John Reynolds, introduced what is now called System F: the polymorphic lambda calculus. Polymorphism means that a single function can work uniformly at many types. The identity function, for example, can be given the type "for every type α, α $\rightarrow $ α," meaning it takes a value of any type and returns a value of that same type11. System F was strong enough to encode a great deal of mathematics, and Girard used it to prove a major result in proof theory, but its full power also made type inference undecidable.

A more practical compromise came from Roger Hindley in 1969 and Robin Milner in 1978. The Hindley–Milner type system allowed polymorphism but restricted it so that the most general type of an expression could always be computed automatically12. This made possible languages in which programmers write code without type annotations and the compiler infers the types12. Milner's work fed directly into ML, the language family that includes OCaml and influenced Haskell, and Hindley–Milner inference remains one of the most successful ideas in programming-language design.

The Calculus of Constructions and the Logical Framework

The 1980s saw an effort to unify the strands. Thierry Coquand and Gérard Huet introduced the Calculus of Constructions in 1988, a system that combined dependent types, polymorphism, and higher-order functions in a single framework. It was powerful enough to serve as a foundation for mathematics and as a programming language at once13. The Coq proof assistant, developed from the late 1980s onward, was built on this tradition, and it became a tool for machine-checked proofs of substantial theorems, including the formal verification of the four-colour theorem and later the CompCert compiler.

The Calculus of Constructions belongs to a family sometimes called the lambda cube, which classifies type systems by which kinds of dependency they allow14. Its practical importance was that it showed type theory could be a working environment for mathematics and software verification, not only a foundational curiosity.

Homotopy Type Theory: Types as Spaces

The most recent major development began with a surprise. In 2006, Vladimir Voevodsky, a mathematician working in algebraic geometry and homotopy theory, noticed that Martin-Löf's identity types behaved like paths in a space. A proof that two points are equal is like a path between them; a proof that two paths are equal is like a homotopy between paths; and the structure continues upward. This observation, developed with collaborators, became homotopy type theory1516.

The key new idea was the univalence axiom, which says that equivalent types can be treated as identical1. In ordinary mathematics, two structures that are isomorphic are not literally the same object, but univalence makes the type theory respect the practice of identifying isomorphic structures. Homotopy type theory was presented in a collaborative book, Homotopy Type Theory: Univalent Foundations of Mathematics, released in 2013. It offered a new foundation for mathematics in which types are spaces and equality is path structure, and it connected type theory to higher category theory and homotopy theory.

Cubical Type Theory: Making Univalence Compute

Univalence as originally formulated was an axiom, and axioms do not compute. A proof that used univalence could not be run as a program, which limited its usefulness in proof assistants. Cubical type theory, developed in the mid-2010s by Cyril Cohen, Thierry Coquand, Simon Huber, Anders Mörtberg, and others, gave a computational interpretation of univalence using cubical sets—geometric objects built from cubes—as the model. In cubical type theory, the univalence principle is not an axiom but a consequence of the rules, so proofs involving it can be evaluated17. This made homotopy type theory usable in practice and led to proof assistants such as Cubical Agda.

The Present: Many Foundations, One Field

Type theory today is not one system but a family of systems serving different purposes. On the foundational side, dependent type theory in the Martin-Löf tradition, extended by homotopy and cubical ideas, is an active alternative to set theory as a foundation for mathematics, and proof assistants such as Coq, Agda, and Lean put it to work on real theorems. On the computational side, Hindley–Milner inference and its descendants underpin statically typed programming languages, while System F and its variants inform the design of polymorphic languages1112. The Curry–Howard correspondence remains the conceptual bridge, read now through dependent types and equality8.

Open questions remain. The computational behaviour of univalence is still being worked out in full generality, and the relationship between homotopy type theory and classical homotopy theory is an active research area. The design of type theories that are both expressive and practical—strong enough for mathematics, usable by programmers—continues to drive new systems. And the old question of what a foundation should be, which sent Russell looking for types in the first place, is still being answered in new ways.

References

  1. Type theory (introduction, History, Constructive mathematics, Intuitionistic logic, Judgments, Identity type, Axioms), Wikipedia
  2. Axiom of reducibility (History), Wikipedia
  3. Principia Mathematica (Ramified types and the axiom of reducibility), Wikipedia
  4. Higher-order logic, Wikipedia
  5. History of type theory (Theory of simple types), Wikipedia
  6. Lambda calculus (introduction, History), Wikipedia
  7. Simply typed lambda calculus, Wikipedia
  8. Curry–Howard correspondence (Origin, scope, and consequences, introduction), Wikipedia
  9. Dependent type (History, introduction), Wikipedia
  10. Intuitionistic type theory, Wikipedia
  11. System F, Wikipedia
  12. Hindley–Milner type system, Wikipedia
  13. Calculus of constructions, Wikipedia
  14. Lambda cube, Wikipedia
  15. Homotopy type theory, Wikipedia
  16. Univalent foundations, Wikipedia
  17. Cubical type theory, Wikipedia

The frameworks of Type Theory

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

  1. 1908-1930

    Ramified Theory of Types

    How can self-reference be avoided in logic?

    Fly to its tower in Nousfarer

  2. 1925-1960

    Simple Theory of Types

    What hierarchy of types avoids paradox?

    Fly to its tower in Nousfarer

  3. 1940-Present

    Typed Lambda Calculus

    How do types discipline function application?

    Fly to its tower in Nousfarer

  4. 1969-Present
  5. 1969-Present

    Hindley–Milner Type System

    How can types be inferred automatically?

    Fly to its tower in Nousfarer

  6. 1971-Present
  7. 1971-Present

    System F

    How can functions work uniformly at many types?

    Fly to its tower in Nousfarer

  8. 1988-Present

    Calculus of Constructions

    How can dependent types and polymorphism be unified?

    Fly to its tower in Nousfarer

  9. 2006-Present

    Homotopy Type Theory

    What is the structure of equality in type theory?

    About Homotopy Type Theory
    Homotopy type theory (HoTT) rethinks the very notion of identity in type theory. In earlier frameworks, two terms of a type were either equal or not—a simple yes-or-no question. HoTT, emerging from the 2006–2026 period, treats identity as a structure. A proof that two terms are equal is interpreted as a path between points in a space; the type of such proofs itself has higher-dimensional structure, with paths between paths, and so on. This geometric perspective transforms type theory from a logic of static propositions into a logic of spaces and continuous deformations, opening new foundations for mathematics and new tools for formalization.
    At the core of a first course in HoTT lie several interconnected concepts. The curriculum begins with identity types (IdA(a,b)\text{Id}_A(a,b)), which internalize equality as a type whose terms are proofs that aa and bb are equal. The key insight is that these types can be iterated: given two proofs p,q:IdA(a,b)p,q : \text{Id}_A(a,b), one can form IdIdA(a,b)(p,q)\text{Id}_{\text{Id}_A(a,b)}(p,q), and so on. This tower of identity types gives every type a higher-dimensional structure. Next comes the homotopy interpretation: types are viewed as spaces, terms as points, and identity proofs as paths. This leads to the univalence axiom, a signature principle of HoTT. Univalence states that equivalence of types is equivalent to identity: (A≃B)≃(A=B)(A \simeq B) \simeq (A = B). In practical terms, isomorphic structures can be treated as identical, a powerful principle for formalizing mathematics. The curriculum then develops higher inductive types, which allow the direct construction of spaces (like the circle S1S^1 or the sphere S2S^2) by specifying their points and paths. These are complemented by dependent types (dependent sums Σ\Sigma and dependent products Π\Pi), carried over from Martin-Löf type theory, which now gain geometric meaning. The homotopy hypothesis—that types behave like weak ω\omega-groupoids—provides a unifying bridge between type theory and homotopy theory. Students learn to work with contractibility, connectedness, and truncation levels (e.g., sets are 0-truncated, propositions are (−1)(-1)-truncated). The structure identity principle formalizes how univalence applies to algebraic structures. Finally, the formalization of mathematics in proof assistants like Coq, Agda, and Lean is a practical thread throughout the curriculum, showing how HoTT enables new, more natural encodings of classical mathematics.
    The intellectual history of HoTT begins in the early 2000s. The first higher-dimensional models of intensional type theory were constructed by Steve Awodey and Michael Warren in 2005, using Quillen model categories from homotopy theory. Awodey coined the term "homotopy type theory" in a 2007 talk. Independently, Vladimir Voevodsky was developing a type-theoretic foundation for formalizing mathematics, and in 2006 he sketched a "homotopy λ\lambda calculus" with a model in Kan simplicial sets. Voevodsky's key contribution was the univalence axiom, which he introduced around 2009. The coherence problems that plagued early models were solved by Voevodsky (2009) and later by Peter Lumsdaine and Warren (2014). The seminal work that crystallized the field is the book Homotopy Type Theory: Univalent Foundations of Mathematics (2013), produced by the Univalent Foundations Program at the Institute for Advanced Study. This book, written collaboratively by over two dozen researchers, remains the canonical textbook. HoTT builds directly on Intuitionistic Type Theory (Martin-Löf, 1971–present) and the Curry-Howard Correspondence, but it adds a geometric layer that earlier frameworks lacked. It coexists with the Calculus of Constructions (Coquand and Huet, 1986–present) as a foundation for proof assistants, but HoTT's univalence and higher inductive types offer a different approach to formalization. The field remains active, with ongoing work on cubical type theories, synthetic homotopy theory, and the formalization of advanced mathematics.
    The 10 concepts its tower teaches
    • Contractibility and connectedness
    • Dependent types
    • Formalization of mathematics
    • Higher inductive types
    • Homotopy hypothesis
    • Homotopy interpretation
    • Identity types
    • Structure identity principle
    • Truncation levels
    • Univalence axiom

    Fly to its tower in Nousfarer

  10. 2014-Present

    Cubical Type Theory

    How can equality be made computational?

    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.

Ramified Theory of TypesSimple Theory of TypesTyped Lambda CalculusCurry–Howard CorrespondenceHindley–Milner Type SystemIntuitionistic Type TheorySystem FCalculus of ConstructionsHomotopy Type TheoryCubical Type Theory

Beyond the field

Where Type Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 61 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.

Type Theory is a planet in Nousfarer

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

Land on Type Theory

Related fields

Fields its ideas are linked to

More in Mathematical Logic

See where Type Theory sits on the Map of Human Knowledge