B-SYSTEMS AND C-SYSTEMS ARE EQUIVALENT

Abstract

C-systems were defined by Cartmell as models of generalized algebraic theories. B-systems were defined by Voevodsky in his quest to formulate and prove an initiality conjecture for type theories. They play a crucial role in Voevodsky’s construction of a syntactic C-system from a term monad. In this work, we construct an equivalence between the category of C-systems and the category of B-systems, thus proving a conjecture by Voevodsky.

1 Introduction

Vladimir Voevodsky spent the last years of his life developing a mathematical theory of type theories. One of his main goals was to give a rigorous statement, and proof, of an “initiality conjecture.” The “template” for any initiality statement is as follows: One starts by defining a suitable notion of signature—an abstract specification device describing the (types and) terms of a language. To any signature, one then associates a category of models of that signature, in such a way that the ¹ initial object in that category—if it exists—deserves to be called the syntax generated by the signature. Finally, one aims to construct such initial objects, or identify sufficient criteria for a signature to admit initial objects.

The use of such an initiality result is multifold:

1. 1. it gives a mathematical characterization, up to (unique) isomorphism, of the syntax generated by a signature; and

2. 2. it provides a recursion principle allowing one to define interpretations from the syntax into worlds of mathematical objects.

As part of his quest towards an initiality conjecture for type theories, Voevodsky develops the notion of B-system [8] as one of several suitable mathematical structures for type theory. Specifically, Voevodsky uses B-systems to build “term” C-systems (or “term” contextual categories), for which he then aims to prove initiality. For more details of the role of B-systems in Voevodsky’s theory of type theories, we point the interested reader to the introduction of [15]; a summary is given in [1, Section 1.2].

B-systems, Voevodsky conjectures in [8], are constructively equivalent to the well-known C-systems or contextual categories first introduced by Cartmell [2]. Furthermore, in his Templeton grant application [13], Voevodsky writes:

The theory of B-systems is conjecturally equivalent to the theory of C-systems that were introduced by John Cartmell under the name “contextual categories” in [2, 3]. Proving this equivalence is among the first goals of the proposed research.

B-systems reflect very directly the way in which inference rules are written; see Example 2.4. Inference rules are commonly used to present a type theory in terms of generators and relations. As such, B-systems seem particularly well suited for defining and studying the syntax generated by a signature.

2 B-systems

Voevodsky’s definition of B-systems [8] is inspired by the presentation of type theories in terms of inference rules. Specifically, type theories “of Martin-Löf genus” are given by sets of five kinds of judgements, namely well-formed context ( $\Gamma \vdash $ ), well-formed type in some context ( ), well-formed term of some type in some context ( $\Gamma \vdash a : A$ ), equality of types ( $\Gamma \vdash A \equiv B$ ), and equality of terms ( $\Gamma \vdash a \equiv b : A$ ). Interpreting equality of types and terms as actual equality, and expressing $\Gamma \vdash A$ instead as $\Gamma , A \vdash $ , led Voevodsky to defining a B-system $\mathbb {B}$ to consist of families of sets $(B_n)_{n \in {\mathbb {N}}}$ and $(\tilde {B}_{n+1})_{n \in {\mathbb {N}}}$ , intuitively denoting, for any $n \in {\mathbb {N}}$ , contexts of length n, and terms in a context of length n together with their types, respectively. Furthermore, any B-system has two projection maps ${\mathsf {ft}} \colon B_{n+1} \to B_n$ and $\partial \colon \tilde {B}_{n+1} \to B_{n+1}$ that, intuitively, map a context of length $n+1$ to its initial segment of length n, and a term to its context extended with its type, respectively. Finally, any B-system has weakening and substitution operations on B and $\tilde {B}$ , as well as functions $\delta \colon B_{n+1} \to \tilde {B}_{n+2}$ that intuitively provide assumption variables. This intuitive explanation of B-systems is made precise in Example 2.4.

Definition 2.1. A B-frame $\mathbb {B}$ is a diagram of sets and functions as in the right-hand diagram in (1), where the set $B_0$ is assumed to be a singleton.

(1)

Equivalently, a B-frame is a presheaf on the “comb” category, i.e., the left-hand diagram in (1), that preserves terminal objects as a functor, namely, that maps $0$ to a singleton set.

A homomorphism of B-frames $\mathbb {H}\colon \mathbb {A} \to \mathbb {B}$ is a natural transformation of B-frames; it consists of maps $H_n \colon A_n\to B_n$ and $\tilde {H}_{n+1} \colon \tilde {A}_{n+1}\to \tilde {B}_{n+1}$ such that

$$\begin{align*}{\mathsf{ft}_{n}} (H_{n+1}(X)) = H_n({\mathsf{ft}_{n}} (X)) \qquad\text{and}\qquad {\partial_{n+1}}(\tilde{H}_{n+1}(x)) = H_{n+1}({\partial_{n+1}}(x)) \end{align*}$$

for any $X\in A_{n+1}$ and $x\in \tilde {A}_{n+1}$ .

For $m,n\in \mathbb {N}$ , we denote the composition ${\mathsf {ft}_{n}} \circ \cdots \circ {\mathsf {ft}_{n+m}} :B_{n+m+1}\to B_n$ by ${\mathsf {ft}_{n}^m}$ . However, we often omit subscripts as these are usually clear from context.

We refer to elements in $B_n$ as contexts and elements in $\tilde {B}_{n+1}$ as terms. We say that b is an element of a B-frame $\mathbb {B}$ , and write $b \in \mathbb {B}$ , to mean that b is either a context or a term.

Remark 2.2. Given a B-frame $\mathbb {B}$ and a context $X \in B_n$ in that B-frame, we construct the slice of $\mathbb {B}$ over X, i.e., the B-frame that consists only of the contexts and terms of $\mathbb {B}$ that depend on X. More precisely, for every $X \in B_n$ , the slice B-frame $\mathbb {B}/X$ consists of the sets

$$ \begin{align*} (B/X)_{m} & := \{Y\in B_{n+m}\mid{\mathsf{ft}^{m}} (Y)= X\},\\ (\tilde{B}/X)_{m+1} & := \{y\in \tilde{B}_{n+m+1}\mid{\mathsf{ft}}^{m+1}(\partial (y))= X\} \end{align*} $$

together with the restriction of the ${\mathsf {ft}}$ and ${\partial } $ maps from $\mathbb {B}$ .

A homomorphism $\mathbb {H} \colon \mathbb {A} \to \mathbb {B}$ induces in the obvious way a homomorphism $\mathbb {H}/X \colon \mathbb {A}/X \to \mathbb {B}/H(X)$ .

Definition 2.3. A B-system $\mathbb {B}$ consists of a B-frame $\mathbb {B}$ together with:

1. 1. for every $x \in \tilde {B}_{n+1}$ , a homomorphism of B-frames $\mathbb {S}_x \colon \mathbb {B}/{\partial } (x) \to \mathbb {B}/{\mathsf {ft}} ({\partial } (x))$ called substitution,

2. 2. for every $X \in B_{n+1}$ , a homomorphism of B-frames $\mathbb {W}_X \colon \mathbb {B}/{\mathsf {ft}} (X) \to \mathbb {B}/X$ called weakening, and

3. 3. for every n, a function $\delta _n \colon B_{n+1} \to \tilde {B}_{n+2}$ called generic element such that ${\partial } (\delta (X)) = W_X(X)$ , for every $X \in B_{n+1}$ .

These functions are subject to the following equations:

1. 1. For every $x \in \tilde {B}_{n+1}$ , the substitution $\mathbb {S}_x$ distributes over substitution and over weakening in the slice B-system $\mathbb {B}/{\partial } (x)$ , meaning that, for every $y \in (\tilde {B}/{\partial } (x))_{m+1}$ , $Y \in (B/{\partial } (x))_{k+1}$ , $b \in \mathbb {B}/{\mathsf {ft}} ({\partial } (y))$ , and $b' \in \mathbb {B}/{\mathsf {ft}} (Y)$

   $$\begin{align*}\mathbb{S}_x (\mathbb{S}_y(b)) = \mathbb{S}_{\tilde{S}_x(y)}(\mathbb{S}_x(b)) \hspace{2em}\text{and}\hspace{2em} \mathbb{S}_x (\mathbb{W}_Y(b')) = \mathbb{W}_{S_x(Y)}(\mathbb{S}_x(b')). \end{align*}$$

2. 2. For every $X \in B_{n+1}$ , the weakening $\mathbb {W}_X$ distributes over substitution and weakening in the slice B-system $\mathbb {B}/X$ , meaning that, for every $y \in (\tilde {B}/X)_{m+1}$ , $Y \in (B/X)_{k+1}$ , $b \in \mathbb {B}/{\mathsf {ft}} ({\partial } (y))$ , $b' \in \mathbb {B}/{\mathsf {ft}} (Y)$

   $$\begin{align*}\mathbb{W}_X(\mathbb{S}_y(b)) = \mathbb{S}_{\tilde{W}_X(y)}(\mathbb{W}_X(b)) \hspace{2em}\text{and}\hspace{2em} \mathbb{W}_X(\mathbb{W}_Y(b')) = \mathbb{W}_{W_X(Y)}(\mathbb{W}_X(b')). \end{align*}$$

3. 3. For every $x \in \tilde {B}_{n+1}$ and $X \in B_{n+1}$ , substitution $S_x$ and weakening $W_X$ preserve generic elements in $\mathbb {B}/{\partial } (x)$ and $\mathbb {B}/{\mathsf {ft}} (X)$ , respectively, meaning that, for every $m \in {\mathbb {N}}$ , $Y \in (B/{\partial } (x))_{m+1}$ , and $Z \in (B/{\mathsf {ft}} (X))_{m+1}$

   $$\begin{align*}\tilde{S}_x(\delta_{n+m+1}(Y)) = \delta_{n+m}(S_x(Y)) \!\!\hspace{2em}\text{and}\!\!\hspace{2em} \tilde{W}_X(\delta_{n+m}(Z)) = \delta_{n+m+1}(W_X(Z)). \end{align*}$$

4. 4. Substitution into a dummy variable does nothing, i.e., $\mathbb {S}_x(\mathbb {W}_{{\partial } (x)}(b)) =b$ , for every $x\in \tilde {B}_{n+1}$ and $b \in \mathbb {B}/{\mathsf {ft}} ({\partial } (x))$ .

5. 5. Substituting a term into the generic element on its context yields the term, i.e., $\tilde {S}_x(\delta ({\partial } (x)))= x$ , for every $x\in \tilde {B}_{n+1}$ .

6. 6. Substituting a generic element into a duplicated variable contracts it, i.e., $\mathbb {S}_{\delta (X)}(\mathbb {W}_X(b)) = b$ , for every $X\in B_{n+1}$ and $b \in \mathbb {B}/X$ .

A homomorphism of B-systems, or B-homomorphism for short, is a homomorphism of B-frames $\mathbb {H} \colon \mathbb {A} \to \mathbb {B}$ that distributes over substitution and weakening, and that commutes with generic elements, meaning that, for every $x \in \tilde {A}_{n+1}$ , $X \in A_{n+1}$ , $a \in \mathbb {A}/{\partial } (x)$ , and $a' \in \mathbb {A}/{\mathsf {ft}} (X)$

$$ \begin{gather*} \mathbb{H}(\mathbb{S}_x(a)) = \mathbb{S}_{\tilde{H}(x)}(\mathbb{H}(a)), \hspace{3em} \mathbb{H}(\mathbb{W}_X(a')) = \mathbb{W}_{H(X)}(\mathbb{H}(a')) \\ \text{and}\hspace{3em} \tilde{H}(\delta_n(X)) = \delta_n(H(X)). \end{gather*} $$

We denote the category of B-systems by ${\mathbf {Bsys}}$ .

Example 2.4 (B-systems from signatures)

An important class of examples of B-systems arises by considering “restricted 2-sorted binding signature” à la Voevodsky [15]. Intuitively, such a signature specifies expressions of two sorts, ${\mathsf {Type}}$ and ${\mathsf {Term}}$ . Expressions can depend on variables, where each variable is again either of sort ${\mathsf {Type}}$ or ${\mathsf {Term}}$ . The signatures are “restricted” in the sense that variable binding is only allowed for variables of sort ${\mathsf {Term}}$ , not of variables of sort ${\mathsf {Type}}$ .

Such a signature is used to specify the presyntax (or raw syntax) of Martin-Löf type theory, specifying that, say, there is a term “zero” of sort ${\mathsf {Term}}$ and a term “nat” of sort ${\mathsf {Type}}$ . ² The presyntax serves to formally specify judgements and inference rules, which in turn specify the typing relation between types and terms of a type system such as Martin-Löf type theory. Typically, we demand a (term) judgement to have the following shape:

(2) $$ \begin{align} A_0, A_1, \ldots, A_n \vdash t : A. \end{align} $$

This judgement is built from expressions generated by a two-sorted binding signature: $A_i$ and A are expressions of sort ${\mathsf {Type}}$ , with a suitable number of variables, and t is an expression of sort ${\mathsf {Term}}$ , depending on n variables.

Formally, any restricted two-sorted binding signature generates a monad R of terms relative to the inclusion of finite sets into sets, and a module $LM$ of types over R. Here, if we let $[n]$ denote the standard set $\{0,\ldots ,n-1\}$ with n elements, $R([n])$ and $LM([n])$ are the set of terms and types depending on n variables, respectively. The monad R comes with a map from variables to terms, $\eta : [m] \to R([m])$ , for any m, and with a monadic substitution of type $([m] \to R([n])) \to R([m]) \to R([n])$ , for any m and n. Similarly, $LM$ comes with a module substitution of type $([m] \to R([n])) \to LM([m]) \to LM([n])$ . The module substitution of $LM$ substitutes term expressions (from R) for variables occurring in type expressions. Note that the “simultaneous” substitution above can be specialized to a “single-variable” substitution by mapping any variable x that should not be substituted to $\eta (x)$ .

From such a pair $(R, LM)$ , Voevodsky constructs a B-system as follows. The families B and $\tilde {B}$ are defined by

$$ \begin{align*} B_n := \prod_{i=0}^{n-1}LM([i]) \qquad \tilde{B}_{n+1} := \left(\prod_{i=0}^{n-1}LM([i])\right)\times R([n])\times LM([n]) \end{align*} $$

with the obvious maps for ${\mathsf {ft}}$ and ${\partial }$ . Intuitively, the sets $\tilde {B}_n$ represent term judgements such as (2). The sets $B_n$ represent context judgements.

The definition of substitution for the B-system uses the monad and module substitution operations on R and $LM$ . Specifically, given an element $x \in \tilde {B}_{n+1}$ , and hence in particular, a term $t \in R([n])$ , we obtain a substitution map $\mathbb {S}_x : \mathbb {B}/{\partial } (x) \to \mathbb {B}/{\mathsf {ft}} ({\partial } (x))$ that substitutes the term t for the “last” free variable in any element of $\mathbb {B}$ lying “over” ${\partial } (x)$ . For instance, taking x to be $A_0 \vdash t_1 : A_1$ , the substitution $\mathbb {S}_x$ maps the element $A_0,A_1 \vdash s : A_2$ to $A_0 \vdash s[t_1] : A_2[t_1]$ .

Weakening for R and $LM$ is simply given by the functorial action of R and $LM$ on inclusions of the form $[m] \to [m+1]$ . For weakening in the B-system, consider $X \in B_{1+1}$ to be a context $A_0 \vdash A_1$ . The weakening $\mathbb {W}_X$ maps any context of the form $A_0,A^{\prime }_1,\ldots ,A^{\prime }_n\vdash A^{\prime }_{n+1}$ to the weakened context $A_0,A_1,A^{\prime }_1,\ldots ,A^{\prime }_n\vdash A^{\prime }_{n+1}$ , and similar for elements in $\tilde {B}$ .

For the generic element, consider, for instance, a context $X = A_0 \vdash A_1$ in $B_2$ . This context induces the generic element $A_0,A_1 \vdash \eta (1) : A_1$ , where $\eta (1)\in R([2])$ is the “de Bruijn” variable $1$ bound by $A_1$ in the context, and considered as a term by being wrapped in an application of the monadic unit $\eta $ of the monad R (the inclusion of variables into terms). We have

$$\begin{align*}{\partial} (A_0,A_1 \vdash \textsf{var}(1) : A_1) \enspace = \enspace A_0, A_1 \vdash A_1 \enspace = \enspace W_{A_0 \vdash A_1}(A_0 \vdash A_1).\end{align*}$$

We omit the proof of some of the axioms of a B-frame, which correspond to standard laws of substitution.

Example 2.5 (B-system on finite sets)

Let $[n]$ denote the set $\{0,\ldots ,n-1\}$ and consider the B-frame defined, for each $n \in {\mathbb {N}}$ , by $B_n := \{n\}$ and $\tilde {B}_{n+1} := [n]$ . This B-frame admits the structure of a B-system as follows.

For every $n \in N$ and $x \in \tilde {B}_{n+1}$ , the substitution homomorphism $\mathbb {S}_x \colon \mathbb {B}/(n+1) \to \mathbb {B}/n$ consists of a family of functions $S_{x,j} \colon [n+1+j] \to [n+j]$ , for $j\in {\mathbb {N}}$ , each of which lists all elements in $[n+j]$ repeating the element x in position $n+1$ .

A weakening homomorphism $\mathbb {W}_n \colon \mathbb {B}/n \to \mathbb {B}/(n+1)$ , for $n\in {\mathbb {N}}$ , consists of a family of functions $W_{n,j} \colon [n+j] \to [n+1+j]$ , for $j\in {\mathbb {N}}$ , each of which lists all elements in $[n+1+j]$ except for n.

Finally, the generic elements are the largest elements in each finite set, that is, $\delta _{n} := n \in \tilde {B}_{n+2}$ .

To see how substitution acts on weakening in this setting, take $x \in \tilde {B}_3=[2]$ and consider $\mathbb {S}_x \colon \mathbb {B}/3 \to \mathbb {B}/2$ , $\mathbb {W}_{2+k}$ for $k\in {\mathbb {N}}$ and the composite

(3)

For each $j\in {\mathbb {N}}$ , $W_{2+k,j}$ misses $2+k$ in the image and $S_{x,k+j}$ fixes 0 and 1, maps 2 to x, and maps $3+i$ to $2+i$ for all $i<k+j$ . It is then clear that if $k=0$ the composite in (3) is the identity function. When $k>0$ , the composite in (3) is (one of the functions of) the left-hand side of the right-hand equation in Definition 2.3.1. The equation itself holds since, when $k>0$ , the functions $S_{x,k+j}$ and $W_{2+k,j}$ act non-trivially on disjoint segments of each set $[2+k+j]$ . In practice, the composite is the function that repeats x and misses $2+k$ .

3 C-systems

C-systems were originally introduced by Cartmell with the name contextual categories [3]. A C-system $\mathbb {C}$ consists of a (strict) category $\mathcal {C}$ with a distinguished terminal object 1 such that:

1. 1. There is a wide subcategory ${\mathbf {RT}}(\mathbb {C})$ of $\mathcal {C}$ which has the structure of (a category freely generated by) a rooted tree, where the terminal object $1$ of $\mathcal {C}$ is the root of ${\mathbf {RT}}(\mathbb {C})$ . In particular, each object X comes equipped with a length $\ell (X) \in {\mathbb {N}}$ such that $\ell (X)=0$ if and only if $X=1$ . Otherwise, there is a distinguished arrow ${\mathsf {p}}_X$ with domain X such that $\ell ({\mathrm {cod}}({\mathsf {p}}_X)) = \ell (X)-1$ .

2. 2. For every object $X \neq 1$ and arrow $f \colon Y \to {\mathrm {cod}}({\mathsf {p}}_X)$ there are an object ${f^{*}\!} X$ and an arrow ${\mathsf {q}}(f,X) \colon {{f}^*\!} X \to X$ such that $\mathrm {cod}({\mathsf {p}}_{f^{*X}})=Y$ and the square below is a pullback in $\mathcal {C}$ .

   
   Moreover the choice of ${f^*\!} X$ and ${\mathsf {q}}(f,X)$ is functorial in f.

A morphism of C-systems $\mathbb {C} \to \mathbb {C'}$ consists of a functor $F \colon \mathcal {C} \to \mathcal {C'}$ between the underlying categories that preserves the rooted tree and the choice of pullbacks.

Let ${\mathbf {Csys}}$ denote the category of C-systems and their morphisms.

Example 3.1 (C-systems from Lawvere theories)

Fiore and Voevodsky [4] construct an isomorphism of categories between the category of Lawvere theories and the category of $\ell $ -bijective C-systems, that is, of C-systems whose length function is a bijection. Intuitively, such a C-system can be seen as modelling an untyped (or single-sorted) language.

Example 3.2 (C-systems and contextual categories)

C-systems are equivalent to Cartmell’s contextual categories. In his Ph.D. dissertation, Cartmell [3, Section 2.4] constructs an equivalence between the category of contextual categories and homomorphisms between them and the category of Generalized Algebraic Theories (GATs) and (equivalence classes of) interpretations between them. Hence C-systems are equivalent to GATs.

Example 3.3 (C-system from a universe category)

Voevodsky [9, Construction 2.12] describes a way to construct C-systems out of what he calls universe categories. A universe category is a category with a chosen terminal object and a universe, that is, a morphism $p : {\tilde {\mathcal {U}}} \to {\mathcal {U}}$ together with a choice of pullback of p along any morphism $X \to {\mathcal {U}}$ . Roughly, the C-system constructed from a universe category has, as objects of length n, sequences of n morphisms $f_1,\ldots ,f_n$ into ${\mathcal {U}}$ such that the domain of $f_{i+1}$ is the chosen pullback of p along $f_i$ . Such a sequence can be thought of as a sequence of (dependent) types $(A_1, A_2,\ldots ,A_n)$ such that $A_1,\ldots A_i\vdash A_{i+1}$ . Furthermore, any small C-system can be obtained via this construction; given a C-system $\mathbb {C}$ , a universe can be constructed [9, Construction 5.2] on the presheaf category $\hat {\mathbb {C}}$ such that the C-system obtained from that universe is isomorphic to the C-system $\mathbb {C}$ . For a brief overview of these constructions, see [6, Section 1.3].

Voevodsky’s simplicial model of univalent foundations [6] is built on top of a C-system obtained from a universe in the category of simplicial sets. Also Shulman’s interpretation into an $(\infty ,1)$ -topos [7] uses this construction to define a C-system out of an $(\infty ,1)$ -topos.

Remark 3.4. C-systems are not invariant under equivalence of categories, only under isomorphism of categories. Indeed, the terminal category has a structure of C-system, namely the trivial one. Its equivalent category that consists of two objects and an isomorphism between them does not have the structure of a C-system since taking pullbacks along an arrow of the form ${\mathsf {p}}$ always increases lengths by one.

4 An equivalence between B-systems and C-systems

In this section we briefly sketch a proof of the following result. All details can be found in [1].

Theorem 4.1. The category ${\mathbf {Bsys}}$ of B-systems and the category ${\mathbf {Csys}}$ of C-systems are equivalent.

Given a C-system $\mathbb {C}$ , we can partition the objects of its underlying category $\mathcal {C}$ into sets $(B_n)_n$ according to their length. The rooted tree then provides the maps ${\mathsf {ft}}$ that take an object X of length $n+1$ to the context it depends on, namely the codomain of the arrow ${\mathsf {p}}_X$ . This gives rise to a B-frame by taking as elements of $\tilde {B}_{n+1}$ the sections of the maps ${\mathsf {p}}_X$ for $X \in B_{n+1}$ . Note that pullback along an arrow $f \colon Y \to {\mathsf {ft}} (X)$ maps sections of ${\mathsf {p}}_X$ into sections of ${\mathsf {p}}_{f^{*X}}$ :

Thus the choice of pullbacks along f induces a homomorphism of B-frames. With this observation we obtain substitution and weakening homomorphisms: substituting a term $t \in \tilde {B}_{n+1}$ is defined by taking a pullback along the section t in $\mathbb {C}$ , and weakening by (a variable of) $X\in B_{n+1}$ is defined by taking a pullback along ${\mathsf {p}}_X$ . Finally, generic elements are defined by the universal property of the pullback of ${\mathsf {p}}_X$ along itself. We thus obtain a B-system ${\mathbf {B}}(\mathbb {C})$ (see [1, Section 5.1]).

Conversely, let $\mathbb {B}$ be a B-system. Note first that the functions ${\mathsf {ft}}$ present the elements of the sets $B_n$ as nodes of a rooted tree $\mathbf {RT}(\mathbb {B})$ . More precisely, there is an edge $X \to Y$ if and only if $X\in B_{n+1}, Y \in B_n$ and ${\mathsf {ft}} (X) = Y$ . Thus every vertex has a unique outgoing edge, except for the vertex $\ast \in B_0$ , which is the root of the tree and has no outgoing edge. The arrow ${\mathsf {p}}_X$ of the C-system we are constructing corresponds to the edge $X \to {\mathsf {ft}} (X)$ . We briefly describe how to construct a suitable category “around” the rooted tree $\mathbf {RT}(\mathbb {B})$ , and how to equip it with the structure of a C-system ${\mathbf {C}}(\mathbb {B})$ . For details we refer to [1, Sections 4.3.1 and 5.2]. As we already have the objects, we construct arrows using elements of the sets $\tilde {B}_{n+1}$ . Readers familiar with the construction of the syntactic category of a dependent type theory ([5, Section 2.2 and Example 2.4.2] or [2, Sections 13 and 14]) will recognise the strategy. We first define finite lists of typed terms (a.k.a. context morphisms) out of the elements of the sets $\tilde {B}_{n+1}$ . This is done by defining, at the same time, the action on the sets of $\mathbb {B}$ of what we can think of as the simultaneous substitution of the terms in the list. Simultaneous substitution yields, in particular, a “pre-composition” homomorphism for each such context morphism. The action of pre-composition on terms allows us to define composition of context morphisms, whereas its action on contexts, together with generic elements, allows us to construct a functorial choice of pullbacks.

These two constructions extend to functors ${\mathbf {C}} \colon {\mathbf {Bsys}} \rightleftarrows {\mathbf {Csys}} \ \colon \! {\mathbf {B}}$ . To briefly justify the fact that these functors form an equivalence of categories, note that a context morphism in ${\mathbf {C}}{\mathbf {B}}(\mathbb {C})$ is completely determined by its last component. This establishes a bijection between context morphisms and arrows in $\mathbb {C}$ which then extends to a natural isomorphism of C-systems ${\mathbf {C}}{\mathbf {B}}(\mathbb {C}) \cong \mathbb {C}$ . Details are in [1, Construction 5.39]. Conversely, given a B-system $\mathbb {B}$ , a context morphism which is also a section of a ${\mathsf {p}}_X$ in ${\mathbf {C}}(\mathbb {B})$ is, in particular, a list of length one, i.e., it is a term of $\mathbb {B}$ . This observation establishes an isomorphism of B-frames, which then can be extended to a natural isomorphism of B-systems ${\mathbf {B}}{\mathbf {C}}(\mathbb {B}) \cong \mathbb {B}$ .

5 Conclusion

We have constructed an equivalence between the category of C-systems and the category of B-systems. The equivalence does not rely on classical reasoning principles such as the axiom of choice or excluded middle. This equivalence constitutes a crucial piece in Voevodsky’s research program on the formulation and solution of an initiality conjecture.

Voevodsky has studied different types of constructions on C-systems, in particular, dependent function types [11,14] and identity types [10]. The equivalence constructed in the present paper should be extended to type and term constructors on C-systems and B-systems.