natural deduction metalanguage, practical foundations
type theory (dependent, intensional, observational type theory, homotopy type theory)
computational trinitarianism =
propositions as types +programs as proofs +relation type theory/category theory
A type theory with both type variables (i.e. polymorphic type theory) and, for any type , variables of terms of type (i.e. dependent type theory).
Traditionally, there are two different ways to present dependent type theory:
One can present dependent type theory with a hierarchy of type universes such that every type is a term of a universe of the hierarchy. Examples of such dependent type theories include the one found in the HoTT book and the proof assistants Agda, Rocq, Lean, and its variants like Cubical Agda.
Alternatively, one can present dependent type theory with a separate type judgment and no type universes at all. Examples of such dependent type theories include the one found in Egbert Rijke‘s Introduction to Homotopy Type Theory.
In the first presentation of dependent type theory, the concept of a “-small type variable” exists: since types are terms of universes, type variables are term variables where the context is extended by a free variable of a universe. Thus, the type theory is polymorphic in the sense that it has -small polymorphism for all universe in the universe hierarchy.
In the second presentation of dependent type theory, the theory does not come with the concept of a type variable, since the context can only be extended by term judgments, and not type judgments. While this is sufficient to define univalent universes and higher inductive types in the type theory, there are a few reasons why one might want to extend dependent type theory with type variables to form polymorphic dependent type theory:
Large elimination principles of inductive types and higher inductive types are principles where given some existing data one can construct a type family indexed by the inductive type . Type variables are important for large recursive principles in many ways:
The concept of impredicative polymorphism can be implemented as applying to the entire type theory, rather than to a single universe. Impredicative polymorphism is important for:
defining axioms such as UIP, excluded middle, the axiom of replacement and the axiom of choice as actual axioms rather than unjustified rules. Axioms involving type families can be represented using an auxiliary type and a function to the index type, where the type family itself is represented by the fiber types of the function.
defining impredicative structures in dependent type theory, such as frames, Cauchy complete spaces, Grothendieck topoi, the type of all propositions, etc.
With type variables, one can define identity types between types and . This has a few benefits:
With identity types between types, it is possible to define the univalence axiom and thus make the type theory a univalent type theory without requiring universes in the type theory. This is important since the univalence axiom implies the large elimination principles discussed in the previous point.
In a dependent type theory without judgmental equality, such as objective type theory, it is cumbersome to define or explicitly convert types in terms of other types, since one has to equip each definition or explicit conversion with the structure of an equivalence of types. With identity types between types, one can simply make use of an identification between types to represent definitional equality or explicit conversion.
The same goes with the weak large eliminaiton principles: in the absence of either judgmental equality or identity types between types, the computation rules associated with large eliminaiton principles state that one can construct an equivalence of types between certain types given in the elimination rules of the large elimination principles. With identity types between types, one can simply make use of an identification between types.
Polymorphic dependent type theory with type variables is thus similar to System F, which is a non-dependent polymorphic lambda calculus with type variables.
We assume dependent type theory with context judgments , type judgments , and term judgments and the usual context-creating rules and structural rules for the dependent type theory.
To extend the above theory with type variables, we add the following rule
which states that it is possible to extend the context by a type judgment, and the following rule
which states that we may derive a type judgment if the type judgment is already in the context.
It is conjectured in the Category Theory Zulip that the substitution rules and weakening rules for type variables are admissible rules.
If the type theory has additional judgments and for judgmental equality of terms and judgmental equality of types respectively and the associated structural rules for judgmental equality, then the corresponding rules for judgmental equality involving type variables (i.e. substitution is a congruence, variable conversion, etc) should also be admissible rules.
In the presentation of dependent type theory using a hierarchy of universes, impredicative polymorphism is a resizing axiom which says that for all endofunctions on the first type universe , the dependent product type is (essentially) -small.
In the presentation of dependent type theory without universes but with a separate type judgment, while there is no universe to quantify over for the dependent product type, using the type variable we can add an untyped version of the dependent product type to the type theory. This type is similar to universal quantification in untyped first-order logic, and plays the same role in this presentation of dependent type theory that the type does for the other presentation of dependnet type theory. The rules for are as follows:
Formation rule:
Introduction rule:
Elimination rule:
Computation rules:
Uniqueness rules:
Impredicative polymorphism is important for defining the impredicative universe of propositions as a positive type via the higher inductive type formulation as the initial frame or complete Heyting algebra.
Type variables allow for the formation of identity types between types.
If the dependent type theory has impredicative polymorphism, then the contexts can be removed from the elimination and computation rules of the identity types between types, simplifying the rules down to the following:
There are many consequences of having identity types between types in the dependent type theory. One such example is that any time one uses an equivalence of types in a definition, such as weak Tarski universes or typal large elimination principles for inductive types, one can instead use identity types between types in the definition. In addition, one can add univalence to the dependent type theory itself, which makes the identity types between types and equivalence types coincide with each other.
The univalence axiom states that the function
inductively defined by
is an equivalence of types for all types and ,
where is the identity function on the type . In impredicative polymorphism, this is given by the following axiom:
Unlike the other presentation of dependent type theory in terms of universes, in this presentation of dependent type theory with a type judgment and type variables, it is consistent to assume both the univalence axiom and an axiom of set truncation like UIP or axiom K, since here there is no universe, provided one doesn’t have any higher types, such as the circle type.
In the usual dependent type theory without type variables, there are strict and weak versions of large elimination principles: the strict large elimination principles use judgmental equality between types for the computation and uniqueness rules, while the weak large elimination principles use equivalences of types for the computation and uniqueness rules. For example, the strict large elimination principle for the type of booleans says that given types and , one can construct a type family such that
and the weak large elimination principle for the type of booleans says that the type family above comes with equivalences of types
However, with type variables and identity types between types, one can also use identifications of types instead of equivalences of types to express weak large elimination of the type of booleans:
This third notion of weak large elimination in dependent type theory with a single type judgment and type variables parallels the third notion of weak large elimination in the other formulation of dependent type theory involving a hierarchy of universes.
Independently of the consequences of having identity types between types, having type variables allows for the formulation of certain large elimination principles which are not possible in the dependent type theory with a single type judgment but no type variables. These include large elimination for recursive inductive types and recursive higher inductive types such as the natural numbers type, W-types, and localizations of a type.
For example, the usual recursion principle for the natural numbers type is given by the following: given
a type
an element
a family of elements
one can construct a family of elements
such that
and
In the other formulation of dependent type theory in terms of a hierarchy of universes and no type judgment, large elimination of the natural numbers is simply the recursion principle for a universe in the hierarchy: given
a universe
an type
a family of elements
one can construct a family of elements
such that
and
However, in dependent type theory with a single type judgment, the universe is not needed and in fact non-existent. Translating the large elimination principle into type judgments, we get the following: given
a type
a family of types
one can construct a family of types
such that
and
It is clear that type variables are needed, since otherwise the second requirement in the large elimination principle that we have a family of types will not be possible.
Similar requirements of type variables apply to the large elimination principles of more general recursive inductive types like W-types.
An alternative to the univalence axiom which does not need a prior notion of identity types between types in polymorphic dependent type theory is equivalence induction. Traditionally, equivalence induction is formulated using universes, such as in Corollary 5.8.5 of the HoTT Book. However, with type variables, one can express equivalence induction without using universes.
Like the induction principle of identity types, there are two versions of equvialence induction, the standard (Martin-Lof) equivalence induction and the based (Paulin-Mohrung) equivalence induciton.
The (based Paulin-Mohrung style) equivalence induction states that given type and a type family indexed by type and equivalence , and an element , for all types and one can construct an element such that .
With impredicative polymorphism, one can also express the standard equivalence induction without using universes.
The (standard Martin-Lof style) equivalence induction states that given a type family indexed by types and and equivalence , and an element , for all types , , and equivalences one can construct an element such that .
In the presence of identity types between types, equivalence induction of both kinds is equivalent in strength to the univalence axiom.
It is also possible to consider adding type variables to cubical type theory, yielding polymorphic cubical type theory. Adding type variables to a cubical type theory with glue types allows one to prove equivalence induction in the theory without the need for identity types between types.
Given a dependent type theory with type variables, dependent sum types, identity types, and function types, type families indexed by type and functions to are equivalent to each other:
By the inference rules of dependent sum types, a type family is equivalently a type with a function to .
Similarly, a type with a function is equivalently a type family .
If the type theory is formulated using a hierarchy of universes , one can show for all types that the above operations form an equivalence of types between the following types:
As a result, a type family variable or a variable of type families simply consists of a type variable and a term variable of a function type:
On the other hand, if the dependent type theory does not have function types, such as the case for a hypothetical geometric homotopy type theory as the internal logic of a Grothendieck -topos, then one would have to add type telescopes to the theory. Via telescopes, we have, for each type , a separate judgment:
where is the telescope consisting of the judgment .
With type telescopes, there inference rules which mimic the inference rules for function types for a type universe are derivable from the inference rules for telescopes:
Then we have additional context forming rules that says that given a type judgment in context , we can add the judgment to the context:
In addition, the judgment behaves as a dependent function, and we also have inference rules which mimic the inference rules for dependent function types :
Then we have additional context forming rules that says that given the judgment in context , we can add the judgment to the context:
Collectively, the additions of type telescopes to the dependent type theory behave as if it is a modal type theory whose mode theory is given by the original dependent type theory and represents, for an -topos , the -category of slice -toposes .
polymorphic dependent type theory
Some discussion about extending dependent type theory with type variables occurs in:
Last revised on September 20, 2026 at 04:06:10. See the history of this page for a list of all contributions to it.