Internal Language of Indexed Monoidal Categories

July 6, 2020 02:00 UTC (Last updated on April 13, 2023 10:11 UTC)

Tags: math, category theory

Introduction

This is part 2 in a series. See the previous part about internal languages for (non-indexed) monoidal categories. The main application I have in mind – enriching in indexed monoidal categories – is covered in the next post.

As Jean Bénabou pointed out in Fibered Categories and the Foundations of Naive Category Theory (PDF) notions of “families of objects/arrows” are ubiquitous and fundamental in category theory. One of the more noticeable places early on is in the definition of a natural transformation as a family of arrows. However, even in the definition of category, identities and compositions are families of functions, or, in the enriched case, arrows of $$. From a foundational perspective, one place where this gets really in-your-face is when trying to formalize the notion of (co)completeness. It is straightforward to make a first-order theory of a finitely complete category, e.g. this one. For arbitrary products and thus limits, we need to talk about families of objects. To formalize the usual meaning of this in a first-order theory would require attaching an entire first-order theory of sets, e.g. ZFC, to our notion of complete category. If your goals are of a foundational nature like Bénabou’s were, then this is unsatisfactory. Instead, we can abstract out what we need of the notion of “family”. The result turns out to be equivalent to the notion of a fibration.

My motivations here are not foundational but leaving the notion of “family” entirely meta-theoretical means not being able to talk about it except in the semantics. Bénabou’s comment suggests that at the semantic level we want not just a monoidal category, but a fibration of monoidal categories¹. At the syntactic level, it suggests that there should be a built-in notion of “family” in our language. We accomplish both of these goals by formulating the internal language of an indexed monoidal category.

As a benefit, we can generalize to other notions of “family” than set-indexed families. We’ll clearly be able to formulate the notion of an enriched category. It’s also clear that we’ll be able to formulate the notion of an indexed category. Of course, we’ll also be able to formulate the notion of a category that is both enriched and indexed which includes the important special case of an internal category. We can also consider cases with trivial indexing which, in the unenriched case, will give us monoids, and in the $$-enriched case will give us rings.

Indexed Monoidal Categories

Following Shulman’s Enriched indexed categories, let $$ be a category with a cartesian monoidal structure, i.e. finite products. Then an $$-indexed monoidal category is simply a pseudofunctor $$. A pseudofunctor is like a functor except that the functor laws only hold up to isomorphism, e.g. $$. $$ is the $$-category of monoidal categories, strong monoidal functors², and monoidal natural transformations. We’ll write $$ as $$ and $$ as $$. We’ll never have multiple relevant indexed monoidal categories so this notation will never be ambiguous. We’ll call the categories $$ fiber categories and the functors $$ reindexing functors. The cartesian monoidal structure on $$ becomes relevant when we want to equip the total category, $$, (computed via the Grothendieck construction in the usual way) with a monoidal structure. In particular, the tensor product of $$ and $$ is an object $$ calculated as $$ where $$ is the monoidal tensor in $$. The unit, $$, is the unit $$.

The two main examples are: $$ where $$ is a (non-indexed) monoidal category and $$ where $$ is a category with finite limits. $$ is a $$-indexed monoidal category with $$ defined as the category of $$-indexed families of objects of $$, families of arrows between them, and an index-wise monoidal product. We can identify $$ with the functor category $$ where $$ takes a set $$ to a small discrete category. Enriching in indexed monoidal category $$ will be equivalent to enriching in the non-indexed monoidal category $$, i.e. the usual notion of enrichment in a monoidal category. $$ is an $$-indexed monoidal category and $$ is the slice category $$ with its cartesian monoidal structure. $$ is the pullback functor. $$-enriched categories are categories internal to $$. A third example we’ll find interesting is $$ for a (non-indexed) monoidal category, $$, which is a $$-indexed monoidal category, which corresponds to an object of $$, namely $$.

The Internal Language of Indexed Monoidal Categories

This builds on the internal language of a monoidal category described in the previous post. We’ll again have linear types and linear terms which will be interpreted into objects and arrows in the fiber categories. To indicate the dependence on the indexing, we’ll use two contexts: $$ will be an index context containing index types and index variables, which will be interpreted into objects and arrows of $$, while $$, the linear context, will contain linear types and linear variables as before except now linear types will be able to depend on index terms. So we’ll have judgements that look like: $$ The former indicates that $$ is a linear type indexed by the index variables of $$. The latter states that $$ is a linear term of linear type $$ in the linear context $$ indexed by the index variables of $$. We’ll also have judgements for index types and index terms: $$ The former asserts that $$ is an index type. The latter asserts that $$ is an index term of index type $$ in the index context $$.

Since each fiber category is monoidal, we’ll have all the rules from before just with an extra $$ hanging around. Since our indexing category, $$, is also monoidal, we’ll also have copies of these rules at the level of indexes. However, since $$ is cartesian monoidal, we’ll also have the structural rules of weakening, exchange, and contraction for index terms and types. To emphasize the cartesian monoidal structure of indexes, I’ll use the more traditional Cartesian product and tuple notation: $$ and $$. This notation allows a bit more uniformity as the $$ case can be notated by $$.

The only really new rule is the rule that allows us to move linear types and terms from one index context to another, i.e. the rule that would correspond to applying a reindexing functor. I call this rule Reindex and, like Cut, it will be witnessed by substitution. Like Cut, it will also be a rule which we can eliminate. At the semantic level, this elimination corresponds to the fact that to understand the interpretation of any particular (linear) term, we can first reindex everything, i.e. all the interpretations of all subterms, into the same fiber category and then we can work entirely within that one fiber category. The Reindex rule is: $$

By representing reindexing by syntactic substitution, we’re requiring the semantics of (linear) type and term formation operations to be respected by reindexing functors. This is exactly the right thing to do as the appropriate notion of, say, indexed coproducts, which would correspond to sum types, is coproducts in each fiber category which are preserved by reindexing functors.

Below I provide a listing of rules and equations.

Relation to Parameterized and Dependent Types

None of this section is necessary for anything else.

This notion of (linear) types and terms being indexed by other types and terms is reminiscent of parametric types or dependent types. The machinery of indexed/fibered categories is also commonly used in the categorical semantics of parameterized and dependent types. However, there are important differences between those cases and our case.

In the case of parameterized types, we have types and terms that depend on other types. In this case, we have kinds, which are “types of types”, which classify types which in turn classify terms. If we try to set up an analogy to our situation, index types would correspond to kinds and index terms would correspond to types. The most natural thing to continue would be to have linear terms correspond to terms, but we start to see the problem. Linear terms are classified by linear types, but linear types are not index terms. They don’t even induce index terms. In the categorical semantics of parameterized types, this identification of types with (certain) expressions classified by kinds is handled by the notion of a generic object. A generic object corresponds to the kind $$ (what Haskell calls *). The assumption of a generic object is a rather strong assumption and one that none of our example indexed monoidal categories support in general.

A similar issue occurs when we try to make an analogy to dependent types. The defining feature of a dependent type system is that types can depend on terms. The problem with such a potential analogy is that linear types and terms do not induce index types and terms. A nice way to model the semantics of dependent types is the notion of a comprehension category. This, however, is additional structure beyond what we are given by an indexed monoidal category. However, comprehension categories will implicitly come up later when we talk about adding $$-indexed (co)products. These comprehension categories will share the same index category as our indexed monoidal categories, namely $$, but will have different total categories. Essentially, a comprehension category shows how objects (and arrows) of a total category can be represented in the index category. We can then talk about having (co)products in a different total category with same index category with respect to those objects picked out by the comprehension category. We get dependent types in the case where the total categories are the same. (More precisely, the fibrations are the same.) Sure enough, we will see that when $$ has $$-indexed products, then $$ is, indeed, a model of a dependent type theory. In particular, it is locally cartesian closed.

Rules for an Indexed Monoidal Category

$$

Equations

$$

$$ means $$ is a primitive index type in the signature. $$ means that $$ is a primitive linear type in the signature. $$ and $$ mean that $$ and $$ are assigned these types in the signature. In the latter case, it is assumed that $$ for $$ and $$. Alternatively, these assumptions could be added as additional hypotheses to the PrimTerm rule. Generally, every $$ will be used in some $$ or in $$, though this isn’t technically required.

As before, I did not write the usual laws for equality (reflexivity and indiscernability of identicals) but they also should be included.

See the discussion in the previous part about the commuting conversion ($$) rules.

A theory in this language is free to introduce additional index types, operations on indexes, linear types, and linear operations.

Interpretation into an $$-indexed monoidal category

Fix an $$-indexed monoidal category $$. Write $$ for the (overloaded) interpretation function. Its value on primitive operations is left as a parameter.

Associators for the semantic $$ and $$ will be omitted below.

Interpretation of Index Types

$$

Interpretation of Index Terms

$$

Witnesses of Index Derivations

IxAx is witnessed by identity, and IxCut by composition in $$. Weakening is witnessed by projection. Exchange and Contraction are witnessed by expressions that can be built from projections and tupling. This is very standard.

Interpretation of Linear Types

$$

Interpretation of Linear Terms

$$

Witnesses of Linear Derivations

As with the index derivations, Ax is witnessed by the identity, in this case in $$.

$$ witnesses Cut.

Roughly speaking, Reindex is witnessed by $$. If we were content to restrict ourselves to semantics in $$-indexed monoidal categories witnessed by functors, as opposed to pseudofunctors, into strict monoidal categories, then this would suffice. For an arbitrary $$-indexed monoidal category, we can’t be sure that the naive interpretation of $$, i.e. $$, which we’d get from two applications of the Reindex rule, is the same as the interpretation of $$, i.e. $$, which we’d get from IxCut followed by Reindex. On the other hand, $$ is simply true syntactically by the definition of substitution (which I have not provided but is the obvious, usual thing). There are similar issues for (meta-)equations like $$ and $$.

The solution is that we essentially use a normal form where we eliminate the uses of Reindex. These normal form derivations will be reached by rewrites such as: $$

Semantically, this is witnessed by the strong monoidal structure, i.e. $$. We need such rewrites for all (linear) rules that can immediately precede Reindex in a derivation. For $$, $$, $$, and, as we’ve just seen, $$, these rewrites are witnessed by $$ being a strong monoidal functor. The rewrites for $$ and $$ are witnessed by functorality of $$ and also strong monoidality for Cut. Finally, two adjacent uses of Reindex become an IxCut and a Reindex and are witnessed by the pseudofunctoriality of $$. (While we’re normalizing, we may as well eliminate Cut and IxCut as well.)

---

1. As the previous post alludes, monoidal structure is more than we need. If we pursue the generalizations described there in this indexed context, we eventually end up at augmented virtual double categories or virtual equipment.↩︎

2. The terminology here is a mess. Leinster calls strong monoidal functors “weak”. “Strong” also refers to tensorial strength, and it’s quite possible to have a “strong lax monoidal functor”. (In fact, this is what applicative functors are usually described as, though a strong lax closed functor would be a more direct connection.) Or the functors we’re talking about which are not-strong strong monoidal functors…↩︎