Type theory

Lore & Background

Type theory was created to avoid paradoxes in naive set theory and formal logic, such as Russell's paradox, which demonstrates that without proper axioms it is possible to define the set of all sets that are not members of themselves. Between 1902 and 1908, Bertrand Russell proposed various solutions, and by 1908 he arrived at a ramified theory of types together with an axiom of reducibility, both appearing in Whitehead and Russell's Principia Mathematica published in 1910, 1912, and 1913. This system avoided contradictions by creating a hierarchy of types and assigning each concrete mathematical entity to a specific type, preventing an entity from being defined using itself.

Type theory is particularly popular in conjunction with Alonzo Church's lambda calculus. One notable early example is Church's simply typed lambda calculus, which helped the formal system avoid the Kleene–Rosser paradox that afflicted the original untyped lambda calculus. Church demonstrated that it could serve as a foundation of mathematics and it was referred to as a higher-order logic. In the modern literature, 'type theory' refers to a typed system based around lambda calculus. Influential systems include Per Martin-Löf's intuitionistic type theory, proposed as a foundation for constructive mathematics, and Thierry Coquand's calculus of constructions, used as the foundation by Rocq (formerly Coq), Lean, and other computer proof assistants.

Reader's Guide

Type theory is significant as an alternative to set theory for the foundations of mathematics, with examples including Alonzo Church's simple theory of types and Per Martin-Löf's intuitionistic type theory. It underpins many proof assistants, such as Rocq (formerly Coq) based on the calculus of inductive constructions, and Lean based on dependent type theory. The first computer proof assistant, Automath, used type theory to encode mathematics. Type theory also influences programming languages: any static program analysis, such as type checking algorithms in compilers, has a connection to type theory, and the programming language ML was developed for manipulating type theories. In linguistics, type theory is widely used in formal semantics of natural languages, especially Montague grammar and its descendants, with basic types e and t for individuals and truth-values. Gregory Bateson introduced a theory of logical types into the social sciences, based on Russell's theory of types. Type theory is an active area of research, one direction being the development of homotopy type theory, which explores connections between dependent types and algebraic topology.

Did You Know?

• Type theory was created to avoid paradoxes in naive set theory and formal logic, such as Russell's paradox.
• Bertrand Russell proposed a ramified theory of types by 1908, which appeared in Whitehead and Russell's Principia Mathematica.
• The first computer proof assistant, Automath, used type theory to encode mathematics on a computer.
• Type theory is used in formal semantics of natural languages, particularly Montague grammar, with basic types e and t for individuals and truth-values.