# Dependent type

A dependent type is a type whose definition depends on a value: a family of types B indexed by terms x : A, so that for each different a : A the instance B(a) may be a genuinely different type. Such a family is best thought of as a function from terms of type A to types, and it is the central feature distinguishing dependent type theories such as [Martin-Löf type theory](https://www.edgepedia.org/martin-lof-type-theory) from simply typed systems.<sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup>

| Key fact | Detail |
|---|---|
| Definition | A family of types B indexed by terms x : A; for each a : A, B(a) may be a distinct type<sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup> |
| Dependent function type | \( \Pi_{x:A} B \): functions that, given a : A, return a term of type B[x ↦ a]; when B does not depend on x it reduces to A → B<sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup> |
| Dependent pair type | \( \Sigma_{x:A} B(x) \): pairs (a, b) with a : A and b : B(a); when B does not depend on x it reduces to A × B<sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup> |
| Logical reading | Under propositions-as-types, Π behaves like ∀ and Σ like ∃; a predicate such as Prime(x) becomes the type of proofs that x is prime<sup>[2](https://math.berkeley.edu/~forte/notes/type_theory.pdf)</sup><sup> • </sup><sup>[3](https://plato.stanford.edu/entries/type-theory-intuitionistic/)</sup> |
| Canonical example | Length-indexed vectors: Vec t n is a distinct type for each n, and concatenation of a length-m and a length-n vector is declared to return a vector of length m + n<sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup><sup> • </sup><sup>[4](https://www.funcp.org/wiki/dependent-type)</sup> |
| Origin | Per Martin-Löf's 1972 paper "An intuitionistic theory of types" presented the theory as a full-scale system for formalizing intuitionistic mathematics<sup>[5](https://archive-pml.github.io/martin-lof/pdfs/An-Intuitionistic-Theory-of-Types-1972.pdf)</sup> |
| Languages | Agda, Rocq (formerly Coq), Lean, and Idris are dependently typed languages and proof assistants<sup>[6](https://agda.readthedocs.io/en/latest/getting-started/what-is-agda.html?highlight=instance)</sup><sup> • </sup><sup>[7](https://lean-lang.org/doc/reference/latest/)</sup> |

## The two basic type formers

**Dependent function types (Π).** Given a type A and a type B(x) for every x : A, the type \( \Pi_{x:A} B(x) \), read "pi-type", contains dependent functions: a term f of this type returns, for each input a : A, a result whose type is specifically B[a/x]. Defining such an f is equivalent to defining a term f(x) : B(x) for every x : A. When B does not actually depend on x, the type collapses to the ordinary function type A → B, so Π strictly generalizes the arrow.<sup>[2](https://math.berkeley.edu/~forte/notes/type_theory.pdf)</sup><sup> • </sup><sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup>

**Dependent pair types (Σ).** Given the same data, the type \( \Sigma_{x:A} B(x) \), read "sigma-type", contains pairs (a, b) where a : A and b : B(a); the type of the second component depends on the value of the first. When B does not depend on x, \( \Sigma_{x:A} B \) is just A × B, so Σ generalizes the ordinary pair type the same way Π generalizes →.<sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup>

Each former carries a standard set of inference rules: a formation rule building the type from A and the family B, an introduction rule (λ-abstraction for Π, pairing for Σ), an elimination rule (application for Π, induction on pairs for Σ), and computation rules such as \( (\lambda x.\, b)(a) \equiv b[a/x] \).<sup>[2](https://math.berkeley.edu/~forte/notes/type_theory.pdf)</sup>

## Interpretations

The same syntax supports three standard readings, which is a large part of the concept's usefulness:<sup>[2](https://math.berkeley.edu/~forte/notes/type_theory.pdf)</sup>

- **Sets.** \( \Pi_{x:A} B(x) \) is the product of the family of sets B(x) indexed by x : A, and \( \Sigma_{x:A} B(x) \) is its disjoint union.<sup>[2](https://math.berkeley.edu/~forte/notes/type_theory.pdf)</sup>
- **Spaces.** Π is the space of sections of a fibration with base space A and fiber B(x); Σ is the total space of that fibration.<sup>[2](https://math.berkeley.edu/~forte/notes/type_theory.pdf)</sup>
- **Propositions.** Π is a universal quantifier, so a term of \( \Pi_{x:A} B \) is a proof of ∀x : A, B(x); Σ is an existential quantifier, so a term of \( \Sigma_{x:A} B \) is a proof of ∃x : A, B(x).<sup>[2](https://math.berkeley.edu/~forte/notes/type_theory.pdf)</sup>

The [Stanford Encyclopedia of Philosophy](https://www.edgepedia.org/stanford-encyclopedia-of-philosophy) describes intuitionistic type theory as having primitive type formers Σ and Π for general sums and products, plus identity types, which are themselves dependent: the identity type \( \mathrm{I}(\mathbb{N}, m, n) \) depends on the elements m, n : ℕ, making it an indexed family of types.<sup>[3](https://plato.stanford.edu/entries/type-theory-intuitionistic/)</sup>

## Computation in types

Dependent types can be defined by primitive recursion, and the defining equations are computation rules. The type of n-tuples A<sup>n</sup>, indexed by n : ℕ, is given by \( A^0 = 1 \) and \( A^{n+1} = A \times A^n \), where 1 is a one-element type; from these rules one can compute, for example, \( A^3 = A \times (A \times (A \times 1)) \).<sup>[3](https://plato.stanford.edu/entries/type-theory-intuitionistic/)</sup> This is what lets a function's result type be computed from its arguments, so that vector concatenation of lengths m and n is declared to return length m + n.<sup>[4](https://www.funcp.org/wiki/dependent-type)</sup>

## Propositions as types

Under the Curry-Howard interpretation, predicates become dependent types: the predicate Prime(x) becomes the type of proofs that x is prime, and x < y becomes the type of proofs that x is less than y.<sup>[3](https://plato.stanford.edu/entries/type-theory-intuitionistic/)</sup> A concrete example is the proposition that there are arbitrarily large primes, which becomes the type \( \Pi m{:}\mathbb{N}.\ \Sigma n{:}\mathbb{N}.\ m < n \times \mathrm{Prime}(n) \): a function mapping each number m to a triple (n, (p, q)) where p proves m < n and q proves that n is prime. A [constructive proof](https://www.edgepedia.org/constructive-proof) of the proposition is therefore a program that, given any number, produces a larger prime together with the two proofs; this is the proofs-as-programs principle. The classical proof by contradiction that assumes a largest prime is not constructive, since it does not compute a larger prime.<sup>[3](https://plato.stanford.edu/entries/type-theory-intuitionistic/)</sup>

**Refinement types.** A [refinement type](https://www.edgepedia.org/refinement-type) is a subtype formed from its supertype by a value-based restriction. The positive naturals can be written \( \Sigma_{n:\mathrm{Nat}} (n > 0) \), a pair of a number together with a proof that it is positive. This reading only makes sense once a proposition such as n > 0 is allowed to appear as a type.<sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup>

## Programming with dependent types

The canonical programming example is the length-indexed vector: Vec t n is a distinct type for each natural number n, representing vectors of exactly that length. Operations then carry precise types, for instance head : \( \Pi_{n:\mathrm{Nat}} (\mathrm{Vec}\ t\ (n+1) \to t) \), defined only on nonempty vectors.<sup>[1](https://cs.lmu.edu/~ray/notes/typetheory/)</sup> Since a vector's length forms part of its type, appending a length-m vector to a length-n vector can be given a result type specifying length m + n.<sup>[4](https://www.funcp.org/wiki/dependent-type)</sup>

Several languages build programs around this idea. Agda is a dependently typed programming language, an extension of Martin-Löf's type theory, that can be used as a proof assistant, allowing one to prove theorems in a constructive setting and run such proofs as algorithms.<sup>[6](https://agda.readthedocs.io/en/latest/getting-started/what-is-agda.html?highlight=instance)</sup> Lean is an interactive theorem prover based on dependent type theory, designed for both cutting-edge mathematics and software verification, and is also a pure functional programming language.<sup>[7](https://lean-lang.org/doc/reference/latest/)</sup> Idris is a general-purpose language with full dependent types, closely related to Epigram and Agda, in which types are predicated on values so that aspects of a program's behavior can be specified precisely in the type; its newer incarnation promotes type-driven development, treating the type as the plan for a program.<sup>[8](https://idris-hackers.github.io/idris-doc/)</sup><sup> • </sup><sup>[9](https://idris-lang.org/)</sup> Rocq (formerly Coq) is likewise described both as an expressive functional programming language with dependent types and as a proof assistant for mechanized interactive theorem proving.<sup>[10](https://rocq-prover.org/docs)</sup>

## Decidability and practical restrictions

Full generality has a price: type checking is undecidable in systems where "Type" is a type, that is, where there is a type of all types including itself.<sup>[11](https://dspace.mit.edu/entities/publication/8b2db262-e703-4b1e-b19a-7044efa612d5)</sup> Practical systems manage this in two ways. When programming functionally, the index objects belonging to type families come from a constraint domain that can be handled efficiently—for example, integer linear equalities and inequalities; Hongwei Xi and Frank Pfenning, a programming-language researcher at [Carnegie Mellon University](https://www.edgepedia.org/carnegie-mellon-university), applied this approach in their 1999 POPL paper "Dependent types in practical programming".<sup>[12](https://www.cs.cmu.edu/~fp/courses/15312-f04/lectures/27-dependent.html)</sup><sup> • </sup><sup>[13](https://dblp.uni-trier.de/rec/conf/popl/XiP99.html)</sup> In logical frameworks, decidability is preserved by restricting to the pure lambda calculus, in which type checking remains decidable.<sup>[12](https://www.cs.cmu.edu/~fp/courses/15312-f04/lectures/27-dependent.html)</sup>

## History

The theory was presented by [Per Martin-Löf](https://www.edgepedia.org/per-martin-lof), a Swedish logician then at the University of Stockholm, in the 1972 paper "An intuitionistic theory of types", intended as a full-scale system for formalizing intuitionistic mathematics in the tradition of Bishop. The paper notes an earlier, not yet conclusive attempt at formulating such a theory by [Dana Scott](https://www.edgepedia.org/dana-scott) in 1970, and related type-free theories of constructions by Kreisel and Goodman. Howard's 1969 proposed axioms are special cases of the existential elimination rule of the theory.<sup>[5](https://archive-pml.github.io/martin-lof/pdfs/An-Intuitionistic-Theory-of-Types-1972.pdf)</sup> Later extensions with primitive identity types, well-founded tree types, universe hierarchies, and general inductive and inductive-recursive definitions increased the proof-theoretic strength of the theory and made it more convenient for programming and formalization of mathematics.<sup>[3](https://plato.stanford.edu/entries/type-theory-intuitionistic/)</sup>

## References

1. [Notes on Type Theory, LMU (Ray Toal)](https://cs.lmu.edu/~ray/notes/typetheory/)
2. [Introduction to Type Theory, UC Berkeley lecture notes](https://math.berkeley.edu/~forte/notes/type_theory.pdf)
3. [Intuitionistic Type Theory, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/type-theory-intuitionistic/)
4. [Dependent type, The Functional Programmer wiki](https://www.funcp.org/wiki/dependent-type)
5. [Per Martin-Löf (1972). An Intuitionistic Theory of Types](https://archive-pml.github.io/martin-lof/pdfs/An-Intuitionistic-Theory-of-Types-1972.pdf)
6. [What is Agda?, Agda User Manual](https://agda.readthedocs.io/en/latest/getting-started/what-is-agda.html?highlight=instance)
7. [The Lean Language Reference](https://lean-lang.org/doc/reference/latest/)
8. [idris](https://idris-hackers.github.io/idris-doc/)
9. [Idris: A Language for Type-Driven Development](https://idris-lang.org/)
10. [Learn Rocq, Rocq documentation](https://rocq-prover.org/docs)
11. [Typechecking is Undecidable when 'Type' is a Type, MIT DSpace](https://dspace.mit.edu/entities/publication/8b2db262-e703-4b1e-b19a-7044efa612d5)
12. [15-312 Foundations of Programming Languages, Lecture 27: Dependent Types, Carnegie Mellon University](https://www.cs.cmu.edu/~fp/courses/15312-f04/lectures/27-dependent.html)
13. [Hongwei Xi and Frank Pfenning (1999). Dependent Types in Practical Programming, POPL 1999, dblp](https://dblp.uni-trier.de/rec/conf/popl/XiP99.html)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Logical calculi and logical syntax › Lambda calculus and type theory › Dependent type theory and Martin-Löf type theory*

*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license