A Formalization of Higher-Order Categories in Lean 4

2 Single-sorted presentation of higher-order categories

In the single-sorted presentation of higher-order categories, objects, morphisms, 2-morphisms, and all higher morphisms live in a single set, distinguished by source and target operations at each dimension. Also, composition at each dimension is defined as a partial operation that is only defined when appropriate source-target matching conditions are satisfied. In this chapter, we present the very basic definitions and axioms of single-sorted categories and single-sorted functors between them, concluding with the definition of the category of single-sorted categories itself.

2.1 Single-sorted categories

We start by defining the necessary data for defining a single-sorted category.

Definition 2.1 Single-sorted category structure

Let \(C\) be a set whose elements will be called morphisms. The required data for defining a single-sorted \(\mathcal{I}\)-category structure on \(C\) consists of:

  1. A unary operation \(\operatorname{sc}^k \colon C \to C\) for each index \(k \in \mathcal{I}\), called the source at dimension \(k\).

  2. A unary operation \(\operatorname{tg}^k \colon C \to C\) for each index \(k \in \mathcal{I}\), called the target at dimension \(k\).

  3. A partial binary operation \(\operatorname{\# }^k \colon C \times C \rightharpoonup C\) for each index \(k \in \mathcal{I}\), called the composition at dimension \(k\).

The composition \(g \operatorname{\# }^k f\) is defined if and only if \(\operatorname{sc}^k (g) = \operatorname{tg}^k (f)\), in which case we say that \(g\) and \(f\) are composable at dimension \(k\).

We will represent the above data as a tuple \(\mathsf{C} = (C, (\operatorname{sc}^k, \operatorname{tg}^k, \operatorname{\# }^k)_{k \in \mathcal{I}})\).

We split the axioms of single-sorted categories into two parts: first, those concerning only one dimension at a time, and then those concerning the interaction between different dimensions. This division is made by first defining the notion of pre-single-sorted category:

Definition 2.2 Pre-single-sorted category

A pre-single-sorted \(\mathcal{I}\)-category is a tuple

\[ \mathsf{C} = (C, (\operatorname{sc}^k, \operatorname{tg}^k, \operatorname{\# }^k)_{k \in \mathcal{I}}), \]

satisfying, for each index \(k \in \mathcal{I}\), the following axioms:

  1. For all \(f \in C\),

    \begin{align*} \operatorname{sc}^k (\operatorname{sc}^k (f)) = \operatorname{sc}^k (f), \qquad & \operatorname{tg}^k (\operatorname{sc}^k (f)) = \operatorname{sc}^k (f), \\ \operatorname{sc}^k (\operatorname{tg}^k (f)) = \operatorname{tg}^k (f), \qquad & \operatorname{tg}^k (\operatorname{tg}^k (f)) = \operatorname{tg}^k (f). \end{align*}
  2. For all \(f, g \in C\), if \(g\) and \(f\) are composable, then

    \begin{align*} \operatorname{sc}^k (g \operatorname{\# }^k f) = \operatorname{sc}^k (f), \qquad & \operatorname{tg}^k (g \operatorname{\# }^k f) = \operatorname{tg}^k (g). \end{align*}
  3. For all \(f \in C\), the morphisms \(f\) and \(\operatorname{sc}^k (f)\) are composable and

    \[ f \operatorname{\# }^k \operatorname{sc}^k (f) = f. \]
  4. For all \(f \in C\), the morphisms \(\operatorname{tg}^k (f)\) and \(f\) are composable and

    \[ \operatorname{tg}^k (f) \operatorname{\# }^k f = f. \]
  5. For all \(f, g, h \in C\), if \(h\) and \(g\) are composable, and \(g\) and \(f\) are composable, then \(h \operatorname{\# }^k g\) and \(f\) and \(h\) and \(g \operatorname{\# }^k f\) are composable, and

    \[ (h \operatorname{\# }^k g) \operatorname{\# }^k f = h \operatorname{\# }^k (g \operatorname{\# }^k f). \]

We finally define a single-sorted category structure by extending the above definition with the axioms concerning the interaction between different dimensions:

Definition 2.3 Single-sorted category

A single-sorted \(\mathcal{I}\)-category is a pre-single-sorted \(\mathcal{I}\)-category \(\mathsf{C} = (C, (\operatorname{sc}^k, \operatorname{tg}^k, \operatorname{\# }^k)_{k \in \mathcal{I}})\) satisfying, in addition to the axioms of pre-single-sorted categories, the following cross-dimensional axioms, for all indices \(k, j \in \mathcal{I}\) with \(j {\lt} k\):

  1. For all \(f \in C\),

    \begin{align*} \operatorname{sc}^k (\operatorname{sc}^j (f)) = \operatorname{sc}^j (f), \qquad & \operatorname{sc}^j (\operatorname{sc}^k (f)) = \operatorname{sc}^j (f), \\ \operatorname{sc}^j (\operatorname{tg}^k (f)) = \operatorname{sc}^j (f), \qquad & \operatorname{tg}^k (\operatorname{tg}^j (f)) = \operatorname{tg}^j (f), \\ \operatorname{tg}^j (\operatorname{tg}^k (f)) = \operatorname{tg}^j (f), \qquad & \operatorname{tg}^j (\operatorname{sc}^k (f)) = \operatorname{tg}^j (f). \end{align*}
  2. For all \(f, g \in C\), if \(g\) and \(f\) are composable at dimension \(j\), then \(\operatorname{sc}^k (g)\) and \(\operatorname{sc}^k (f)\) and \(\operatorname{tg}^k (g)\) and \(\operatorname{tg}^k (f)\) are also composable at dimension \(j\), and

    \begin{align*} \operatorname{sc}^k (g \operatorname{\# }^j f) = \operatorname{sc}^k (g) \operatorname{\# }^j \operatorname{sc}^k (f), \\ \operatorname{tg}^k (g \operatorname{\# }^j f) = \operatorname{tg}^k (g) \operatorname{\# }^j \operatorname{tg}^k (f). \end{align*}
  3. For all \(f_1, f_2, g_1, g_2 \in C\), suppose that:

    • \(g_2\) and \(f_2\) are composable at dimension \(j\),

    • \(g_1\) and \(f_1\) are composable at dimension \(j\),

    • \(g_2\) and \(g_1\) are composable at dimension \(k\), and

    • \(f_2\) and \(f_1\) are composable at dimension \(k\).

    Then, the morphisms \((g_2 \operatorname{\# }^j f_2)\) and \((g_1 \operatorname{\# }^j f_1)\) are composable at dimension \(k\), and the morphisms \((g_2 \operatorname{\# }^k g_1)\) and \((f_2 \operatorname{\# }^k f_1)\) are composable at dimension \(j\), and

    \[ (g_2 \operatorname{\# }^j f_2) \operatorname{\# }^k (g_1 \operatorname{\# }^j f_1) = (g_2 \operatorname{\# }^k g_1) \operatorname{\# }^j (f_2 \operatorname{\# }^k f_1). \]

    That is, composing first at dimension \(j\) and then at dimension \(k\) yields the same result as composing first at dimension \(k\) and then at dimension \(j\).

Definition 2.4 Single-sorted finite category

Given a natural number \(n \in \mathbb {N}\), a single-sorted \(n\)-category is a single-sorted category indexed by the finite set \(n = \left\{ 0, 1, \ldots , n-1 \right\} \).

Definition 2.5 Pre-single-sorted one-categories lifting

Any pre-single-sorted \(1\)-category is, in fact, a single-sorted \(1\)-category. Since the index set \(1 = \left\{ 0 \right\} \) has exactly one element, there are no pairs of distinct indices \(j {\lt} k\), so all cross-dimensional axioms are vacuously satisfied.

We now define the notion of cell or identity morphism at a given dimension in a single-sorted category.

Let \(\mathsf{C}\) be a single-sorted \(\mathcal{I}\)-category and \(k \in \mathcal{I}\). We say that a morphism \(f \in C\) is a \(k\)-cell or identity morphism at dimension \(k\) if and only if

\[ \operatorname{sc}^k (f) = f. \]

We will denote the set of \(k\)-cells of \(\mathsf{C}\) by \(C_k\).

The above definition defines \(k\)-cells using the source operation, however, it is also possible to define them using the target operation and, using the axioms of single-sorted categories, one can prove that both definitions are equivalent.

Definition 2.7 Target-based cell

Let \(\mathsf{C}\) be a single-sorted \(\mathcal{I}\)-category and \(k \in \mathcal{I}\). A morphism \(f \in C\) is a target-based \(k\)-cell if and only if

\[ \operatorname{tg}^k (f) = f. \]

Let \(\mathsf{C}\) be a single-sorted \(\mathcal{I}\)-category and \(k \in \mathcal{I}\). A morphism \(f \in C\) is a \(k\)-cell if and only if it is a target-based \(k\)-cell.

It follows that the set of \(k\)-cells \(C_k\) is equal to the set of target-based \(k\)-cells.

Proof

Let \(f \in C\). Suppose first that \(f\) is a \(k\)-cell, i.e., \(\operatorname{sc}^k (f) = f\). By Axiom 2.2.1, we have that

\[ \operatorname{tg}^k (f) = \operatorname{tg}^k (\operatorname{sc}^k (f)) = \operatorname{sc}^k (f) = f, \]

so \(f\) is a target-based \(k\)-cell.

Conversely, suppose that \(f\) is a target-based \(k\)-cell, i.e., \(\operatorname{tg}^k (f) = f\). By Axiom 2.2.1, we have that

\[ \operatorname{sc}^k (f) = \operatorname{sc}^k (\operatorname{tg}^k (f)) = \operatorname{tg}^k (f) = f, \]

so \(f\) is a \(k\)-cell.

Definition 2.9 Single-sorted omega category

A single-sorted \(\omega \)-category is a single-sorted category indexed by the set of natural numbers \(\mathbb {N}\), satisfying and additional axiom: for all \(f \in C\), there exists a dimension \(k \in \mathbb {N}\) such that \(f\) is a \(k\)-cell.

2.2 Single-sorted functors

Unlike in the many-sorted presentation, where a functor consists of a family of maps — one for each set of morphisms — a single-sorted functor is simply a single map on the set of all morphisms, since all morphisms live in a single set. Such a map must preserve sources, targets, and composition at each dimension.

Definition 2.10 Single-sorted functor

Let \(\mathsf{C} = (C, (\operatorname{sc}^k, \operatorname{tg}^k, \operatorname{\# }^k)_{k \in \mathcal{I}})\) and \(\mathsf{D} = (D, (\operatorname{sc}^k, \operatorname{tg}^k, \operatorname{\# }^k)_{k \in \mathcal{I}})\) be single-sorted \(\mathcal{I}\)-categories. A single-sorted \(\mathcal{I}\)-functor from \(\mathsf{C}\) to \(\mathsf{D}\) is a map \(F \colon C \to D\), written \(F \colon \mathsf{C} \to \mathsf{D}\), satisfying, for each index \(k \in \mathcal{I}\), the following preservation properties:

  1. For all \(f \in C\),

    \[ F (\operatorname{sc}^k (f)) = \operatorname{sc}^k (F (f)), \qquad F (\operatorname{tg}^k (f)) = \operatorname{tg}^k (F (f)). \]
  2. For all \(f, g \in C\), if \(g\) and \(f\) are composable at dimension \(k\), then \(F (g)\) and \(F (f)\) are also composable at dimension \(k\), and

    \[ F (g \operatorname{\# }^k f) = F (g) \operatorname{\# }^k F (f). \]

We can define composition of single-sorted functors as the usual composition of functions, and the identity single-sorted functor as the identity function on the set of morphisms.

Definition 2.11 Composition of single-sorted functors

Let \(\mathsf{C}, \mathsf{D}, \mathsf{E}\) be single-sorted \(\mathcal{I}\)-categories, and let \(F \colon \mathsf{C} \to \mathsf{D}\) and \(G \colon \mathsf{D} \to \mathsf{E}\) be single-sorted \(\mathcal{I}\)-functors. Then, the composition \(G \circ F \colon \mathsf{C} \to \mathsf{E}\) is also a single-sorted \(\mathcal{I}\)-functor.

Proof

Let \(k \in \mathcal{I}\). For all \(f \in C\), since \(F\) and \(G\) are single-sorted functors, we have that

\[ \begin{split} (G \circ F) (\operatorname{sc}^k (f)) & = G (F (\operatorname{sc}^k (f))) \\ & = G (\operatorname{sc}^k (F (f))) \\ & = \operatorname{sc}^k (G (F (f))) \\ & = \operatorname{sc}^k ((G \circ F) (f)), \end{split} \]

and similarly,

\[ \begin{split} (G \circ F) (\operatorname{tg}^k (f)) & = G (F (\operatorname{tg}^k (f))) \\ & = G (\operatorname{tg}^k (F (f))) \\ & = \operatorname{tg}^k (G (F (f))) \\ & = \operatorname{tg}^k ((G \circ F) (f)), \end{split} \]

that is, \(G \circ F\) preserves sources and targets at dimension \(k\).

Now, let \(f, g \in C\) be composable at dimension \(k\). We have that

\[ \begin{split} (G \circ F) (g \operatorname{\# }^k f) & = G (F (g \operatorname{\# }^k f)) \\ & = G (F (g) \operatorname{\# }^k F (f)) \\ & = G (F (g)) \operatorname{\# }^k G (F (f)) \\ & = (G \circ F) (g) \operatorname{\# }^k (G \circ F) (f), \end{split} \]

so \(G \circ F\) preserves composition at dimension \(k\).

Definition 2.12 Identity single-sorted functor

Let \(\mathsf{C}\) be a single-sorted \(\mathcal{I}\)-category. Then, the identity function \(\operatorname{id}_C \colon C \to C\), written \(\operatorname{id}_{\mathsf{C}} \colon \mathsf{C} \to \mathsf{C}\), is a single-sorted \(\mathcal{I}\)-functor from \(\mathsf{C}\) to itself.

Proof

It trivially follows from reflexivity.

Definition 2.13 Single-sorted finite functor

Given a natural number \(n \in \mathbb {N}\), a single-sorted \(n\)-functor is a single-sorted functor between single-sorted \(n\)-categories.

Definition 2.14 Single-sorted omega functor

A single-sorted \(\omega \)-functor is a single-sorted functor between single-sorted \(\omega \)-categories.

2.3 The category of single-sorted categories

Lastly, we define the category whose objects are single-sorted categories and whose morphisms are single-sorted functors.

Definition 2.15 Category of single-sorted categories

The category of single-sorted \(\mathcal{I}\)-categories, denoted by \(\mathcal{I}\mathsf{Cat}\), is defined as follows:

  1. Its objects are single-sorted \(\mathcal{I}\)-categories.

  2. Its morphisms are single-sorted \(\mathcal{I}\)-functors between single-sorted \(\mathcal{I}\)-categories.

  3. Composition of morphisms is given by composition of single-sorted functors.

  4. The identity morphism for each object is given by the identity single-sorted functor.

Proof

Composition and the identity functor are well defined by Definitions 2.11 and 2.12, respectively. The required category laws trivially follow from the corresponding properties of function composition.

Definition 2.16 Category of single-sorted finite categories

Given a natural number \(n \in \mathbb {N}\), the category of single-sorted \(n\)-categories, denoted by \(n\mathsf{Cat}\), is the particular case of Definition 2.15 where \(\mathcal{I}\) is the finite set \(n\). Its objects are single-sorted \(n\)-categories and its morphisms are single-sorted \(n\)-functors.

Proof

This is a particular case of Definition 2.15, so the result follows immediately.

Definition 2.17 Category of single-sorted omega categories

The category of single-sorted \(\omega \)-categories, denoted by \(\omega \mathsf{Cat}\), is the particular case 1 of Definition 2.15 where \(\mathcal{I}\) is the set of natural numbers \(\mathbb {N}\). Its objects are single-sorted \(\omega \)-categories and its morphisms are single-sorted \(\omega \)-functors.

Proof

This is a particular case of Definition 2.15, so the result follows immediately.

Notation 2.18
#

We extend the notation \(n\mathsf{Cat}\) to all \(n \in \overline{\mathbb {N}}\), understanding that,

  • if \(n \in \mathbb {N}\), this is the category \(n\mathsf{Cat}\) of Definition 2.16, and

  • if \(n = \omega \), this denotes \(\omega \mathsf{Cat}\) of Definition 2.17.

  1. Strictly speaking, \(\omega \mathsf{Cat}\) is not exactly a particular case of Definition 2.15 with \(\mathcal{I}= \mathbb {N}\): a single-sorted \(\omega \)-category is not merely a single-sorted \(\mathbb {N}\)-category, but one satisfying the additional axiom that every morphism is a \(k\)-cell for some \(k \in \mathbb {N}\). Thus, the objects of \(\omega \mathsf{Cat}\) form a subclass of those of \(\mathbb {N}\mathsf{Cat}\). The categorical structure (composition, identity, and laws), however, is inherited directly.