Simply-typed lambda-calculus; System F polymorphism; Calculus of Constructions; Pi/Sigma/inductive/identity types; universe hierarchy; type-checking decidability; strong normalization; parametricity. Complementary to existing Curry-Howard…
Type Theory
Simply typed lambda calculus
Church 1940 STLC: lambda terms typed by base types and arrows; strongly normalizing; isomorphic to intuitionistic propositional logic via…
System F polymorphism
Girard-Reynolds 1972 second-order lambda-calculus with universal type-quantification; basis for ML-style polymorphism; strong normalization…
Calculus of constructions
Coquand-Huet 1985: dependent types plus higher-order polymorphism; foundation of Coq proof-assistant; expressive enough for full…
Lambda cube (Barendregt)
Barendregt 1991: 8 typed lambda-calculi differing in 3 dependency-axes (terms-on-types, types-on-types, types-on-terms); STLC corner /…
Pi type (dependent product)
Generalizes function-type to Pi(x:A) B(x) where output type may depend on input value; unifies forall-quantifier and dependent function;…
Sigma type (dependent sum)
Generalizes pair-type to Sigma(x:A) B(x); unifies exists-quantifier and dependent record; first-projection extracts witness,…
Inductive type (W-type)
Martin-Lof 1984 W-types: well-founded trees parametrized by family of arities; encodes natural numbers, lists, ordinals; well-founded…
Identity type (Id)
Id_A(x,y) is the type of proofs that x equals y in type A; refl: Id_A(x,x); J-eliminator allows transport along equalities; HoTT gives Id…
Universe hierarchy (Russell)
Russell-style universes Type_0 : Type_1 : Type_2 : ...; avoids Girard-Hurkens paradox of Type:Type; cumulative or non-cumulative variants…
Type checking (decidability)
STLC + System F + MLTT + CoC all admit decidable type-checking (modulo definitional-equality); Lean's elaborator uses bidirectional…
Strong normalization (type theory)
Tait 1967 reducibility-candidates: every well-typed term in STLC / System F / MLTT reduces to a normal form regardless of reduction order;…
Reynolds parametricity
Reynolds 1983: polymorphic functions cannot inspect their type-arguments; gives free theorems (e.g., forall a. a -> a is identity);…
Curry-Howard isomorphism (typed lambda)
Curry 1934 / Howard 1969: types correspond to propositions, terms to proofs, beta-reduction to proof-normalization; foundation of…
Impredicativity + Girard paradox
System U (Girard 1972) with Type:Type is inconsistent (Girard paradox); shows impredicative systems with unrestricted self-reference are…
Propositions-as-types (BHK interpretation)
Brouwer-Heyting-Kolmogorov 1930s constructive interpretation: A and B = pair of proofs; A or B = tagged-union; forall = function; exists =…
Logical Framework (Edinburgh LF)
Harper-Honsell-Plotkin 1987 LF lambda-Pi: meta-language for representing logical systems via dependent types; Twelf implementation; bedrock…
Coq proof assistant (Coquand-Huet)
Coq based on Calculus of Inductive Constructions (CIC); supports impredicative Prop universe + predicative Type hierarchy + inductive…
Agda dependent types (Norell)
Agda based on Martin-Lof type theory; Norell 2007 thesis introduced unicode-friendly syntax + interactive editing; widely used for…
Russell types (1908)
B Russell 1908 type-theory + Principia 1910-1913 Russell-Whitehead; modern modern foundational text + ramified vs simple-type + Church 1940…
Church STT (1940)
A Church 1940 simply-typed-λ-calculus; modern modern foundational text + Hindley-Milner type-inference 1969-1978 + ML-family languages.
System F (Girard-Reynolds 1972)
J-Y Girard 1971 + J Reynolds 1972 polymorphic-System-F; modern modern foundational text + Haskell-System-F + 2024 type-class-overloading.
Martin-Löf (1972)
P Martin-Löf 1972 dependent-types; modern modern foundational text + ITT + Coq + Agda + 2024 cubical-type-theory homotopy.
HoTT univalence (2013)
Voevodsky 2009 + UniMath 2013 HoTT univalence; modern modern foundational text + cubical-CCHM 2018 + 2024 Lean-mathlib + Lean4 ecosystem.
CoC (Coquand 1988)
T Coquand-G Huet 1988 calculus-of-constructions; modern modern foundational + Coq-90s-2024 + 4-color theorem proven Gonthier 2005.