Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 12, 2024

Double Limits: A User’s Guide

Posted by Emily Riehl

Guest post by Matt Kukla and Tanjona Ralaivaosaona

Double limits capture the notion of limits in double categories. In ordinary category theory, a limit is the best way to construct new objects from a given collection of objects related in a certain way. Double limits, extend this idea to the richer structure of double categories. For each of the limits we can think of in an ordinary category, we can ask ourselves: how do these limits look in double categories?

In ordinary category theory, many results can be extended to double categories. For instance, in an ordinary category, we can determine if it has all limits (resp. finite limits) by checking if it has all products and equalizers (resp. binary products, a terminal object, and equalizers) (see Thm 5.1.26 in [3]). In a double category, we need to introduce a new notion of limit, known as a tabulator. One of the main theorems by Grandis and Paré states that a double category has all small double limits if and only if it has small double products, double equalizers, and tabulators. Therefore, these components are sufficient to construct small double limits. To explain this concept thoroughly, we will introduce their definitions in this post. There are various definitions depending on your focus, but for the sake of simplicity, this guide aims to be accessible to anyone with a background in category theory. For an introduction to double categories, see here.

We give an overview of how limits behave in this two-dimensional setting, following Grandis and Paré’s “Limits in double categories.” In particular, we make several definitions more explicit for use in further computations.

Introduction

Recall that double categories consist of two types of morphisms, horizontal and vertical, which interact in a compatible way. Often, composition of one arrow type is weaker than the other. Therefore, we may also think of limits in two different directions. However, limits with respect to the weaker class of morphisms tend to be badly behaved. Hence, in this post, we will only focus on horizontal double limits.

Throughout this article, we will refer to the class of morphisms with strong composition as “arrows,” written horizontally, with composition denoted by \circ. The weaker arrows will be called “proarrows,” written as vertical dashed arrows, and with composition denoted by \bullet. Identity arrows/proarrows for an object XX will be written 1 X\mathbf{1}_X and 1 X \mathbf{1}_X^\bullet respectively. Sometimes, we will also refer to the identity cell associated to an arrow f:XYf:X \to Y. This is obtained by taking both proarrow edges to be the respective vertical identities on objects:

There’s an analogous construction for proarrows, but we won’t need it in this article.

Double limits are defined for double diagrams and a double diagram is a double functor from an indexing double category 𝕀\mathbb{I} to an arbitrary double category 𝔸\mathbb{A}. A limit for a given double diagram DD is a universal double cone over DD. This is a very high-level definition, but we will try to explain each unfamiliar term and illustrate it with examples.

The first thing we need to understand is a double diagram for which we take the limits.

Diagrams

A double diagram in 𝔸\mathbb{A} of shape 𝕀\mathbb{I} is a double functor F:𝕀𝔸F: \mathbb{I}\to \mathbb{A} between double categories 𝕀\mathbb{I} and 𝔸\mathbb{A}. In strict double categories, a double functor is simultaneously a functor on the horizontal and vertical structures, preserving cells as well as their vertical compositions, horizontal compositions, identities. That is, for every cell α:uv\alpha: u\to v,

and for every composable pair of cells α:uv\alpha: u\to v and β:vw\beta: v\to w

  1. preserve horizontal compositions of cells: F(βα)=F(β)F(α)F (\beta \circ \alpha) = F(\beta) \circ F(\alpha),

  2. preserve vertical compositions of cells: F(γα)=F(γ)F(α)F (\gamma \bullet \alpha) = F(\gamma) \bullet F(\alpha),

  3. preserve cell-wise horizontal identity: for each proarrow u:ABu: A\nrightarrow B, F(1 u)=1 FuF(1_u) = 1_{F u},

  4. preserve cell-wise vertical identity: for each arrow f:AAf: A\to A', F(1 f )=1 Ff F(1^{\bullet}_f) = 1^{\bullet}_{F f},

We will also need the notion of a double natural transformation. These are defined componentwise, much in the same way as ordinary natural transformations. For double functors F,G:𝕀𝔸F, G: \mathbb{I} \to \mathbb{A}, a horizontal transformation H:FGH: F \Rightarrow G is given by the following data:

  • horizontal 𝔸\mathbb{A}-arrows Hi:FiGiH i: F i \to G i for every object i𝕀i \in \mathbb{I}

  • an 𝔸\mathbb{A}-cell HuH u for every proarrow u:iju:i \nrightarrow j in 𝕀\mathbb{I} of the shape

double_limits_guide_3.png

  • Identities and composition are preserved.

  • For every cell α𝕀\alpha \in \mathbb{I} with proarrow edges u,vu, v and arrow edges f,gf, g, the component cells of uu and vv satisfy (Fα|Hv)=(Hu|Gα)(F\alpha | H v) = (H u | G \alpha)

Vertical transformations satisfy analogous requirements with respect to vertical morphisms, given Section 1.4 of [1].

We will also use the notion of a modification to define double limits. Suppose we have double functors F,F,G,G:𝕀𝔸F, F', G, G': \mathbb{I} \to \mathbb{A}, horizontal transformations H:FG,K:FGH:F \Rightarrow G, K: F' \Rightarrow G' and vertical transformations U:FF,V:GGU:F \Rightarrow F', V: G \Rightarrow G'. A modification is an assignment of an 𝔸\mathbb{A}-cell μi\mu i to each object i𝕀i \in \mathbb{I}:

such that, for every horizontal f:ijf:i \to j, (μi|Vf)=(Uf|μj)(\mu i| V f) = (U f|\mu j):

Double limits will be defined as a universal double cone. But what are cones or double cones in double categories? You may ask.

Like ordinary categories, cones for a functor FF in double categories also consist of an object XX and morphisms from XX to the objects FiF i, for each object ii of 𝕀\mathbb{I}. Note that there two types of morphisms, those of horizontal direction or arrows and those of vertical direction or proarrows. The morphisms involved in cones are the horizontal ones but must be compatible with vertical ones. Let’s dive into the definition to see how that works.

A double cone for a double functor F:𝕀𝔸F: \mathbb{I}\to \mathbb{A} consists of an XX with arrows p i:XFip_i: X\to F i for each object ii of 𝕀\mathbb{I}, and cells pu:1 X Fup u: \mathbf{1}^{\bullet}_X \to F u for each every proarrow u:iju:i\nrightarrow j, satisfying the following axioms:

  1. for each object ii in 𝕀\mathbb{I}, p(1 i )=1 p i p(\mathbf{1}^{\bullet}_i)= \mathbf{1}^{\bullet}_{p_i}

  2. for each composable pair of proarrows uu and vv in 𝕀\mathbb{I}, p(vu)=pvpup(v\bullet u)=p v\bullet p u

  3. for every cell α:uv\alpha: u\to v in 𝕀\mathbb{I}, (pu|Fα)=pv(p u | F\alpha) = p v

Note that this implies that Ffp i=p jF f\circ p_i = p_j and Fgp k=p lFg\circ p_k = p_l. We can observe that the cells pupu for every uu are made of two green arrows and FuF u, which is indeed a cell such that the horizontal source of pup u is the identity proarrow 1 X \mathbf{1}^{\bullet}_{X}.

For example, let’s take cones for the functor FF from an indexing double category which is the discrete double category (made of only two objects ii and jj), to an arbitrary double category, defined such that Fi=AF i= A and Fj=BF j= B. Then, a double cone XX for FF is a candidate product for AA and BB.

Notice that the above description of a double cone satisfies the requirements of a horizontal transformation. We can consider a constant functor DA:𝕀𝔸D A: \mathbb{I} \to \mathbb{A} at an object AA of 𝔸\mathbb{A}, then the data of a double cone with vertex AA is determined by a horizontal transformation x:DAFx:D A \Rightarrow F. The componentwise definition of xx unrolls to precisely the conditions specified above.

We have now all the setup needed for defining double limits, since as we mentioned above, double limits are universal double cones. That is, a double cone for an underlying functor FF through which any other double cones factor.

Double Limits

Limits

Let F:𝕀𝔸F: \mathbb{I} \to \mathbb{A} be a double functor. The (horizontal) double limit of FF is a universal cone (A,x)(A,x) for FF.

Explicitly, this requires several things:

  • For any other double cone (A,x)(A', x'), there exists a unique arrow c:AAc:A' \to A in 𝔸\mathbb{A} with xDc=xx \circ D c = x' (where DD is the constant functor at the vertex of AA)

  • Let (A,x),(A,x)(A', x'), (A'', x'') be double cones with a proarrow u:AAu: A' \nrightarrow A''. For every collection of cell η i\eta_i where ii is an object of 𝕀\mathbb{I}, associated to components of each cone, which organize into a modification, there exists a unique 𝔸\mathbb{A}-cell τ\tau such that (τ|xi)=η i(\tau | x i) = \eta_i:

In other words, a cell built from a proarrow and the components of two cones (viewed as natural transformations) can be factored uniquely via τ\tau and 1 1^\bullet.

To get a better feel for double limits in practice, let’s examine (binary) products in a double category. Just as in 1-category theory, products are constructed as the double limit of the diagram \bullet \ \bullet (two discrete objects). Spelling out the universal properties of a double limit, the (double) product of objects A,B𝔸A, B \in \mathbb{A} consists of an object A×BA \times B which satisfies the usual requirements for a product with respect to horizontal morphisms (with projection maps π A,π B\pi_A, \pi_B. Additionally, given cells α,β\alpha, \beta as below:

there exists a unique cell α×β\alpha \times \beta such that

An identical condition must also hold for BB and π B\pi_B.

Equalizers can be extended to the double setting in a similar manner. Taking the double limit of the diagram \bullet \rightrightarrows \bullet yields double equalizers. For horizontal f,g:ABf,g: A \rightrightarrows B in 𝔸\mathbb{A}, the double equalizer of ff and gg consists of an object Eq(f,g)Eq(f,g) equipped with a horizontal arrow e:Eq(f,g)Ae:Eq(f,g) \to A, which is the equalizer of f,gf,g in the ordinary sense with respect to horizontal arrows. Additionally, for every cell η\eta with (η|1 f )=(η|1 g )(\eta | \mathbf{1}^\bullet_f) = (\eta | \mathbf{1}^\bullet_g), there exists a unique τ\tau such that (τ|1 )=η(\tau | \mathbf{1}^\bullet) = \eta:

Tabulators

Until now, we have considered examples of double limits of diagrams built from horizontal morphisms. Tabulators bring proarrows into the mix. They are an interesting case obtained as the limit over the diagram consisting of a single proarrow: \bullet \nrightarrow \bullet.

Suppose that u:ABu:A \nrightarrow B is a proarrow. The tabulator of uu is the double limit of the diagram consisting of just uu. Unrolling the limit, this amounts to an object TuT u along with a cell τ\tau:

such that, for any cell η\eta of the following shape,

there exists a unique horizontal morphism f:CTf: C \to T such that (1 f |τ)=η(1^\bullet_f | \tau) = \eta:

Additionally, any proarrow v:CDv: C \nrightarrow D with horizontal morphisms to AA and BB forming a tetrahedron can be uniquely factored through TuT u:

In an ordinary category, the existence of all finite products and equalizers is enough to guarantee the existence of all limits. However, in the double setting, we need something extra: tabulators. The following result gives us a similar condition for limits in double categories.

Theorem (5.5 in [1]): A double category 𝔸\mathbb{A} has all small double limits if and only if it has small double products, equalizers, and tabulators.

Examples in elset\mathbb{R}\text{elset}

In this section, we consider the double category elset\mathbb{R}\text{elset} of sets with functions as horizontal morphisms and relations as vertical morphisms, for more information see [1].

Tabulators

A tabulator for a proarrow or relation RA×BR\subseteq A\times B is RR itself with the projection maps p 1:RAp_1: R\to A and p 2:RBp_2: R\to B. For every other double cone (C,q)=(C,q 1,q 2)(C, q)= (C,q_1,q_2) of RR, there exists a unique function or arrow h=q 1,q 2:CTRh= \langle q_1, q_2\rangle : C\to T R (TR=RT R= R), such that q i=p ihq_i = p_i\circ h; and for every relation SC×DS\subseteq C\times D and such that (D,t)=(D,t 1,t 2)(D, t)= (D,t_1,t_2) is also a double cone for RR, there exists a unique cell η=(SR):S1 R \eta = (S R): S\to \mathbf{1}^{\bullet}_{R}, such that (η|pR)=q 1t 2(\eta | p R) = q_1 \nrightarrow t_2.

Product

The double product of two sets AA and BB is the cartesian product with the usual projection maps and we also have the following:

References

[1] Grandis, Marco, and Robert Paré. "Limits in double categories." Cahiers de topologie et géométrie différentielle catégoriques 40.3 (1999): 162-220.

[2] Patterson, Evan. “Products in double categories, revisited.” arXiv preprint arXiv:2401.08990 (2024).

[3] Leinster, Tom. “Basic category theory.” arXiv preprint arXiv:1612.09375 (2016).|

Posted at July 12, 2024 9:06 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3542

0 Comments & 0 Trackbacks

Post a New Comment