Semantics of type theory

The semantics of type theory involves several closely related kinds of models, which are constructed and studied in order to justify axioms and new type theories, and to use type theory as an internal language for categories, higher categories and other mathematical structures.

There are several ways to package the structure of a model of type theory, including categories with families, comprehension categories, categories with attributes and contextual categories. In all cases, a model is a base substrate, together with extra structure and requirements for each rule of the type theory under consideration.

Categories with families

Categories with families, introduced by Dybjer, are a commonly used notion of model which stays relatively close to the syntax of type theory.

Introduction

The CwF structure is designed to closely parallel the syntax of type theory.

• To each derivable syntactic judgment of the form “$\mathrm{\Gamma }$ is a context”, the semantics in a CwF associates an element $\hat{\mathrm{\Gamma }}$ of a set of contexts denoted $\mathrm{Con}$.
• To each derivable judgment “$A$ is a type in context $\mathrm{\Gamma }$” is associated an element $\hat{A}$ of a set of types in context $\hat{\mathrm{\Gamma }}$ denoted $\mathrm{Ty}(\hat{\mathrm{\Gamma }})$. (Here $\hat{A}$ depends on $\mathrm{\Gamma }$ and not merely on $A$ although this dependency is dropped in the notation.)
• To each derivable judgment “$t$ is a term of type $A$ in context $\mathrm{\Gamma }$” (usually denoted $\mathrm{\Gamma }⊢t:A$) is associated an element $\hat{t}$ of a set of terms of type $\hat{A}$ in context $\hat{\mathrm{\Gamma }}$, denoted ${\mathrm{Tm}}_{\hat{\mathrm{\Gamma }}}(\hat{A})$.

(The terminology may be confusing because the "terms" of the model need not be finite syntactic objects as in the traditional sense of "term" in mathematical logic, but merely constitute the semantics of the syntactic terms of the type theory. Some authors instead call them elements, or refer to semantic contexts, semantic types and semantic terms.)

The semantic interpretation of definitional equality is always actual equality in the model, so whenever a judgment “$A$ and $B$ are definitionally equal types in context $\mathrm{\Gamma }$” is derivable, the interpretation in the model must ensure $\hat{A}=\hat{B}$, and whenever “$t$ and $u$ are definitionally equal terms of type $A$ in context $\mathrm{\Gamma }$” is derivable, the interpretation ensures $\hat{t}=\hat{u}$.

A CwF contains operations to interpret contexts: a special element $\diamond \in \mathrm{Con}$ to model the empty context, and a context extension operation $▹$ to model the addition of a new variable to a context.

The remaining data of CwFs serves to interpret the substitution operation necessitated by dependent types: if $f$ has the dependent function type $(x:A)\to B$ where $B$ is a term involving the variable $x$, the application of $f$ to a term $t$ has the type $B[x:=t]$. CwFs use parallel substitutions, namely substitutions between entire contexts. If there were a judgment in the syntax which was directly interpreted by a substitution from $\hat{\mathrm{\Gamma }}$ to $\hat{\mathrm{\Delta }}$ in the CwF, it would be “$\sigma$ is a list of terms in context $\mathrm{\Gamma }$, one for each type in $\mathrm{\Delta }$, having this type with the previous variables from $\mathrm{\Delta }$ substituted by the previous terms in the list” (e.g., a parallel substitution from $\mathrm{\Gamma }$ to $x:A,y:B$ in the syntax would be a term $t$ of type $A$ in context $\mathrm{\Gamma }$ and a term $u$ of type $B[x:=t]$ in context $\mathrm{\Gamma }$).

Definition

Let $\mathrm{Fam}$ denote the category of families of sets. An object of $\mathrm{Fam}$ is a family $(A_i{)}_{i\in I}$ where $I$ is a set and each $A_i$ is a set. A morphism $f:(A_i{)}_{i\in I}\to (B_j{)}_{j\in J}$ in $\mathrm{Fam}$ is a function $r:I\to J$ together with, for each $i\in I$, a function $t_i:A_i\to B_{r(i)}$. (This category is equivalent to the arrow category of $\mathrm{Set}$, through the correspondence between a function $f:A\to I$ and the family of sets $(f^{-1}(\{i\}){)}_{i\in I}$.)

A category with families (CwF) consists of the following data:

• A category.

  The class of objects is denoted $\mathrm{Con}$ and the objects are called contexts. The class of morphisms from a context $\mathrm{\Delta }$ to a context $\mathrm{\Gamma }$ is denoted $\mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma })$ and these morphisms are called substitutions from $\mathrm{\Delta }$ to $\mathrm{\Gamma }$.

• A contravariant functor from this category to $\mathrm{Fam}$.

  The image of a context $\mathrm{\Gamma }$ is a family of sets denoted $({\mathrm{Tm}}_{\mathrm{\Gamma }}(A){)}_{A\in \mathrm{Ty}(\mathrm{\Gamma })}$ (we usually drop the subscript in ${\mathrm{Tm}}_{\mathrm{\Gamma }}(A)$). The elements of $\mathrm{Ty}(\mathrm{\Gamma })$ are called types in context $\mathrm{\Gamma }$, and the elements of $\mathrm{Tm}(A)$ are called terms of type $A$ (in context $\mathrm{\Gamma }$).

  The image of a substitution $\sigma \in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma })$ is a morphism $(\mathrm{Tm}(A){)}_{A\in \mathrm{Ty}(\mathrm{\Gamma })}\to (\mathrm{Tm}(B){)}_{B\in \mathrm{Ty}(\mathrm{\Delta })}$ in $\mathrm{Fam}$. Its component $\mathrm{Ty}(\mathrm{\Gamma })\to \mathrm{Ty}(\mathrm{\Delta })$ is denoted by $A\mapsto A[\sigma ]$, and for each $A\in \mathrm{Ty}(\mathrm{\Gamma })$, its component $\mathrm{Tm}(A)\to \mathrm{Tm}(A[\sigma ])$ is also denoted $t\mapsto t[\sigma ]$. These operations are respectively called substitution in types and substitution in terms.

  Alternatively, this data can be packaged as a presheaf of types $\mathrm{Ty}$ on the category of contexts, and a dependent presheaf of terms $\mathrm{Tm}$ on the category of contexts over the presheaf of types.

• A terminal object in the category of contexts.

  It is denoted $\diamond$ and called the empty context.

• For each context $\mathrm{\Gamma }$ and for each type $A\in \mathrm{Ty}(\mathrm{\Gamma })$, consider the presheaf on the category of contexts which sends a context $\mathrm{\Delta }$ to the set of pairs of a substitution $\sigma \in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma })$ and a term $t\in {\mathrm{Tm}}_{\mathrm{\Delta }}(A[\sigma ])$. The functorial action of the presheaf on a substitution $\delta \in \mathrm{Sub}(\mathrm{\Sigma },\mathrm{\Delta })$ is given by $(\sigma ,t)\mapsto (\sigma \circ \delta ,t[\delta ])$. The last part of the CwF data is a representing object for this presheaf, together with a natural isomorphism witnessing the representation.

  The representing context is denoted $\mathrm{\Gamma }▹A$ and called the context extension of $\mathrm{\Gamma }$ by $A$.

  In one direction, the natural isomorphism sends a substitution $\sigma \in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma })$ and a term $t\in \mathrm{Tm}(A[\sigma ])$ to a new substitution $(\sigma ▹t)\in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma }▹A)$ called the substitution extension of $\sigma$ by $t$. In the other direction, it sends a substitution ${\sigma }^{\prime }\in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma }▹A)$ to a pair of its tail $\mathrm{tl}({\sigma }^{\prime })\in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma })$ and its head term $\mathrm{hd}({\sigma }^{\prime })\in \mathrm{Tm}(A[\mathrm{tl}({\sigma }^{\prime })])$.

  Explicitly, the fact that this is a natural isomorphism means that the following laws hold:$$\begin{array}{rl}& \mathrm{tl}(\sigma ▹t)=\sigma \\ & \mathrm{hd}(\sigma ▹t)=t\\ & {\sigma }^{\prime }=\mathrm{tl}({\sigma }^{\prime })▹\mathrm{hd}({\sigma }^{\prime })\\ & (\sigma ▹t)\circ \delta =(\sigma \circ \delta )▹t[\delta ]\\ & \mathrm{tl}({\sigma }^{\prime })\circ \delta =\mathrm{tl}({\sigma }^{\prime }\circ \delta )\\ & \mathrm{hd}({\sigma }^{\prime })[\delta ]=\mathrm{hd}({\sigma }^{\prime }\circ \delta )\end{array}$$

Defined operations

Let $\mathrm{\Gamma }$ be a context and $A$ a type in $\mathrm{\Gamma }$. The head and tail of the identity substitution from $\mathrm{\Gamma }▹A$ to itself are respectively a substitution $\mathrm{wk}\in \mathrm{Sub}(\mathrm{\Gamma }▹A,\mathrm{\Gamma })$ called weakening, and a term $\mathrm{vz}\in {\mathrm{Tm}}_{\mathrm{\Gamma }▹A}(A[\mathrm{wk}])$ called the head variable. Informally, the weakening adds an unused variable to the context, and the head variable is the term given by the variable last declared in the context.

Observe that weakening and the head variable allow to recover the tail and head of any substitution $\sigma \in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma }▹A)$ by $$\mathrm{tl}(\sigma )=\mathrm{tl}(\mathrm{i}\mathrm{d}\circ \sigma )=\mathrm{tl}(\mathrm{i}\mathrm{d})\circ \sigma =\mathrm{w}\mathrm{k}\circ \sigma$$ and $$\mathrm{hd}(\sigma )=\mathrm{hd}(\mathrm{id}\circ \sigma )=\mathrm{hd}(\mathrm{id})[\sigma ]=\mathrm{vz}[\sigma ].$$

Furthermore, given a substitution $\sigma \in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma })$, and a type $A\in \mathrm{Ty}(\mathrm{\Gamma })$, we define a lifted substitution ${\sigma }^{+}\in \mathrm{Sub}(\mathrm{\Delta }▹A[\sigma ],\mathrm{\Gamma }▹A)$ by ${\sigma }^{+}:=(\sigma \circ \mathrm{w}\mathrm{k})▹\mathrm{vz}$.

Extra structure for type formers

For each rule of a particular type theory, there is added structure and/or requirements on a CwF for it to model the type theory.

• A rule which introduces a type or term former is interpreted by an operation returning a type or term of the CwF, which is required to commute with substitution. The latter requirement is necessary since substitution is defined recursively in the syntax, e.g., $(A\times B)[x:=t]$ is $A[x:=t]\times B[x:=t]$.
• A rule adding definitional equalities is interpreted by a requirement that the operations on the CwF satisfy a corresponding equation.

To illustrate this, consider the case of dependent pair types (Σ-types). The type formation rule is

$$\frac{\mathrm{\Gamma }\text{context}\mathrm{\Gamma }⊢A\text{type}\mathrm{\Gamma },x:A⊢B\text{type}}{\mathrm{\Gamma }⊢(x:A)\times B\text{type}}$$

The corresponding operation on a CwF is: for each $\mathrm{\Gamma }\in \mathrm{Con}$, for each $A\in \mathrm{Ty}(\mathrm{\Gamma })$, and for each $B\in \mathrm{Ty}(\mathrm{\Gamma }▹A)$, a type $\mathrm{\Sigma }(A,B)\in \mathrm{Ty}(\mathrm{\Gamma })$. This operation is required to satisfy the substitution rule: for all substitution $\sigma \in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma })$ and types $A\in \mathrm{Ty}(\mathrm{\Gamma }),B\in \mathrm{Ty}(\mathrm{\Gamma }▹A)$, we must have $\mathrm{\Sigma }(A,B)[\sigma ]=\mathrm{\Sigma }(A[\sigma ],B[{\sigma }^{+}])$.

The term formation rules for the pairing operation is:

$$\frac{\mathrm{\Gamma }\text{context}\mathrm{\Gamma }⊢A\text{type}\mathrm{\Gamma },x:A⊢B\text{type}\mathrm{\Gamma }⊢t:A\mathrm{\Gamma }⊢u:B[x:=t]}{\mathrm{\Gamma }⊢⟨t,u⟩:(x:A)\times B}$$

The corresponding operation on a CwF is: for each $\mathrm{\Gamma }\in \mathrm{Con}$, $A\in \mathrm{Ty}(\mathrm{\Gamma })$, $B\in \mathrm{Ty}(\mathrm{\Gamma }▹A)$, $t\in \mathrm{Tm}(A)$ and $u\in \mathrm{Tm}(B[\mathrm{id}▹t])$), a term $⟨t,u⟩\in \mathrm{Tm}(\mathrm{\Sigma }(A,B))$. This must satisfy the substitution rule:

$$⟨t,u⟩[\sigma ]=⟨t[\sigma ],u[\sigma ]⟩.$$

This equation is meaningful because of the CwF laws and the substitution rule for $\mathrm{\Sigma }$. The left hand side is an element of $\mathrm{\Sigma }(A,B)[\sigma ]$, which by the substitution rule for $\mathrm{\Sigma }$ is equal to $\mathrm{\Sigma }(A[\sigma ],B[{\sigma }^{+}])$. To see that the right hand side is in this set, one has to check that $u[\sigma ]$ is in $B[{\sigma }^{+}][\mathrm{id}▹t[\sigma ]]$. This holds because $u[\sigma ]$ is in $B[\mathrm{id}▹t][\sigma ]$ and

$$\begin{array}{rl}& B[\mathrm{id}▹t][\sigma ]\\ & =B[(\mathrm{id}▹t)\circ \sigma ]\\ & =B[(\mathrm{id}\circ \sigma )▹t[\sigma ]]\\ & =B[\sigma ▹t[\sigma ]]\end{array}$$

while

$$\begin{array}{rl}& B[{\sigma }^{+}][\mathrm{id}▹t[\sigma ]]\\ & =B[(\sigma \circ \mathrm{wk})▹\mathrm{vz}][\mathrm{id}▹t[\sigma ]]\\ & =B[((\sigma \circ \mathrm{wk})▹\mathrm{vz})\circ (\mathrm{id}▹t[\sigma ])]\\ & =B[((\sigma \circ \mathrm{wk})\circ (\mathrm{id}▹t[\sigma ]))▹\mathrm{vz}[\mathrm{id}▹t[\sigma ]]]\\ & =B[\sigma \circ (\mathrm{wk}\circ (\mathrm{id}▹t[\sigma ]))▹\mathrm{vz}[\mathrm{id}▹t[\sigma ]]]\\ & =B[\sigma \circ \mathrm{tl}(\mathrm{id}▹t[\sigma ])▹\mathrm{hd}(\mathrm{id}▹t[\sigma ])]\\ & =B[(\sigma \circ \mathrm{id})▹t[\sigma ]]\\ & =B[\sigma ▹t[\sigma ]].\end{array}$$

Finally, the remaining rules for dependent pair types are the computation rules (or β-rules)

$$\frac{\mathrm{\Gamma }\text{context}\mathrm{\Gamma }⊢A\text{type}\mathrm{\Gamma },x:A⊢B\text{type}\mathrm{\Gamma }⊢t:A\mathrm{\Gamma }⊢u:B[x:=t]}{\mathrm{\Gamma }⊢\mathrm{fst}(⟨t,u⟩)\equiv t:A}$$

$$\frac{\mathrm{\Gamma }\text{context}\mathrm{\Gamma }⊢A\text{type}\mathrm{\Gamma },x:A⊢B\text{type}\mathrm{\Gamma }⊢t:A\mathrm{\Gamma }⊢u:B[x:=t]}{\mathrm{\Gamma }⊢\mathrm{snd}(⟨t,u⟩)\equiv u:B[x:=t]}$$

and the uniqueness rule (or η-rule)

$$\frac{\mathrm{\Gamma }\text{context}\mathrm{\Gamma }⊢A\text{type}\mathrm{\Gamma },x:A⊢B\text{type}\mathrm{\Gamma }⊢p:(x:A)\times B}{\mathrm{\Gamma }⊢p\equiv ⟨\mathrm{fst}(p),\mathrm{snd}(p)⟩:(x:A)\times B}$$

These are interpreted by requiring the following equations on the previous operations:

• $\mathrm{fst}(⟨t,u⟩)=t$ and $\mathrm{snd}(⟨t,u⟩)=u$ (for $\mathrm{\Gamma }\in \mathrm{Con}$, $A\in \mathrm{Ty}(\mathrm{\Gamma })$, $B\in \mathrm{Ty}(\mathrm{\Gamma }▹A)$, $t\in \mathrm{Tm}(A)$, $u\in \mathrm{Tm}(B[\mathrm{id}▹t])$),
• $p=⟨\mathrm{fst}(p),\mathrm{snd}(p)⟩$ (for $\mathrm{\Gamma }\in \mathrm{Con}$, $A\in \mathrm{Ty}(\mathrm{\Gamma })$, $B\in \mathrm{Ty}(\mathrm{\Gamma }▹A)$, $p\in \mathrm{Tm}(\mathrm{\Sigma }(A,B))$).

Universes

The case of universes is somewhat special because it is common to define the syntax of type theory without a separate judgment for “$A$ is a type in context $\mathrm{\Gamma }$”, instead using “$A$ is a term of type ${𝒰}$ in context $\mathrm{\Gamma }$”, i.e., $\mathrm{\Gamma }⊢A:{{𝒰}}_n$, where ${{𝒰}}_n$ is the $n$-th universe (also denoted ${\mathsf{T}\mathsf{y}\mathsf{p}\mathsf{e}}_n$, especially in proof assistants). This is called Russell universes. To give semantics to this kind of type theory, one needs to requirement in the CwF structure that the interpretation of both kinds of judgments in the semantics coincide.

First consider the simpler case of a single Russell universe ${𝒰}$ containing itself (the syntax has the type in type rule that ${𝒰}$ has type ${𝒰}$, which is inconsistent). The corresponding requirements on a CwF are:

• For each context $\mathrm{\Gamma }$, a type ${𝒰}\in \mathrm{Ty}(\mathrm{\Gamma })$ (we leave the dependency on $\mathrm{\Gamma }$ implicit to lighten the notation), with the substitution rule ${𝒰}[\sigma ]={𝒰}$. (This is equivalent to the data of a single type in the empty context ${𝒰}\in \mathrm{Ty}(\diamond )$, the version in an arbitrary context $\mathrm{\Gamma }$ being recovered as ${𝒰}[ϵ]$ where $ϵ$ is the unique substitution from $\mathrm{\Gamma }$ to $\diamond$.)
• An equality of sets $\mathrm{Ty}(\mathrm{\Gamma })={\mathrm{Tm}}_{\mathrm{\Gamma }}({𝒰})$ for every context $\mathrm{\Gamma }$.

For a hierarchy of universes ${{𝒰}}_0$, ${{𝒰}}_1$ where ${{𝒰}}_n$ has type ${{𝒰}}_{n+1}$, …, there is a complication since types are stratified in the syntax and therefore must also be stratified in the semantics. This is treated using a slight variant of CwFs which consists of a category of contexts and substitutions, a terminal object for the empty context, and for each universe level $n$, a functor from this category to families of sets, mapping a context $\mathrm{\Gamma }$ to a family $\mathrm{\Gamma }\mapsto ({\mathrm{Tm}}_{\mathrm{\Gamma }}(A){)}_{A\in {\mathrm{Ty}}_n(\mathrm{\Gamma })}$ of types of level $n$ and terms of these types, equipped with an operation to extend the context with a type of level $n$ (giving for $A\in {\mathrm{Ty}}_n(\mathrm{\Gamma })$ a bijection $\mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma }{▹}_{n}A)\cong (\sigma \in \mathrm{Sub}(\mathrm{\Delta },\mathrm{\Gamma }))\times {\mathrm{Tm}}_{\mathrm{\Delta }}(A[\sigma ])$ natural in $\mathrm{\Delta }$). One can then model universes with, for each level $n$, types ${{𝒰}}_n\in {\mathrm{Ty}}_{n+1}(\mathrm{\Gamma })$ with the substitution rule ${{𝒰}}_n[\sigma ]={{𝒰}}_n$, and an equality of sets ${\mathrm{Ty}}_n(\mathrm{\Gamma })={\mathrm{Tm}}_{\mathrm{\Gamma }}({{𝒰}}_n)$.

A slightly weaker variant is Coquand universes, which require a bijection between the sets ${\mathrm{Ty}}_n(\mathrm{\Gamma })$ and ${\mathrm{Tm}}_{\mathrm{\Gamma }}({{𝒰}}_n)$ natural in $\mathrm{\Gamma }$, instead of an equality. This corresponds to a syntax with a primitive operation $\mathrm{El}$ that takes an element of the universe ${𝒰}$ (a “code” for a type) and gives an actual type, and another primitive operation $\mathrm{code}$ that converts back a type into a code, with definitional equalities $\mathrm{code}(\mathrm{El}(t))\equiv t$ and $\mathrm{El}(\mathrm{code}(A))\equiv A$. Coquand's original motivation for introducing this style of universes is that they are the most natural to construct in presheaf models.

Finally, an even weaker variant is Tarski universes, which only have the $\mathrm{El}$ operation but not a $\mathrm{code}$ operation, and which require, for each type former, a counterpart on the level of codes, e.g., an operation $-{\times }_c-$ on ${\mathrm{Tm}}_{\mathrm{\Gamma }}({𝒰})$ with the definitional equality $\mathrm{El}(t{\times }_{c}u)\equiv \mathrm{El}(t)\times \mathrm{El}(u)$, etc.

Some type theories have universe cumulativity: a type in a universe is also automatically a type in all higher universes. This can be treated in various ways, including subset inclusions between the ${\mathrm{Ty}}_n(\mathrm{\Gamma })$, and several variants of lifting operations between universes.

Democracy

The basic intuition stemming from the syntax is that a context is a list of types $x_0:A_0,\dots ,x_{k-1}:A_{k-1}$, which is essentially equivalent to an iterated Σ-type $(x_0:A_0)\times \dots \times (x_{k-2}:A_{k-2})\times A_{k-1}$. This is not true in all models, but it can be a useful property to consider.

A CwF is democratic when every context $\mathrm{\Gamma }$ is isomorphic (in the category of contexts) to $\diamond ▹A$ for some closed type $A$ (i.e., a type in the empty context $\diamond$).

The set model

The set model, or standard model, is the simplest model of type theory. Every construct is simply interpreted by its metatheoretic counterpart: a term of a function type is a function, a term of a product type is a pair, etc. (This is akin to the usual Tarskian semantics of first-order logic. If one constructs it in type theory itself as a metatheory and one views type theory as a programming language, it is a metacircular interpreter.)

The CwF is defined as follows:

• A context is a set and a substitution is a function (so the category of contexts and substitutions is the category of sets).
• A type in $\mathrm{\Gamma }$ is a family of sets $(A_i{)}_{i\in \mathrm{\Gamma }}$, and a term of this type is a choice of an element $t_i\in A_i$ for each $i\in \mathrm{\Gamma }$. The action of a substitution $\sigma :\mathrm{\Delta }\to \mathrm{\Gamma }$ on a type $(A_i{)}_{i\in \mathrm{\Gamma }}$ gives $(A_{\sigma (j)}{)}_{j\in \mathrm{\Delta }}$, and on a term $(t_i\in A_i{)}_{i\in \mathrm{\Gamma }}$, it gives $(t_{\sigma (j)}\in A_{\sigma (j)}{)}_{j\in \mathrm{\Delta }}$.
• The empty context is a fixed singleton set.
• The extension of a context $\mathrm{\Gamma }$ by a type $(A_i{)}_{i\in \mathrm{\Gamma }}$ is the type of pairs of an $i\in \mathrm{\Gamma }$ and an element of $A_i$. The tail and head of a substitution $\mathrm{\Delta }\to (\mathrm{\Gamma }▹(A_i{)}_{i\in \mathrm{\Gamma }}),j\mapsto (i_j,a_j)$ are given by $j\mapsto i_j$ and $j\mapsto a_j$.

All type formers are defined “pointwise”. For example, the product $(A_i{)}_{i\in \mathrm{\Gamma }}\times (B_i{)}_{i\in \mathrm{\Gamma }}$ is defined as $(A_i\times B_i{)}_{i\in \mathrm{\Gamma }}$, the pairing of terms $(t_i\in A_i{)}_{i\in \mathrm{\Gamma }}$ and $(u_i\in B_i{)}_{i\in \mathrm{\Gamma }}$ is $((t_i,u_i)\in A_i\times B_i{)}_{i\in \mathrm{\Gamma }}$, etc. This model supports essentially any type former supported by the metatheory (with the exception of universes: the metatheory needs a stronger universe than the object theory contains, namely a universe large enough to contain all universes from the object theory, as is expected from Gödel's second incompleteness theorem). It can model the equality reflection rule of extensional type theory, but not univalence.

The syntactic model

The syntactic model (or term model) is given by the contexts, parallel substitutions, types and terms in the syntax of the type theory under consideration, with the operations induced by all type and term constructors of the type theory.

For “reasonable” type theories, the syntactic model is also the initial model, which means that it has a unique morphism into every other model. The notion of morphism between models is usually defined by presenting the definition of a model as a generalized algebraic theory (GAT) (which is like an algebraic theory but allowing dependent functions), and applying the standard definition of morphism between algebras of a GAT. The initiality means that the syntax can indeed be interpreted in every model as expected. Actually establishing this turns out to be very tedious. While Cartmell and Hofmann proved it for some standard type theories, initiality became a contentious point in the research community around 2015 when some researchers, notably Voevodsky, opined that it was not justified to treat it as established for different type theories without carefully adapting the proofs. Most researchers consider the issue to have been satisfactorily solved by Uemura's introduction of the logical framework of second-order generalized algebraic theories (SOGATs), which encompasses practically all existing type theories (the main exception being substructural type theories), and his proof of initiality of the syntactic model for any SOGAT.

Meanwhile, it has also become common to eschew the traditional syntactic presentation of type theory entirely and define the syntax as the initial model (which exists for any GAT). This approach is called intrinsic syntax. At this level of abstraction, it is possible to construct and study models and to use type theory as an internal language for them (treating the traditional terms merely as a notation for elements of the model). It is not possible to study properties of the concrete, extrinsic syntax such as subject reduction and confluence. However, remarkably, the two main syntactic properties of some type theories, canonicity and normalization, can be stated and proved entirely at this level.

Presheaf models

Let ${𝒞}$ be a category. The presheaf category $\widehat{{𝒞}}$ is equipped with a canonical CwF structure as follows.

A type $A$ in context $\mathrm{\Gamma }$ is a dependent presheaf on ${𝒞}$ over $\mathrm{\Gamma }$. This means the following data:

• For each object $x\in {𝒞}$, and for each element $i\in \mathrm{\Gamma }(x)$, a set $A(x{)}_i$,
• For each morphism $f:x\to y$ in ${𝒞}$, and for each element $i\in \mathrm{\Gamma }(y)$, a function $A(f{)}_i:A(y{)}_i\to A(x{)}_{\mathrm{\Gamma }(f)(i)}$.

This data is subject to a functoriality requirement: $A(g\circ f{)}_i=A(g{)}_{\mathrm{\Gamma }(f)(i)}\circ A(f{)}_i$ and $A(\mathrm{id}{)}_i=\mathrm{id}$.

Alternatively, $A$ can be viewed as a presheaf on the category of elements of $\mathrm{\Gamma }$.

A term $t$ of type $A$ in context $\mathrm{\Gamma }$ consists of, for each object $x\in {𝒞}$ and for each element $i\in \mathrm{\Gamma }(x)$, an element $t(x{)}_i\in A(x{)}_i$, such that these choices are natural: for $f:x\to y$ in ${𝒞}$ and $i\in \mathrm{\Gamma }(y)$, we should have $A(f{)}_i(t(y{)}_i)=t(x{)}_{\mathrm{\Gamma }(f)(i)}$.

For a natural transformation $\sigma :\mathrm{\Delta }\to \mathrm{\Gamma }$, the substituted type $A[\sigma ]$ is defined by precomposition: it maps an object $x\in {𝒞}$ and an element $i\in \mathrm{\Delta }(x)$ to the set $A(x{)}_{\sigma (x)(i)}$, and it maps a morphism $f:x\to y$ in ${𝒞}$ and an element $i\in \mathrm{\Delta }(y)$ to the function $A(f{)}_{\sigma (y)(i)}$. Term substitution is also defined by precomposition: $t[\sigma ]$ maps an object $x\in {𝒞}$ and an element $i\in \mathrm{\Delta }(x)$ to the element $t(x{)}_{\sigma (x)(i)}\in A(x{)}_{\sigma (x)(i)}$.

The empty context is the presheaf mapping every object to a fixed singleton set. The extended context $\mathrm{\Gamma }▹A$ maps an object $x\in {𝒞}$ to the set of pairs of an element $i\in \mathrm{\Gamma }(x)$ and an element of $A(x{)}_i$, and a morphism $f:x\to y$ in ${𝒞}$ to the function $(i,a)\mapsto (\mathrm{\Gamma }(f)(i),A(f{)}_i(a))$. The extended substitution $\sigma ▹t$ maps an object $x\in {𝒞}$ to the function $i\mapsto (\sigma (x)(i),t(x{)}_i)$.

Other models

Other models of type theory include the setoid model, the groupoid model, the simplicial set model, the assemblies model, and several models in cubical sets starting with the BCH (Bezem–Coquand–Huber) model.

Relationship to categorical logic

Traditional categorical logic involves correspondences between logics and kinds of categories which serve as their models. For example, elementary toposes are models of a form of intuitionistic higher-order logic, and regular categories are models of regular logic. The correspondence is used in both ways: a notion of model is fundamental to study a logic, e.g., to prove that a statement is unprovable by finding a model where it fails, and conversely, a category can be studied by reasoning in a logic of which it is a model, which is often called an internal language for the category.

For simple type theory, such correspondences can be found. For example, Cartesian closed categories model the simply typed λ-calculus with function, top and product types, and bicartesian closed categories model its extension with bottom and sum types. On the other hand, the situation is significantly more complicated for dependent type theory.

In the aforementioned semantics of simple type theory, a type is interpreted by an object of the category. In dependent type theory, a type depends on the value of the context in which it is defined, so one cannot simply use an object. Instead, a natural idea is to interpret a type $A$ in context $\mathrm{\Gamma }$ by an object equipped with a morphism to the interpretation of $\mathrm{\Gamma }$. The idea is to mimic the category of sets, where a family of sets $(A_i{)}_{i\in \mathrm{\Gamma }}$ can be represented categorically as the morphism $r:A\to \mathrm{\Gamma }$, where $A$ is the disjoint union of all the $A_i$, which sends elements of each $A_i$ to their index $i$. The family $(A_i)$ can be recovered by $A_i=r^{-1}(i)$.

This idea was used by Seely in a 1984 paper claiming that Martin–Löf type theory with Π types, Σ types and extensional identity types can be modelled in a locally Cartesian closed category (i.e., a category ${𝒞}$ such that all the slice categories ${𝒞}/A$ are Cartesian closed). However, it was later observed that Seely's proof is wrong. Substitution in types is modelled by pullback. For the interpretation of substitution to be sound, this operation must be strictly functorial way: pullback along $g\circ f$ must be exactly the same as pullback along $f$ followed by pullback along $g$. However, pullback involves an arbitrary choice and there is no reason for all these choices to be globally coherent: these pullbacks are always isomorphic, but have no reason to be the same. (Taking a skeleton of ${𝒞}$ does not help, since a pullback is not merely a choice of object but also a choice of morphisms.)

For example, call $S:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ the successor constructor of natural numbers, and consider the trivial proof that for a predicate $P:\mathbb{\mathbb{N}}\to {𝒰}$, if $P(0)$ holds, $P(1)$ holds, and $P(n)$ holds for all $n\ge 2$ (call this hypothesis $H$), then $P(n)$ for all $n$. This is done by two inductions: the first reduces to proving $(P(n))[n:=S(n^{\prime })]$ where $n^{\prime }:\mathbb{\mathbb{N}}$ is a fresh variable, and the second reduces this to proving $((P(n)[n:=S(n^{\prime })])[n^{\prime }:=S(n^{″})]$ where $n^{″}:\mathbb{\mathbb{N}}$ is fresh. By applying the hypothesis $H$ to $S(S(n^{″}))$ (noting that $S(S(n^{″}))\ge 2$), one obtains an element of $(P(n))[n:=S(S(n^{″}))]$. This only works because in the syntax of type theory, the substituted types $(P(n))[n:=S(S(n^{″}))]$ and $((P(n))[n:=S(n^{\prime })])[n^{\prime }:=S(n^{″})]$ are the same, namely $P(S(S(n^{″}))$. On the other hand, using the interpretation of substitution as pullback, the interpretations of these two types would only be isomorphic and it would not be semantically justified to use elements of one as elements of the other.

The same problem arises with the interpretation of type formers, which must commute with substitution, whereas this fails in Seely's purported model. For example, given a dependent function $f:(x:A)\to (P(x)\times Q(x))$, the application $f(g(y))$ has type $(P(x)\times Q(x))[x:=g(y)]$. Without an actual equality between this type and $P(g(y))\times Q(g(y))$, it is not semantically justified to apply the first projection to $f(g(y))$ to obtain an element of $P(g(y))$.

For this reason, type theory is not modelled directly in categories with properties, but rather in categories enriched with structure, such as CwFs, which include a set of types for each context and a substitution operation on types required to be functorial. The usual way to define a model is to start from a category with good enough properties and define this structure analogously to categorical constructions, but taking care to preserve coherence. This process is sometimes referred to as strictification.

There are several strictification constructions for doing this in general. A construction due to Bénabou was used by Hofmann to interpret MLTT in any locally Cartesian closed category, thus repairing Seely's result (with a different semantic interpretation). More recently, Lumsdaine and Warren proposed the local universes construction, which delays computing pullbacks by modelling a type in $\mathrm{\Gamma }$ as two objects $U$ and $A$ with a pair of morphisms $\mathrm{\Gamma }\to U\leftarrow A$, so that applying a substitution $\mathrm{\Delta }\to \mathrm{\Gamma }$ can be simply performed by composition of $\mathrm{\Delta }\to \mathrm{\Gamma }$ with $\mathrm{\Gamma }\to U$, which is functorial.

However, in most concrete cases, the strictification can be done by hand, and the result is simpler to work with than the output of such general constructions. For example, in the set model, types in context $\mathrm{\Gamma }$ are defined as the actual families of sets $(A_i{)}_{i\in \mathrm{\Gamma }}$ rather than a functions $A\to \mathrm{\Gamma }$ so that the application of a substitution $\gamma :\mathrm{\Delta }\to \mathrm{\Gamma }$ can simply be the family $(A_{\gamma (j)}{)}_{j\in J}$. This definition of substitution is strictly functorial, unlike pullback in the category of sets. The presheaf model is another typical example: substitution is made functorial by replacing presheaves $A$ with a natural transformation to $\mathrm{\Gamma }$ by dependent presheaves over $\mathrm{\Gamma }$.