Created
August 12, 2023 05:38
-
-
Save bmorphism/98345fd11139d0d12feeed6d4796da3c to your computer and use it in GitHub Desktop.
This is to facilitate interactions with tool-using agents that can retrieve into context the bundle informing of various obstructions to compositionality to avoid in the neuro-symbolic architecture
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \title{ | |
| Obstructions to Compositionality | |
| } | |
| \author{ | |
| Caterina Puca \\ Quantinuum* \\ [email protected] | |
| } | |
| \author{ | |
| Amar Hadzihasanovic \\ ${ }^{1}$ Quantinuum* \\ 2 Tallinn University of Technology \\ amar . [email protected] \\ Bob Coecke \\ Quantinuum* \\ [email protected] | |
| } | |
| \author{ | |
| Fabrizio Genovese \\ 20squares \\ noreply@20squares . xyz | |
| } | |
| Compositionality is at the heart of computer science and several other areas of applied category theory such as computational linguistics, categorical quantum mechanics, interpretable AI, dynamical systems, compositional game theory, and Petri nets. However, the meaning of the term seems to vary across the many different applications. This work contributes to understanding, and in particular qualifying, different kinds of compositionality. | |
| Formally, we introduce invariants of categories that we call zeroth and first homotopy posets, generalising in a precise sense the $\pi_{0}$ and $\pi_{1}$ of a groupoid. These posets can be used to obtain a qualitative description of how far an object is from being terminal and a morphism is from being iso. In the context of applied category theory, this formal machinery gives us a way to qualitatively describe the "failures of compositionality", seen as failures of certain (op)lax functors to be strong, by classifying obstructions to the (op)laxators being isomorphisms. | |
| Failure of compositionality, for example for the interpretation of a categorical syntax in a semantic universe, can both be a bad thing and a good thing, which we illustrate by respective examples in graph theory and quantum theory. | |
| Acknowledgements A.H. was supported by the ESF funded Estonian IT Academy research measure (project 2014-2020.4.05.19-0001) and by the Estonian Research Council grant PSG764. We thank Sean Tull and Robin Lorenz for helpful comments on an earlier draft. | |
| \section{Introduction} | |
| Compositionality is probably the most relevant principle in applied category theory (ACT) research. While there is no unified definition $[1,14,6]$, it refers, broadly speaking, to certain forms of relation between properties, behaviours, or observations of a composite system on one hand, and those of its components on the other. A common concern, in this context, is whether it is possible to derive properties of the whole from properties of its parts, and vice versa. In some cases, both directions are viable and inverse to each other, in which case a property is "fully compositional". More frequently, only one direction is viable. | |
| The need to formally quantify and/or qualify compositionality has been widely discussed in the ACT community at least since 2018 [13], as researchers became increasingly aware of various "failures of compositionality", and wished to classify them beyond a simple yes-or-no statement. | |
| Let us be more precise. Much research in ACT has been devoted to the study of open systems, that is, entities with open interfaces that can be composed with other entities of the same kind. This approach | |
| *17 Beaumont Street, Oxford OX1 2NA, United Kingdom | |
| Submitted to: | |
| ACT 2023 has been pervasive, and has been applied in the study of categorical quantum mechanics [2], natural language [7], dynamical systems [12], Petri nets [5], game theory [14] and many other subjects. When studying open systems, it is not rare to define functors mapping a "theory of boxes" - in the form of a monoidal category or bicategory - where the composition rules of the systems are defined, to a certain "semantic universe" of properties or behaviours of the systems. The properties of these functors reflect how well the information that they capture adheres to the composition rules: a lax functor $\mathrm{P}$, with structural laxator morphisms in the direction $\mathrm{P} f_{9}^{\circ} \mathrm{P} g \rightarrow \mathrm{P}\left(f_{9} \circ g\right)$, means that one can derive information on the whole system from information on its components; an oplax functor, with structural morphisms in the direction $\mathrm{P}(f \circ g) \rightarrow \mathrm{P} f \circ \mathrm{Pg}$, means that one can derive information on the components from information on the whole; while a strong functor means that the information on components and the information on the whole completely determine each other. | |
| For example, the functor sending open graphs to their reachability relation (see Section 3.1) is lax, which tells us that the reachability relation of a composition of open graphs can be strictly bigger than the composition of the reachability relations defined on its parts. This is considered undesirable from a computational viewpoint, as it means that one cannot reconstruct the reachability of a graph by separately computing the reachability of its components. | |
| On the other hand, in "Schrödinger compositionality" (covered in Section 3.2), quantum-mechanical behaviour arises from the laxity of the functor mapping each object to its set of states. This laxity implies that not all quantum states are separable, which is desirable, as it unlocks the use of entanglement as a resource unavailable in classical mechanics. | |
| In both cases, laxity represents a "failure of compositionality" which has both practical and foundational importance: the "gap" between a lax and a strong functor represents the gap between what we can compute compositionally with a "divide-and-conquer" strategy and what we cannot, or the gap between a classical and non-classical theory of processes. In this light, the question: how can we qualify (failures of) compositionality? becomes the question: how far is a lax functor from being strong? ${ }^{1}$ In this paper, we attempt to give a structured answer to the question. Our chain of reasoning is the following. | |
| Definition 1. A lax functor is strong when all the components of its laxators are isomorphisms. | |
| Thus, we can think of reducing our question to the more general one: how far is a morphism from being an isomorphism? ${ }^{2}$ Let us use the following, well-known characterisation of isomorphisms. | |
| Proposition 1. A morphism $f: X \rightarrow Y$ in a category $C$ is an isomorphism if and only if it is terminal as an object of the slice category $C / Y$. | |
| This allows us to reduce further to the question: how far is an object from being terminal? Terminality can be split into the following pair of properties. | |
| Definition 2. An object $\mathbb{1}$ in a category $C$ is | |
| - weak terminal if, for all objects $X$ of $C$, there exists a morphism $X \rightarrow \mathbb{1}$; | |
| - subterminal if, for all parallel pairs of morphisms $f, g: X \rightarrow \mathbb{1}$, we have $f=g$. | |
| Hence, to describe how far $\mathbb{1}$ is from being terminal, we can separately describe how far $\mathbb{1}$ is from being weak terminal and subterminal, respectively. | |
| Following this chain of reasoning, we focus on classifying obstructions to weak terminality and subterminality for objects in arbitrary categories. Surprisingly, it turns out that there exists a natural way of | |
| ${ }^{1}$ We will focus on lax functors in our discussion, but everything can be dualised to oplax functors. | |
| ${ }^{2}$ This approach, and the fact that it could be investigated with homotopical methods, was first suggested to us by Jules Hedges. associating certain pointed posets to a pointed category (category with a chosen object), which we call the zeroth and first homotopy poset, because in a precise sense they generalise the $\pi_{0}$ and $\pi_{1}$ of a pointed groupoid seen as a homotopy 1-type. This opens up the possibility of an invariant-based approach to the formal study of compositionality: the homotopy posets contain no information that is not already in the functors and categories, but put it in a form which may be more tractable and intelligible. | |
| In Section 1, we give the definitions of homotopy posets and state their basic properties, demonstrating in which sense they answer our question about terminal objects. In Section 2, going backwards in our chain of reasoning, we apply them to the study of obstructions to morphisms being iso. Finally, in Section 3, we sketch through a couple of simple examples how our framework can be applied to the study of failures of compositionality, seen as failures of certain (op)lax functors to be strong. | |
| \section{Homotopy posets} | |
| To begin, we focus on obstructions to weak terminality. Having fixed a category $C$, we interpret objects of a category $C$ as points, and morphisms between them as paths. From this point of view, a weak terminal object is an object that is always reachable from any generic object $x$ in $C$. | |
| Intuitively, we can fix a "weak terminal object candidate" $\mathbb{1}$ and consider any object $x$ such that there is no morphism $x \rightarrow \mathbb{1}$ as an obstruction to weak terminality. Moreover: | |
| - If $x, y$ are obstructions for $\mathbb{1}$, and there are morphisms $x \rightarrow y$ and $y \rightarrow x$, we regard them as equivalent: if there were a morphism $x \rightarrow \mathbb{1}$ there would be a morphism $y \rightarrow \mathbb{1}$, and vice versa. | |
| - If $x, y$ are obstructions for $\mathbb{1}$ and there is a morphism $x \rightarrow y$, then we regard $x$ as a "more fundamental obstruction than $y$ ". This is because, if there were a morphism $y \rightarrow \mathbb{1}$, we would automatically obtain a morphism $x \rightarrow \mathbb{1}$ by composition (one can "go from $x$ to $y$ and then to $\mathbb{1}$ "), while the opposite is not true. | |
| We will devote this section to making this intuition formal. | |
| Definition 3 (Poset reflection). Let Pos be the large 4 category of posets and order-preserving maps. There is a full and faithful functor $l: \operatorname{Pos} \hookrightarrow$ Cat, whose image consists of the categories that are | |
| - thin (each hom-set contains at most one morphism), and | |
| - skeletal (every isomorphism is an automorphism). | |
| The poset reflection $\|C\|$ of a category $C$ is its image under the left adjoint $\|-\|:$ Cat $\rightarrow$ Pos to $t$ : | |
| - the elements of $\|C\|$ are equivalence classes $\|x\|$ of objects $x$ of $C$, where $\|x\|=\|y\|$ if and only if there exist morphisms $x \rightarrow y$ and $y \rightarrow x$ in $C$, and | |
| - $\|x\| \leq\|y\|$ if and only if there exists a morphism $x \rightarrow y$ in $C$. | |
| Proposition 2. Let $C$ be a category and $\mathbb{1}$ an object in $C$. The following are equivalent: | |
| (a) $\mathbb{1}$ is a weak terminal (respectively, initial) object in $C$; | |
| (b) $\|\mathbb{1}\|$ is the greatest (respectively, least) element of $\|C\|$. | |
| ${ }^{3}$ In this paper, we will use $\mathbb{1}$ to denote "terminal object candidates", that is, objects for which we want to investigate how far they are from being terminal. For an object that we know or presume to be terminal, we will instead use the notation 1. | |
| ${ }^{4} \mathrm{We}$ will denote categories in italics and large categories in bold. Note that in our constructions, what matters is only the relative size: a construction which associates a poset to a category can be applied to a large category, producing a large poset. Definition 4 (Arrow category). Let $\vec{I}$ be the "walking arrow" category, that is, the free category on the graph | |
| $$ | |
| 0 \stackrel{a}{\longrightarrow} 1 . | |
| $$ | |
| The arrow category of a category $C$ is the functor category $C^{\vec{I}}$. Explicitly, the objects of $C^{\vec{I}}$ are morphisms of $C$, while morphisms of $C^{\vec{I}}$ are commutative squares in $C$. There are functors dom, $\operatorname{cod}: C^{\vec{I}} \rightarrow C$ which, given a morphism $\left(h_{0}, h_{1}\right)$, return $h_{0}$, respectively, $h_{1}$. | |
| Definition 5 (Category of pointed objects). Let $C$ be a category with a chosen terminal object 1 . A pointed object $(x, v)$ of $C$ is an object $x$ of $C$ together with a morphism $v: \mathbf{1} \rightarrow x$, called its basepoint. The category of pointed objects of $C-$ denoted by $C_{\bullet}-$ is the coslice category $1 / C$. | |
| Proposition 3 (Functoriality of arrow and pointed objects categories). Let $\mathrm{F}: C \rightarrow D$ be a functor. Then $\mathrm{F}$ lifts to a functor $\mathrm{F}^{\vec{I}}: C^{\vec{I}} \rightarrow D^{\vec{I}}$ using the pointwise action of $\mathrm{F}$ on $C$. | |
| If moreover $C$ and $D$ have a chosen terminal object, and if $\mathrm{F}$ preserves it, then it also lifts to a functor $\mathrm{F}_{\bullet}: C_{\bullet} \rightarrow D_{\bullet}$ sending a pointed object $(x, v)$ of $C$ to $(\mathrm{F} x, \mathrm{Fv})$, a pointed object of $D$. | |
| Definition 6 (Quotient of an object by a morphism). Let $C$ be a category with chosen pushouts and a terminal object 1 . Given a morphism $f: x \rightarrow y$, the quotient of $y$ by $f$ is the pushout | |
|  | |
| where $!: x \rightarrow \mathbf{1}$ is the unique morphism from $x$ to the terminal object. | |
| Proposition 4 (Functoriality of the quotient). If $C$ has chosen pushouts and a terminal object $\mathbf{1}$, then for each morphism $f: x \rightarrow y$ in $C$ Definition 6 determines a pointed object $\mathrm{Q}(f):=(y / / f,[x])$ of $C$. This extends to a functor $\mathrm{Q}: C^{\vec{I}} \rightarrow C_{\text {. }}$. If both $C$ and $D$ have chosen pushouts and a chosen terminal object $\mathbf{1}$, and if $\mathrm{F}$ preserves them, then $\mathrm{F}$ induces a commutative square of functors | |
|  | |
| The categories Cat and Pos have all limits and colimits, so in particular they have pushouts and a terminal object. The poset reflection functor $\|-\|$ : Cat $\rightarrow$ Pos sends the terminal category to the terminal poset, and preserves pushouts, since it is a left adjoint. The preservation can be made strict with respect to a choice on both sides. We are in the conditions of Proposition 4: there is a commutative square | |
|  | |
| We are now ready to define the object of interest of this section. | |
| Definition 7 (Zeroth homotopy poset). Let $C$ be a category and $x$ an object in $C$. The zeroth homotopy poset of $C$ over $x$ is the pointed poset | |
| $$ | |
| \left(\pi_{0}(C / x),[x]\right) | |
| $$ | |
| obtained by applying the functor $\mathbf{C a t}^{\vec{I}} \rightarrow$ Pos. from Equation 1 to the slice projection functor | |
| $$ | |
| \text { dom : } C / x \rightarrow C \text {. } | |
| $$ | |
| Let us unravel the definition of $\pi_{0}(C / x)$ to a more explicit form. We start from the projection functor dom: $C / x \rightarrow C$. To this we may either apply $\mathrm{Q}$ or $\|-\| \vec{I}$. Since quotients in Pos are simpler to compute than quotients in Cat, we apply poset reflection first, which gives us an order-preserving map | |
| $$ | |
| \|\operatorname{dom}\|:\|C / x\| \rightarrow\|C\| | |
| $$ | |
| Unravelling the explicit definition of poset reflection for $C / x$, we see that: | |
| - an element of $\|C / x\|$ is an equivalence class $\|f: y \rightarrow x\|$ of morphisms of $C$ with codomain $x$, where $\|f\|=\|g\|$ if and only if $f$ factors through $g$ and $g$ factors through $f$, and | |
| - $\|f\| \leq\|g\|$ if and only if $f$ factors through $g$. | |
| The map $\|\operatorname{dom}\|$ sends $\|f\|$ to $\|\operatorname{dom} f\|$. The image of $\|\operatorname{dom}\|$ is then the set | |
| $$ | |
| \{\|y\| \mid \text { there exists a morphism } f: y \rightarrow x \text { in } C\} | |
| $$ | |
| which is, equivalently, the lower set of $\|x\|$ in $\|C\|$. | |
| Applying Q: $\operatorname{Pos}^{\vec{I}} \rightarrow$ Pos. to this map produces the quotient of $\|C\|$ with all elements of this set identified, pointed with the element resulting from their identification, which we denote by $[x]$. Hence, an element of $\pi_{0}(C / x)$ is either $[x]$, or it is $\|y\|$ for some object $y$ such that there exists no morphism $f: y \rightarrow x$ in $C$. The order relation is defined as follows, by case distinction: | |
| - $[x] \leq[x]$ trivially; | |
| - $[x] \leq\|y\|$ if and only if there exists a span $(x \stackrel{f}{\leftarrow} z \stackrel{g}{\rightarrow} y)$ in $C$; | |
| - it is never the case that $\|y\| \leq[x]$; | |
| - $\|y\| \leq\|z\|$ if and only if there exists a morphism $f: y \rightarrow z$ in $C$. | |
| Notice that $[x]$ is always minimal in $\pi_{0}(C / x)$. | |
| The partial order on $\pi_{0}(C / x)$ ranks obstructions to weak terminality by "size": if we removed an obstruction $\|y\|$, adding a morphism $y \rightarrow x$, we would also have to remove all the "smaller" obstructions $\|z\| \leq\|y\|$. The minimal element $[x]$ represents the "non-obstructions": | |
| Proposition 5. Let $C$ be a category and $x$ an object in $C$. The following are equivalent: | |
| (a) $\pi_{0}(C / x)=\{[x]\}$ | |
| (b) $x$ is a weak terminal object in $C$. | |
| The notation and terminology is suggestive of the $\pi_{0}$ of a pointed topological space or groupoid, that is, its set of connected components, pointed with the connected component of the basepoint. The following result shows that, indeed, the notions coincide when $C$ happens to be a groupoid. Proposition $6\left(\pi_{0}(G / x)\right.$ for a groupoid). Let $G$ be a groupoid and $x$ an object in $G$. Then | |
| 1. $\pi_{0}(G / x)$ is a "set", that is, a discrete poset, and | |
| 2. as a pointed set, it is isomorphic to the set $\pi_{0}(G)$ of connected components of $G$, pointed with the connected component of $x$. | |
| Now, we investigate obstructions to subterminality. Our main strategy will be to recast subterminality in a way that allows us to leverage Definition 7 . We know that an object $\mathbb{1}$ fails to be subterminal when, for an object $x$, the arrow $x \rightarrow \mathbb{1}$ is not unique. As such, we will describe obstructions to subterminality as pairs of parallel, unequal arrows. | |
| Definition 8 (Category of parallel arrows over an object). Let $C$ be a category and $x$ an object in $C$. The category of parallel arrows in $C$ over $x$ is the category $\operatorname{Par}(C / x)$ where: | |
| - Objects are pairs of morphisms $\left(f_{0}, f_{1}: y \rightarrow x\right)$ with codomain $x$. | |
| - A morphism from $\left(f_{0}, f_{1}: y \rightarrow x\right)$ to $\left(g_{0}, g_{1}: z \rightarrow x\right)$ is a morphism $h: y \rightarrow z$ such that $f_{0}=h_{9} g_{0}$ and $f_{1}=h_{9}^{\circ} g_{1}$. | |
| This comes with a projection functor $\operatorname{dom}: \operatorname{Par}(C / x) \rightarrow C$ sending a parallel pair to its domain. | |
| Proposition 7. Let $C$ be a category and $\mathbb{1}$ an object in $C$. The following are equivalent: | |
| (a) $\mathbb{1}$ is subterminal in $C$; | |
| (b) $\left(\mathrm{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)$ is a terminal object in $\operatorname{Par}(C / \mathbb{1})$; | |
| (c) $\left(\operatorname{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)$ is a weak terminal object in $\operatorname{Par}(C / \mathbb{1})$. | |
| Proposition 7 allows us to reduce the study of obstructions to subterminality of an object $\mathbb{1}$ in $C$ to the study of obstructions to weak terminality of $\left(\mathrm{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)$ in $\operatorname{Par}(C / \mathbb{1})$. | |
| Definition 9 (First homotopy poset). Let $C$ be a category and $x$ an object in $C$. The first homotopy poset of $C$ over $x$ is the pointed poset | |
| $$ | |
| \left(\pi_{1}(C / x),[x]\right):=\left(\pi_{0}\left(\operatorname{Par}(C / x) /\left(\operatorname{id}_{x}, \operatorname{id}_{x}\right)\right),\left[\left(\operatorname{id}_{x}, \mathrm{id}_{x}\right)\right]\right) . | |
| $$ | |
| Putting together the description of the 0th homotopy poset, the definition of $\operatorname{Par}(C / x)$ in Definition 8 , and Proposition 7, we see that an element of $\pi_{1}(C / x)$ is either $[x]$, or $\|(f, g)\|$ for some parallel pair of morphisms $f, g: y \rightarrow x$ in $C$ with $f \neq g$. The order relation is defined as follows: | |
| - $[x] \leq[x]$ trivially; | |
| - $[x] \leq\|(f, g: y \rightarrow x)\|$ if and only if there exists a morphism $h: z \rightarrow y$ in $C$ equalising $(f, g)$, that is, satisfying $h \risingdotseq f=h \circ g$; | |
| - it is never the case that $\|(f, g)\| \leq[x]$; | |
| - $\|(f, g: y \rightarrow x)\| \leq\left\|\left(f^{\prime}, g^{\prime}: y^{\prime} \rightarrow x\right)\right\|$ if and only if there exists a morphism $h: y \rightarrow y^{\prime}$ such that $f=h \circ f^{\prime}$ and $g=h \circ g^{\prime}$ in $C$. | |
| Proposition 8. Let $C$ be a category and $x$ an object in $C$. The following are equivalent: | |
| (a) $\pi_{1}(C / x)=\{[x]\}$ | |
| (b) $x$ is subterminal in $C$. | |
| Corollary 1. Let $C$ be a category and $x$ an object in $C$. The following are equivalent: (a) $\pi_{0}(C / x)=\{[x]\}$ and $\pi_{1}(C / x)=\{[x]\}$, | |
| (b) $x$ is a terminal object in $C$. | |
| Remark 1. Recall that the (underlying set of the) fundamental group of a pointed topological space $(X, x)$ is defined by | |
| $$ | |
| \pi_{1}(X, x):=\pi_{0}\left(\Omega(X, x), c_{x}\right) | |
| $$ | |
| where $\Omega(X, x)$ is the space of loops in $X$ based at $x$, and $c_{x}$ is the constant path at $x$. For a pointed groupoid, which may be seen as the fundamental groupoid of a pointed space, this reduces to the set of automorphisms of the object $x$, pointed with the identity automorphism. | |
| The definition of $\pi_{1}(C / x)$ is made in analogy with this, letting the category of parallel arrows over $x$ replace the space of loops based at $x$, and a pair of identity morphisms replace the constant path. The following result proves that, just like the zeroth homotopy poset, the first homotopy poset is a generalisation of its groupoidal analogue. | |
| Proposition $9\left(\pi_{1}(G / x)\right.$ for a groupoid). Let $G$ be a groupoid and $x$ an object in $G$. Then: | |
| 1. $\pi_{1}(G / x)$ is a "set", that is, a discrete poset, and | |
| 2. as a pointed set, it is isomorphic to the underlying pointed set of the group $\pi_{1}(G, x)=\operatorname{Hom}_{G}(x, x)$. | |
| Remark 2. We mention here that the field of directed algebraic topology $[15,10]$ has also produced "non-invertible" versions of $\pi_{1}$, namely, the fundamental category and monoids, that apply to directed spaces. If applied to a category, these pick out "tautologically" the category itself and its monoids of endomorphisms. To our knowledge, there is no strong relation to our line of research. | |
| To conclude this section, we show in what way the homotopy posets are functorial in the pair $(C, x)$ of a category and an object. | |
| Proposition 10 (Functoriality of the homotopy posets). Let $C$ be a category, $i \in\{0,1\}$. Then: | |
| 1. the assignment $x \mapsto \pi_{i}(C / x)$ extends to a functor $\pi_{i}(C /-): C \rightarrow$ Pos.; | |
| 2. a functor $\mathrm{F}: C \rightarrow D$ induces a natural transformation $\pi_{i}(\mathrm{~F}): \pi_{i}(C /-) \Rightarrow \pi_{i}(D / \mathrm{F}-)$. | |
| Given another functor $\mathrm{G}: D \rightarrow E$, this assignment satisfies | |
| $$ | |
| \pi_{i}(\mathrm{~F} \% \mathrm{G})=\pi_{i}(\mathrm{~F}) ; \pi_{i}(\mathrm{G}), \quad \pi_{i}\left(\mathrm{id}_{C}\right)=\mathrm{id}_{\pi_{i}(C /-)} . | |
| $$ | |
| A concise way of packaging this information is to say that $\pi_{i}$ defines a functor from Cat to the lax slice Cat Pos., where $\mathscr{C}$ at is the "huge" category of possibly large categories. The objects of the lax slice are pairs of a possibly large category $\mathbf{C}$ and a functor $\mathbf{C} \rightarrow$ Pos. $_{\bullet}$, and the morphisms are triangles of functors commuting up to a natural transformation. Indeed, given $\mathrm{F}: C \rightarrow D$, we have a triangle | |
|  | |
| commuting up to the natural transformation $\pi_{i}(\mathrm{~F})$. | |
| Remark 3 (Dual invariants). As usual, all the constructions can be dualised to $C^{\mathrm{op}}$. This will replace the slice over an object and its domain opfibration with the slice under an object and its codomain fibration, producing invariants classifying obstructions to initiality of the object. | |
| \section{Obstructions to a morphism being iso} | |
| As remarked in the Introduction, one of our main motivations for introducing homotopy posets was measuring how far a generic morphism is from being iso. Just as we could separate obstructions to terminality into obstructions to weak terminality and subterminality, we can separate obstructions to a morphism being iso into obstructions to a morphism being split epi and mono, respectively. | |
| Proposition 11. Let $f: X \rightarrow Y$ be a morphism in a category $C$. Then: | |
| - $f$ is split epi in $C$ if and only if $f$ is weak terminal in $C / Y$, | |
| - $f$ is mono in $C$ if and only if $f$ is subterminal in $C / Y$. | |
| Corollary 2. Let $f: X \rightarrow Y$ be a morphism in a category $C$. Then: | |
| - $f$ is split epi if and only if $\pi_{0}((C / Y) / f)$ is trivial; | |
| - $f$ is mono if and only if $\pi_{1}((C / Y) / f)$ is trivial, and: | |
| - $f$ is iso if and only if both $\pi_{0}((C / Y) / f)$ and $\pi_{1}((C / Y) / f)$ are trivial. | |
| Furthermore, when the homotopy posets associated to a morphism $f$ are not trivial, they give us precise information about why $f$ fails to be split epi and mono. | |
| To make this more concrete, let us spell out precisely how to compute the invariants associated to a function between sets, where split epi (assuming choice) means surjective and mono means injective. This amounts to calculating $\pi_{0}((\mathbf{S e t} / Y) / f)$ and $\pi_{1}((\mathbf{S e t} / Y) / f)$ for some function $f: X \rightarrow Y$. | |
| Proposition 12. Let $f: X \rightarrow Y$ be a function between sets. $\|$ Set $/ Y \|$ is isomorphic, as a poset, to the power set $\mathscr{P} Y$, via the assignment $(S \subseteq Y) \mapsto\left\|l_{S}\right\|$, where $l_{S}$ is the injective function including $S$ into $Y$. Through this bijection, $\|f\|$ corresponds to the image $f(X)$ of $f$. | |
| Using this correspondence and quotienting by the lower set of $f(X)$, which contains in particular $\varnothing$, we may identify $\pi_{0}((\operatorname{Set} / Y) / f)$ with the subposet of $\mathscr{P} Y$ whose elements are either $\varnothing$ or subsets of $Y$ that contain at least one element $y \notin f(X)$. The "minimal obstructions", that is, the minimal elements in the complement of the basepoint, are the singletons $\{y\}$ with $y \in Y \backslash f(X)$. This poset is trivial if and only if $f(X)=Y$, that is, iff $f$ is surjective. | |
| Example 1. Let $f:\{0,1\} \rightarrow\{0,1,2,3\}$ be the function mapping $0 \mapsto 0$ and $1 \mapsto 1$. The homotopy poset $\pi_{0}(($ Set $/\{0,1,2,3\}) / f)$ has the following structure: | |
|  | |
| The minimal obstructions $\{2\}$ and $\{3\}$ are in bijection with the elements not in the image of $f$. Proposition 13. Let $X \times_{f} X$ be the pullback of $f$ along itself - that is, the set $\left\{\left(x_{0}, x_{1}\right) \mid f\left(x_{0}\right)=f\left(x_{1}\right)\right\}$ - and let $p_{f}: X \times_{f} X \rightarrow Y$ be the function $\left(x_{0}, x_{1}\right) \mapsto f\left(x_{0}\right)=f\left(x_{1}\right)$. Then: | |
| 1. $\|\operatorname{Par}((\mathbf{S e t} / Y) / f)\|$ is isomorphic to $\mathscr{P}\left(X \times_{f} X\right)$ via the assignment $\left(S \subseteq X \times_{f} X\right) \mapsto\left\|\left(\left.p_{0}\right|_{S},\left.p_{1}\right|_{S}\right)\right\|$, where $\left.p_{i}\right|_{S}$ are the projections $X \times_{f} X \rightarrow Y$, restricted to $S$, seen as morphisms $\left.p_{f}\right|_{S} \rightarrow f$ in $\|\operatorname{Par}((\mathbf{S e t} / Y) / f)\| ;$ | |
| 2. through this bijection, $\left\|\left(\mathrm{id}_{f}, \mathrm{id}_{f}\right)\right\|$ is identified with the diagonal $\Delta X$. | |
| Using this correspondence, we may identify $\pi_{1}($ Set $/ X)$ with the subposet of $\mathscr{P}\left(X \times_{f} X\right)$ whose elements are either $\varnothing$, or contain at least one pair $\left(x_{0}, x_{1}\right)$ such that $x_{0} \neq x_{1}$. This poset is trivial if and only if $f$ is injective. Notice that the minimal obstructions to injectiveness of $f$ are in bijection with pairs $\left(x_{0}, x_{1}\right)$ where $x_{0} \neq x_{1}$ but $f\left(x_{0}\right)=f\left(x_{1}\right)$. | |
| Example 2. Let $f:\{0,1\} \rightarrow\{*\}$ be the function mapping $0 \mapsto *, 1 \mapsto *$. Then $\{0,1\} \times_{f}\{0,1\}$ is the set $\{(0,0),(0,1),(1,0),(1,1)\}$, and $\pi_{1}(($ Set $/\{*\}) / f)$ has the following structure: | |
|  | |
| Notice that, via the isomorphism Set $\simeq \operatorname{Set} /\{*\}$, this is isomorphic to $\pi_{1}(\operatorname{Set} /\{0,1\})$. | |
| To conclude, suppose that two morphisms are both components of the same natural transformation. Is there a relation between the associated invariants? The following result answers this question in the affirmative. | |
| Proposition 14 (Covariance over the domain of a natural transformation). Let $\mathrm{F}, \mathrm{G}: C \rightarrow D$ be two functors and let $\alpha: \mathrm{F} \Rightarrow \mathrm{G}$ be a natural transformation. For all $i \in\{0,1\}$, the assignment | |
| $$ | |
| x \mapsto \pi_{i}\left((D / G x) / \alpha_{x}\right) | |
| $$ | |
| extends to a functor $C \rightarrow$ Pos. | |
| Notice that this is not simply a consequence of Proposition 10, that is, it does not arise from the general functoriality result by pre-composition with another functor. ${ }^{5}$ It implies that we can naturally map obstructions for $\alpha_{x}$ to obstructions for $\alpha_{y}$ along a morphism $f: x \rightarrow y$ in $C$; we can think of morphisms in $C$ as inducing a "flow" of obstructions to the components of $\alpha$, under which a non-trivial obstruction may be trivialised, but it can never be the case that a non-obstruction is "un-trivialised". | |
| ${ }^{5}$ There is a unifying perspective on the two functoriality results, involving the theory of fibrations and cofibrations of categories; this will be discussed in an extended technical paper. | |
| \section{Qualifying compositionality} | |
| Now let $\mathrm{P}: C \rightarrow D$ be a lax functor of bicategories. This means that, for all triples of objects $X, Y, Z$ in $C$, we have two functors | |
| $$ | |
| (\mathrm{P}-) \stackrel{9}{ }(\mathrm{P}-), \mathrm{P}(-\stackrel{\circ}{-}): \operatorname{Hom}_{C}(X, Y) \times \operatorname{Hom}_{C}(Y, Z) \rightarrow \operatorname{Hom}_{D}(\mathrm{P} X, \mathrm{PZ}) | |
| $$ | |
| connected by a natural transformation, the laxator $\varphi:(\mathrm{P}-) \circ(\mathrm{P}-) \Rightarrow \mathrm{P}(-\circ-) \cdot{ }^{6}$ As a special case, when $C$ and $D$ are monoidal categories seen as one-object bicategories, $\mathrm{P}$ is a lax monoidal functor, and the laxator is a natural transformation $(\mathrm{P}-) \otimes(\mathrm{P}-) \Rightarrow \mathrm{P}(-\otimes-)$. | |
| By Proposition 14, we obtain functors $\operatorname{Hom}_{C}(X, Y) \times \operatorname{Hom}_{C}(Y, Z) \rightarrow$ Pos. sending a pair of morphisms $(f: X \rightarrow Y, g: Y \rightarrow Z)$ to the homotopy posets | |
| $$ | |
| \pi_{i}\left(\left(\operatorname{Hom}_{D}(\mathrm{P} X, \mathrm{PZ}) / \mathrm{P}(f \circ g)\right) / \varphi_{f, g}\right) | |
| $$ | |
| associated to the component $\varphi_{f, g}$ of the laxator. | |
| In the scenario sketched in the Introduction, the failure of $\varphi_{f, g}$ to be iso is a failure of the "semantic" functor P to be "fully compositional" with respect to the composition $f \circ g$. Thus the elements of these homotopy posets may be seen as local obstructions to compositionality of $\mathrm{P}$. Most interestingly, these obstructions are covariant with respect to the 2-morphisms of $C$; thus we can think of "modifying $f$ and $g$ " by acting on them with a 2-morphism, and see how that affects the obstructions. | |
| \subsection{Open Graphs} | |
| We apply our framework to a couple of tangible examples. Open graphs, defined in [11], can be thought of as graphs with interfaces. Formally, open graphs are (isomorphism classes of) decorated cospans with decorations in the category Graph of graphs and homomorphisms. Intuitively, they are depicted as in the examples below, with input vertices on the left and output vertices on the right: | |
|  | |
| Indeed, there is a bicategory OpenGraph that has sets as objects, open graphs as morphisms, and interface-preserving graph homomorphisms as 2-morphisms. For instance, the first and second open graphs above correspond to morphisms $G:\{1\} \rightarrow\{1,2,3\}$ and $H:\{1,2,3\} \rightarrow\{1\}$. These morphisms can be composed, resulting in the morphism $G_{9}^{\circ} H:\{1\} \rightarrow\{1\}$ corresponding to the third open graph in the picture above. | |
| Every graph can be mapped to its reachability relation ${ }^{7}$ : this is a relation on the vertexes of the graph, where two vertexes are considered related iff there is a path between them. Reachability can be recast as a lax functor OpenGraph $\rightarrow$ Rel to the bicategory of sets, relations, and inclusions of relations, which maps an open graph $G: X \rightarrow Y$ to the relation $\mathrm{R} G: X \rightarrow Y$ defined by | |
| $\mathrm{R} G(x, y)$ if and only if there is a path between the input vertex $x$ and the output vertex $y$. | |
| ${ }^{6}$ Technically, the laxators are a family of natural transformations indexed by $X, Y, Z$, but we will leave the indexing implicit. | |
| ${ }^{7} \mathrm{Cfr}$. [17], for the similar example of open causal models and causal influence. Because Rel is locally posetal, to define R on 2-morphisms it suffices to verify that, if $f: G \rightarrow G^{\prime}$ is a graph homomorphism, then $\mathrm{R} G \subseteq \mathrm{R} G^{\prime}$. The laxators are also uniquely defined. | |
| We can see that this functor is not strong. In the example above we have that $\mathrm{R} G \subseteq\{1\} \times\{1,2,3\}$ only contains the pair $(1,1)$, since there are no paths from 1 to 2 and from 1 to 3 in $G$. Similarly, $\mathrm{R} H \subseteq\{1,2,3\} \times\{1\}$ only contains the pair $(3,1)$. It follows that $\mathrm{R} G_{9}^{\circ} \mathrm{R} H:\{1\} \rightarrow\{1\}$ is the empty relation, but $\mathrm{R}(G \circ H):\{1\} \rightarrow\{1\}$ is total, so $\mathrm{R} G \circ \mathrm{R} H \subsetneq \mathrm{R}(G \circ H)$. | |
| The result is that, if we want to compute the reachability relation of $G_{9}^{\circ} H$ by looking at the reachability relations of $G$ and $H$ separately, we are going to miss something. This "compositionality gap" is tracked by the $\pi_{0}$ associated to the laxator components $\varphi_{G, H}: \mathrm{R} G \circ \mathrm{R} H \subseteq \mathrm{R}\left(G_{9}^{\circ} H\right)$ (because these are all injective, the $\pi_{1}$ will always be trivial). | |
| In our example, $\pi_{0}\left(\left(\operatorname{Hom} \operatorname{Rel}(\{1\},\{1\}) / \mathrm{R}\left(G_{9}^{\circ} H\right)\right) / \varphi_{G, H}\right)$ is isomorphic to the poset $(\varnothing<\{(1,1)\})$ pointed with $\varnothing$, so there is exactly one non-trivial obstruction. Using covariance, we can think of "removing the obstruction" by modifying one or both of the parts $G$ or $H$ with a 2-morphism, that is, with a graph homomorphism. For example, we can act on $G$ with the homomorphism which identifies the output vertices 1 and 3. The resulting graph $G^{\prime}$ has $\mathrm{R} G^{\prime}=\{(1,1),(1,3)\}$, so $\mathrm{R} G^{\prime}{ }_{9} \mathrm{R} H=\mathrm{R}\left(G^{\prime}{ }_{9} H\right)=\{(1,1)\}$; correspondingly, we obtain a map of pointed posets from the $\pi_{0}$ associated to $\varphi_{G, H}$ to the $\pi_{0}$ associated to $\varphi_{G^{\prime}, H}$, which "trivialises all obstructions". | |
| \subsection{Schrödinger Compositionality} | |
| The name Schrödinger compositionality was introduced in [6] to refer to the form of compositionality that exists in quantum mechanics, where non-separable states are present, to disambiguate it from others. ${ }^{8}$ In the following, we will focus on the special case of a state that can be "more than its parts". This is arguably what makes composition interesting in quantum mechanics: it makes entanglement possible, which Schrödinger described as "the characteristic trait of quantum mechanics" [21]. In contrast with the example of open graphs, where the "compositionality gap" represents an obstacle to a computation strategy, here it can be seen as a positive feature. Our approach can be used in both contexts; we will focus on the case study of non-separable states, recasting it as the failure of a lax functor to be strong. | |
| In the context of monoidal categories, a state is a morphism $I \rightarrow A$, where $I$ is the monoidal unit. We say that a state $\psi: I \rightarrow A \otimes B$ is separable if there exist states $\psi_{A}: I \rightarrow A$ and $\psi_{B}: I \rightarrow B$ such that $\psi=\psi_{A} \otimes \psi_{B}$ | |
| Definition 10. Let $(C, \otimes, I)$ be a monoidal category. The state functor of $C$ is the representable functor $\operatorname{Hom}_{C}(I,-): C \rightarrow$ Set. | |
| Proposition 15 (Laxity of the state functor). The state functor lifts to a lax monoidal functor from $(C, \otimes, I)$ to $(\mathbf{S e t}, \times,\{*\})$, with laxator components | |
| $$ | |
| \begin{aligned} | |
| \varphi_{A, B}: \operatorname{Hom}_{C}(I, A) \times \operatorname{Hom}_{C}(I, B) & \rightarrow \operatorname{Hom}_{C}(I, A \otimes B) \\ | |
| \left(\psi_{A}, \psi_{B}\right) & \mapsto \psi_{A} \otimes \psi_{B} . | |
| \end{aligned} | |
| $$ | |
| Recall that a monoidal category is semicartesian if its monoidal unit is terminal. The following result is a consequence of the general fact that a functor from a semicartesian to a cartesian monoidal category has a canonical oplax monoidal structure. | |
| ${ }^{8}$ For the purposes of this work, we are leaving out of the present analysis the aspects of Schrödinger compositionality regarding the "ontological interpretation", originally presented in [6]. Proposition 16 (Oplaxity of the state functor). Let $(C, \otimes, \mathbf{1})$ be a semicartesian category. Then the state functor lifts to an oplax monoidal functor from $(C, \otimes, \mathbf{1})$ to $($ Set, $\times,\{*\})$. | |
| Clearly, there are cases where the state functor is not just lax or oplax, but strong. The following result captures the well-known fact that in a cartesian monoidal category every state is separable. | |
| Proposition 17 (Strongness of the state functor). If $(C, \times, \mathbf{1})$ is cartesian, then the state functor is strong monoidal. | |
| Having turned Schrödinger compositionality into a question about (op)laxity of a functor, we can put our framework to good work. By Proposition 14, we have functors $C \times C \rightarrow$ Pos. sending pairs of objects $(A, B)$ of $C$ to the homotopy posets | |
| $$ | |
| \pi_{i}\left(\left(\mathbf{S e t} / \operatorname{Hom}_{C}(I, A \otimes B)\right) / \varphi_{A, B}\right), \quad i \in\{0,1\} . | |
| $$ | |
| Using the description of homotopy posets for slices of Set from Section 2, we see that | |
| - minimal obstructions in $\pi_{0}$ are in bijection with non-separable states of $A \otimes B$, | |
| - minimal obstructions in $\pi_{1}$ are in bijection with pairs of pairs of states $\left(\left(\psi_{A}, \psi_{B}\right),\left(\chi_{A}, \chi_{B}\right)\right)$ such that $\psi_{A} \otimes \psi_{B}=\chi_{A} \otimes \chi_{B}$. | |
| For example, in $\left(\operatorname{Vect}_{\mathbb{C}}, \otimes, \mathbb{C}\right)$, the monoidal category of complex vector spaces with their tensor product, whenever $A$ and $B$ are at least 2-dimensional, we have instances of both: | |
| - the state $1 \mapsto\left(\begin{array}{l}1 \\ 0\end{array}\right) \otimes\left(\begin{array}{l}1 \\ 0\end{array}\right)+\left(\begin{array}{l}0 \\ 1\end{array}\right) \otimes\left(\begin{array}{l}0 \\ 1\end{array}\right)$ of $\mathbb{C}^{2} \otimes \mathbb{C}^{2}$ is non-separable, | |
| - given any pair of states $\left(\psi_{A}, \psi_{B}\right)$ and any non-zero $\lambda \in \mathbb{C}$, the pair $\left(\chi_{A}, \chi_{B}\right):=\left(\lambda \psi_{A}, \lambda^{-1} \psi_{B}\right)$ satisfies $\psi_{A} \otimes \psi_{B}=\chi_{A} \otimes \chi_{B}$. | |
| We can derive a few simple, immediate consequences from the covariance of (2) in the pair $(A, B)$. | |
| 1. Given morphisms $f: A \rightarrow A^{\prime}, g: B \rightarrow B^{\prime}$, the induced maps of posets preserve the basepoint, that is, map "non-obstructions" to "non-obstructions". In this case, this implies that it is not possible to entangle a separable state by local actions, that is, by applying morphisms on $A$ and $B$ separately. | |
| 2. On the other hand, it is, in principle, possible for the induced maps to send non-trivial obstructions to the basepoint. For example, in complex vector spaces, acting on $A$ or $B$ with a rank-1 linear map always has a separating effect. | |
| \section{Conclusion} | |
| We have introduced our new invariants of categories and stated their fundamental properties, before sketching, through a couple of simple examples, how they may be used to obtain a more fine-grained analysis of "failures of compositionality" than a simple yes-or-no judgement. In an extended technical paper, we will study their formal aspects more in depth, including criteria for the existence of joins and meets, induced monoidal structures, and finer aspects of functoriality. | |
| Most importantly, we hope to have opened a new avenue in "formal compositionality theory". The greatest challenge will be to graduate from proof-of-concept examples to ones that reveal more interesting structure, perhaps in non-Set-like categories where a split epi or mono is not simply a surjective or injective map. We have been looking at case studies of this sort, which nevertheless have manageable combinatorics permitting an exhaustive study of their homotopy posets, and we hope to discuss them in future work. | |
| \section{References} | |
| [1] (2012): The Oxford Handbook of Compositionality. Oxford Handbooks in Linguistics, Oxford University Press, Oxford; New York, NY. | |
| [2] Samson Abramsky \& Bob Coecke (2009): Categorical quantum mechanics. Handbook of quantum logic and quantum structures 2, pp. 261-325. | |
| [3] Jiří Adámek, Horst Herrlich \& George Strecker (1990): Abstract and concrete categories. WileyInterscience. | |
| [4] Jiří Adámek \& Jiří Rosicky (1994): Locally presentable and accessible categories. 189, Cambridge University Press. | |
| [5] John C Baez, Fabrizio Genovese, Jade Master \& Michael Shulman (2021): Categories of nets. In: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE, pp. 1-13. | |
| [6] Bob Coecke (2021): Compositionality as we see it, everywhere around us. arXiv preprint arXiv:2110.05327. | |
| [7] Bob Coecke (2021): The mathematics of text structure. Joachim Lambek: The Interplay of Mathematics, Logic, and Linguistics, pp. 181-217. | |
| [8] Bob Coecke \& Konstantinos Meichanetzidis (2020): Meaning updating of density matrices. arXiv preprint arXiv:2001.00862. Available at http://arxiv.org/abs/2001.00862. | |
| [9] Robin Cooper (2013): Quantification and syntactic theory. 21, Springer Science \& Business Media. | |
| [10] Lisbeth Fajstrup, Eric Goubault, Emmanuel Haucourt, Samuel Mimram \& Martin Raussen (2016): Directed algebraic topology and concurrency. 138, Springer. | |
| [11] Brendan Fong: Decorated Cospans. arXiv preprint arXiv:1502.0087230(33), pp. 1096-1120. | |
| [12] Brendan Fong \& David I. Spivak (2019): An invitation to applied category theory: seven sketches in compositionality. Cambridge University Press, Cambridge; New York, NY. | |
| [13] Fabrizio Romano Genovese (2018): Modularity vs compositionality: a history of misunderstandings. Online article, https://blog.statebox.org/modularity-vs-compositionality-a-history-ofmisunderstandings-be0150033568. Accessed 17 July 2023. | |
| [14] Neil Ghani, Jules Hedges, Viktor Winschel \& Philipp Zahn (2018): Compositional game theory. In: Proceedings of the 33rd annual ACM/IEEE symposium on logic in computer science, pp. 472-481. | |
| [15] Marco Grandis (2009): Directed algebraic topology: models of non-reversible worlds. 13, Cambridge University Press. | |
| [16] André Joyal (2008): The theory of quasi-categories and its applications. Quaderns 45(2), pp. 151-496. | |
| [17] Robin Lorenz \& Sean Tull (2023): Causal models in string diagrams. arXiv preprint arXiv:2304.07638. | |
| [18] Francois Meyer \& Martha Lewis (2020): Modelling lexical ambiguity with density matrices. arXiv preprint arXiv:2010.05670. | |
| [19] Richard Montague (1974): Universal grammar. Theoria, 36. Reprinted in RH Thomason (ed.), Formal philosophy (pp. 222-246). | |
| [20] Robin Piedeleu, Dimitri Kartsaklis, Bob Coecke \& Mehrnoosh Sadrzadeh (2015): Open system categorical quantum semantics in natural language processing. arXiv preprint arXiv:1502.00831. | |
| [21] Erwin Schrödinger (1935): Discussion of Probability Relations between Separated Systems. Mathematical Proceedings of the Cambridge Philosophical Society 31(4), p. 555-563. | |
| [22] Dag Westerstahl (2007): Compositionality and ambiguity. | |
| \section{Proofs} | |
| \section{Introduction} | |
| Definition 11 (Slice category). Let $C$ be a category and $X$ an object in $C$. The slice of $C$ over $X$ is the category $C / X$ whose | |
| - objects are morphisms $(f: Y \rightarrow X)$ in $C$ with codomain $X$, and | |
| - a morphism from $(f: Y \rightarrow X)$ to $(g: Z \rightarrow X)$ is a factorisation of $f$ through $g$, that is, a morphism $h: Y \rightarrow Z$ such that $f=h_{9}^{\circ} g$. | |
| This comes with a projection functor $\operatorname{dom}: C / X \rightarrow C$. | |
| Proposition 1. A morphism $f: X \rightarrow Y$ in a category $C$ is iso iff it is terminal in the slice category $C / Y$. | |
| Proof. Follows from Proposition 11, remembering that a morphism is split epi and mono iff it is iso. | |
| \section{Homotopy posets} | |
| Definition 3 (Poset reflection). Let Pos be the large category of posets and order-preserving maps. There is a full and faithful functor $l$ : Pos $\hookrightarrow$ Cat, whose image consists of the categories that are | |
| - thin (each hom-set contains at most one morphism), and | |
| - skeletal (every isomorphism is an automorphism). | |
| The poset reflection $\|C\|$ of a category $C$ is its image under the left adjoint $\|-\|:$ Cat $\rightarrow$ Pos to $l$ : | |
| - the elements of $\|C\|$ are equivalence classes $\|x\|$ of objects $x$ of $C$, where $\|x\|=\|y\|$ if and only if there exist morphisms $x \rightarrow y$ and $y \rightarrow x$ in $C$, and | |
| - $\|x\| \leq\|y\|$ if and only if there exists a morphism $x \rightarrow y$ in $C$. | |
| Proof. Let $C$ be a category and $P$ a poset; we will identify $P$ with the thin, skeletal category $\imath P$. Given a functor $\mathrm{F}: C \rightarrow \imath P$, we define an order-preserving map $f:\|C\| \rightarrow P$ by letting $f(\|x\|):=\mathrm{F} x$ for all objects $x$ of $C$. This is well-defined as a function, since $\|x\|=\|y\|$ implies that there are morphisms $x \rightarrow y$ and $y \rightarrow x$, hence $\mathrm{F} x \leq \mathrm{F} y$ and $\mathrm{F} y \leq \mathrm{F} x$, so $\mathrm{F} x=\mathrm{F} y$ by antisymmetry of the order on $P$. It is also order-preserving: if $\|x\| \leq\|y\|$ then there exists a morphism $x \rightarrow y$, so $\mathrm{F} x \leq \mathrm{F} y$. | |
| Conversely, given an order-preserving map $f:\|C\| \rightarrow P$, we define a functor $\mathrm{F}: C \rightarrow \imath P$ by letting $\mathrm{F} x:=f(\|x\|)$. The two assignments are clearly inverse to each other, and naturality in $C$ and $P$ is a straightforward check. This proves that $\|-\|:$ Cat $\rightarrow$ Pos is left adjoint to $l:$ Pos $\rightarrow$ Cat. | |
| Proposition 2. Let $C$ be a category and $\mathbb{1}$ an object in $C$. The following are equivalent: | |
| (a) $\mathbb{1}$ is a weak terminal (respectively, initial) object in $C$; | |
| (b) $\|\mathbb{1}\|$ is the greatest (respectively, least) element of $\|C\|$. | |
| Proof. If $x$ is any object of $\|C\|$, then $x$ is of the form $\|\tilde{x}\|$ for some $\tilde{x}$ in $C$. If $\mathbb{1}$ is weak terminal, then there is at least one morphism $\tilde{x} \rightarrow \mathbb{1}$ in $C$, and so $x=\|\tilde{x}\| \leq\|\mathbb{1}\|$ in $\|C\|$. | |
| The other way around, taking any $x$ in $C,\|\mathbb{1}\|$ being the greatest element of $\|C\|$ gives us $\|x\| \leq\|\mathbb{1}\|$ in $\|C\|$; hence there is at least one morphism $x \rightarrow \mathbb{1}$ in $C$, proving that $\mathbb{1}$ is weak terminal. Definition 4 (Arrow category). Let $\vec{I}$ be the "walking arrow" category, that is, the free category on the graph | |
| $$ | |
| 0 \stackrel{a \longrightarrow}{\longrightarrow} 1 | |
| $$ | |
| The arrow category of a category $C$ is the functor category $C^{\vec{I}}$. Explicitly, the objects of $C^{\vec{I}}$ are morphisms of $C$, while morphisms of $C^{\vec{I}}$ are commutative squares in $C$. There are functors dom, $\operatorname{cod}: C^{\vec{I}} \rightarrow C$ which, given a morphism $\left(h_{0}, h_{1}\right)$, return $h_{0}$, respectively, $h_{1}$. | |
| Proof. The proof that the arrow category is a category follows directly from the fact that it is defined as a functor category. Explicitly, composition law is induced point-wise by the composition in $C$. The fact that composition is induced point-wise makes it also obvious to prove that dom, cod are indeed functors. | |
| Proposition 3 (Functoriality of arrow and pointed objects categories). Let $\mathrm{F}: C \rightarrow D$ be a functor. Then $\mathrm{F}$ lifts to a functor $\mathrm{F}^{\vec{I}}: C^{\vec{I}} \rightarrow D^{\vec{I}}$ using the pointwise action of $\mathrm{F}$ on $C$. | |
| If moreover $C$ and $D$ have a chosen terminal object, and if $\mathrm{F}$ preserves it, then it also lifts to a functor $\mathrm{F}_{\bullet}: C_{\bullet} \rightarrow D_{\bullet}$ sending a pointed object $(x, v)$ of $C$ to $(\mathrm{F} x, \mathrm{~F} v)$, a pointed object of $D$. | |
| Proof. The functor $\mathrm{F}^{\vec{I}}$ is defined such that it acts by post-composition with $\mathrm{F}$ on objects of $C^{\vec{I}}$ and by right whiskering with $\mathrm{F}$ on morphisms. Identity and composition preservation easily follow from the definition. | |
| By definition of category of pointed objects, it is enough to prove that $\mathrm{F}: C \rightarrow D$ induces a functor $x / C \rightarrow F x / D$ on the respective coslice categories. In order to do that, it is enough to send an object $f: x \rightarrow y$ of $x / C$ to $F f: F x \rightarrow F y$ and a morphism $h$ of $x / C$ to $F h$. The functor $F$ preserves commutative diagrams, therefore $F h$ is indeed a morphism in $F x / D$. Identity and composition preservation easily follow from the fact that $F$ is a functor. | |
| Proposition 4 (Functoriality of the quotient). If $C$ has chosen pushouts and a terminal object $\mathbf{1}$, then for each morphism $f: x \rightarrow y$ in $C$, Definition 6 determines a pointed object $\mathrm{Q}(f):=(y / / f,[x])$ of $C$. This extends to a functor $\mathrm{Q}: C^{\vec{I}} \rightarrow C_{\text {• }}$. | |
| Lastly, if both $C$ and $D$ have chosen pushouts and a chosen terminal object $\mathbf{1}$, and if $\mathrm{F}$ preserves them, then $\mathrm{F}$ induces a commutative square of functors | |
|  | |
| Proof. First of all, let us build the functor Q. Definition 6 already provides a definition on objects. On morphisms, given $\left(h_{0}, h_{1}\right): f \rightarrow g$ in $C^{\vec{I}}$, corresponding to a commutative square | |
|  | |
| we have a diagram | |
|  | |
| where the left side commutes by assumption, the front and back by construction, and the top because 1 is terminal. Then the universal property of the front pushout square induces a unique morphism | |
| $$ | |
| \mathrm{Q}\left(h_{0}, h_{1}\right): x_{1} / / f \rightarrow y_{1} / / g | |
| $$ | |
| which completes the diagram to a cube whose sides are all commutative. | |
| In particular, $\left[x_{0}\right] \circ \mathrm{Q}\left(h_{0}, h_{1}\right)=\left[y_{0}\right]$, that is, $\mathrm{Q}\left(h_{0}, h_{1}\right)$ determines a morphism of pointed objects from $\left(x_{1} / / f,\left[x_{0}\right]\right)$ to $\left(y_{1} / / g,\left[y_{0}\right]\right)$. It is straightforward to check that this assignment respects composition and identities. | |
| Now, let $\mathrm{F}: C \rightarrow D$ preserve pushouts and terminal objects. First of all, notice that for each $f: x \rightarrow y$ in $C$ we have: | |
| $$ | |
| \mathrm{F}_{\bullet}(\mathrm{Q}(f))=\mathrm{F}_{\bullet}(y / / f,[x])=(\mathrm{F}(y / / f), \mathrm{F}[x])=(\mathrm{F} y / / \mathrm{F} f,[\mathrm{~F} x])=\mathrm{Q}\left(\mathrm{F}^{\vec{I}}(f)\right) | |
| $$ | |
| verifying the commutative square of functors on objects. As for morphisms, consider the following cubes: | |
|  | |
| The morphism $\mathrm{FQ}\left(h_{0}, h_{1}\right)$ makes the first cube commute, while the universal property of the pushout provides $\mathrm{Q}\left(\mathrm{F} h_{0}, \mathrm{~F} h_{1}\right)$ to close the second cube. But since $\mathrm{F}$ preserves the chosen pushouts and terminal objects, the two cubes are the same, and the universal property of the pushout implies the equation $\mathrm{FQ}\left(h_{0}, h_{1}\right)=\mathrm{Q}\left(\mathrm{F} h_{0}, \mathrm{~F} h_{1}\right)$, verifying the commutative square of functors on morphisms. | |
| Proposition 5. Let $C$ be a category and $x$ an object in $C$. The following are equivalent: | |
| (a) $\pi_{0}(C / x)=\{[x]\}$ | |
| (b) $x$ is a weak terminal object in $C$. | |
| Proof. Follows from Definition 2 and the explicit description given in Definition 7. | |
| Proposition $6\left(\pi_{0}(G / x)\right.$ for a groupoid). Let $G$ be a groupoid and $x$ an object in $G$. Then | |
| 1. $\pi_{0}(G / x)$ is a 'set', that is, a discrete poset. | |
| 2. As a pointed set, it is isomorphic to the set $\pi_{0}(G)$ of connected components of $G$, pointed with the connected component of $x$. | |
| Proof. In the poset reflection of $G,\|y\| \leq\|z\|$ if and only if there exists a morphism $f: y \rightarrow z$ in $G$, and since any such morphism is invertible, then $\|z\| \leq\|y\|$, so $\|y\|=\|z\|$. It follows that $\|G\|$ is already a discrete poset, whose elements are in bijection with the connected components of $G$, that is, with $\pi_{0}(G)$. | |
| The identity on $x$ factors through every morphism in $G / x$, so $\|G / x\|$ is the poset with a single element, that is, the terminal poset. We know that the map $\|\operatorname{dom}\|:\|G / x\| \rightarrow\|G\|$ selects the lower set of $\|x\|$ in $\|G\|$, which in this case only contains $\|x\|$ itself. Hence $\|$ dom $\|$ already exhibits $\|G\|$ as a pointed poset with basepoint $\|x\|$, which the quotient leaves unaffected. | |
| Definition 8 (Category of parallel arrows over an object). Let $C$ be a category and $x$ an object in $C$. The category of parallel arrows in $C$ over $x$ is the category $\operatorname{Par}(C / x)$ where: | |
| - Objects are pairs of morphisms $\left(f_{0}, f_{1}: y \rightarrow x\right)$ with codomain $x$. | |
| - A morphism from $\left(f_{0}, f_{1}: y \rightarrow x\right)$ to $\left(g_{0}, g_{1}: z \rightarrow x\right)$ is a morphism $h: y \rightarrow z$ such that $f_{0}=h \circ g_{0}$ and $f_{1}=h_{9} g_{1}$. | |
| This comes with a projection functor dom: $\operatorname{Par}(C / x) \rightarrow C$ sending a parallel pair of morphisms to its domain. | |
| Proof. Compositions and identities in $\operatorname{Par}(C / x)$ are as in $C$. Associativity and identity laws are also inherited from $C$, proving that $\operatorname{Par}(C / x)$ is a category. Proving the functoriality of dom is equally trivial. | |
| Proposition 7. Let $C$ be a category and $\mathbb{1}$ an object in $C$. The following are equivalent: | |
| (a) $\mathbb{1}$ is subterminal in $C$. | |
| (b) $\left(\mathrm{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)$ is a terminal object in $\operatorname{Par}(C / \mathbb{1})$; | |
| (c) $\left(\operatorname{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)$ is a weak terminal object in $\operatorname{Par}(C / \mathbb{1})$. | |
| Proof. Let us begin by proving that the first and second point are equivalent. For any couple of morphisms $f, g: x \rightarrow \mathbb{1}$, consider the following diagram, corresponding to the pair of objects $(f, g)$ and $\left(\mathrm{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)$ in $\operatorname{Par}(C / \mathbb{1})$ : | |
|  | |
| If $\mathbb{1}$ is subterminal in $C$, then $f=g$, so $f$ determines a morphism $(f, g) \rightarrow\left(\operatorname{id}_{\mathbb{1}}, \operatorname{id}_{\mathbb{1}}\right)$ in $\operatorname{Par}(C / \mathbb{1})$, proving weak terminality of $\left(\mathrm{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)$ : | |
|  | |
| Conversely, weak terminality in $\operatorname{Par}(C / \mathbb{1})$ implies that there is always some $h: x \rightarrow \mathbb{1}$ such that | |
|  | |
| commutes, implying | |
| $$ | |
| f=h_{9} \mathrm{id}_{\mathbb{1}}=g | |
| $$ | |
| hence subterminality of $\mathbb{1}$ in $C$. | |
| Now we prove that the last two points are equivalent. One direction is trivial. As for the other one, suppose $\left(\operatorname{id}_{\mathbb{1}}, \operatorname{id}_{\mathbb{1}}\right)$ is weak terminal in $\operatorname{Par}(C / \mathbb{1})$, and suppose that both $h, k: x \rightarrow \mathbb{1}$ make the diagram above commute. Then we have | |
| $$ | |
| f=h \circ \mathrm{id}_{\mathbb{1}}=h \quad f=k \circ \mathrm{id}_{\mathbb{1}}=k | |
| $$ | |
| hence $h=k$, completing the proof. | |
| Proposition 8. Let $C$ be a category and $x$ an object in $C$. The following are equivalent: | |
| (a) $\pi_{1}(C / x)=\{[x]\}$ | |
| (b) $x$ is subterminal in $C$. | |
| Proof. Follows from Definition 2 and the explicit description given in Definition 9. | |
| Corollary 1 . Let $C$ be a category and $x$ an object in $C$. The following are equivalent: | |
| (a) $\pi_{0}(C / x)=\{[x]\}$ and $\pi_{1}(C / x)=\{[x]\}$, | |
| (b) $x$ is a terminal object in $C$. | |
| Proof. $x$ is a terminal object in $C$ if and only if it is weak terminal and subterminal. Combine this with Proposition 5 and Proposition 8. | |
| Proposition $9\left(\pi_{1}(G / x)\right.$ for a groupoid). Let $G$ be a groupoid and $x$ an object in $G$. Then: | |
| 1. $\pi_{1}(G / x)$ is a 'set', that is, a discrete poset. | |
| 2. As a pointed set, it is isomorphic to the underlying pointed set of the group $\pi_{1}(G, x)=\operatorname{Hom}_{G}(x, x)$. Proof. First of all, when $G$ is a groupoid, so is $\operatorname{Par}(G / x)$, so the fact that $\pi_{1}(G / x)$ is discrete follows from the first point of Proposition 6. | |
| As for the second point, we define a function $\pi_{1}(G / x) \rightarrow \operatorname{Hom}_{G}(x, x)$ by | |
| $$ | |
| [x] \mapsto \operatorname{id}_{x}, \quad\|(f, g)\| \mapsto g^{-1} ; f . | |
| $$ | |
| First of all, this is well-defined, in the sense that it is independent of the representative of $\|(f, g)\|$ : if $\|(f, g)\|=\left\|\left(f^{\prime}, g^{\prime}\right)\right\|$, then there exists $h$ such that $f=h \circ f^{\prime}$ and $g=h \circ g^{\prime}$, hence | |
| $$ | |
| g^{-1} \circ f=\left(h \circ g^{\prime}\right)^{-1} \circ\left(h \circ f^{\prime}\right)=g^{\prime-1} \circ\left(h^{-1} \circ h\right) \circ f^{\prime}=g^{\prime-1} \circ f^{\prime} . | |
| $$ | |
| Moreover, it is by construction a map of pointed sets. It is surjective: $\operatorname{id}_{x}$ is the image of $[x]$, and any $f: x \rightarrow x$ such that $f \neq \mathrm{id}_{x}$ is the image of $\left\|\left(\mathrm{id}_{x}, f\right)\right\|$. | |
| To conclude, we need to prove that the function is also injective. Suppose that $(f, g: y \rightarrow x)$ and $\left(f^{\prime}, g^{\prime}: z \rightarrow x\right)$ are two parallel pairs such that $g^{-1} \circ f=g^{\prime-1} \circ f^{\prime}$. Then let $h: y \rightarrow z$ be defined by | |
| $$ | |
| h:=g \circ g^{\prime-1}=g \circ g^{\prime-1} \circ \mathrm{id}_{z}=g \circ g^{\prime-1} \circ f^{\prime} \circ f^{\prime-1}=g_{9} g^{-1} \circ f_{9} f^{\prime-1}=f_{9} \circ f^{\prime-1} . | |
| $$ | |
|  | |
| $\left(f^{\prime}, g^{\prime}\right)$ in $\operatorname{Par}(G / x)$. Since $G$ is a groupoid, $h$ is invertible, and $\|(f, g)\|=\left\|\left(f^{\prime}, g^{\prime}\right)\right\|$. This proves that the function is injective. | |
| \section{Proof of Proposition 10} | |
| Proving Proposition 10 requires to build a hefty amount of theory, which is why we reserved a subsection of the Appendix only to this. | |
| Definition 12 (Past extension). Let $A$ be a category. A past extension of $A$ is a functor $l: A \hookrightarrow B$ with the following property: there exists a functor $\chi_{A}: B \rightarrow \vec{I}$ such that | |
|  | |
| is a pullback in Cat. | |
| Remark 4. The following is an equivalent characterisation of past extensions: there exist a category $\bar{A}$ and a profunctor $\mathrm{H}: \bar{A}^{\mathrm{op}} \times A \rightarrow$ Set such that | |
| 1. $B$ is isomorphic to the collage, also known as cograph, of $\mathrm{H}$, and | |
| 2. $l$ is, up to isomorphism, the inclusion of $A$ into the collage. | |
| A technical name for a functor satisfying the condition on $l$ is codiscrete coopfibration; it is one leg of a two-sided codiscrete cofibration of categories. | |
| The idea is that $l$ embeds $A$ into a larger category, whose objects outside of the image of $A$ only have morphisms pointing towards $A$, hence are "in the past" of $A$ if we interpret the direction of morphisms as a time direction. Notice that the fact that (3) is a pullback implies that $l$ is injective on objects and morphisms, using their representation as functors from 1 and $\vec{I}$, respectively. The following picture illustrates the bipartition of $B$ induced by $\chi_{A}$, with the fibre $\bar{A}$ of 0 "in the past" of the fibre $A$ of 1 : | |
|  | |
| Definition 13 (Category of past extensions). Let $A$ be a category. The category of past extensions of $A$ is the large category $\operatorname{Past}(A)$ whose | |
| - objects are past extensions $l: A \hookrightarrow B$, and | |
| - a morphism from $(\imath: A \hookrightarrow B)$ to $\left(j: A \hookrightarrow B^{\prime}\right)$ is a factorisation of $j$ through $l$, that is, a functor $\mathrm{K}: B \rightarrow B^{\prime}$ such that $j=\imath$ \% $\mathrm{K}$. | |
| Proposition 18 (The indexed category of past extensions of functors). Let $A$ and $C$ be categories. Then there exists a functor | |
| $$ | |
| \operatorname{Ext}_{C}^{A}: \operatorname{Past}(A)^{\mathrm{op}} \times C^{A} \rightarrow \mathbf{C a t} | |
| $$ | |
| whose object part is defined as follows: given a past extension $\imath: A \hookrightarrow B$ and a functor $\mathrm{F}: A \rightarrow C$, the category $\operatorname{Ext}_{C}^{A}(l, \mathrm{~F})$ is the subcategory of $C^{B}$ whose | |
| - objects are (strict) extensions of $\mathrm{F}$ along $l$, that is, functors $\tilde{\mathrm{F}}: B \rightarrow C$ such that | |
|  | |
| strictly commutes, and | |
| - morphisms from $\tilde{\mathrm{F}}_{1}$ to $\tilde{\mathrm{F}}_{2}$ are natural transformations $\tau: \tilde{\mathrm{F}}_{1} \Rightarrow \tilde{\mathrm{F}}_{2}$ that restrict along $l$ to the identity natural transformation on $\mathrm{F}$. | |
| Remark 5. Before giving a detailed proof, we give a more high-level explanation of where Ext $_{C}^{A}$ comes from. When $l: A \hookrightarrow B$ is a coopfibration of categories and $C$ a category, exponentiating $l$ always produces an opfibration $\iota^{*}: C^{B} \rightarrow C^{A}$. In particular, when $l$ is a past extension, $\iota^{*}$ can be endowed with a canonical splitting, defining a contravariant functor | |
| $$ | |
| \operatorname{Past}(A)^{\mathrm{op}} \rightarrow \operatorname{SpOpfib}\left(C^{A}\right) | |
| $$ | |
| to the large category of split opfibrations and split cocartesian morphisms over $C^{A}$. Via the Grothendieck construction, the latter is equivalent to the large category of functors $\mathbf{C a t}^{C^{A}}$. Composing with the inverse of the Grothendieck construction, we thus obtain a functor | |
| $$ | |
| \operatorname{Past}(A)^{\mathrm{op}} \rightarrow \mathbf{C a t}^{C^{A}} | |
| $$ | |
| whose uncurried version is, up to natural isomorphism, our $\operatorname{Ext}_{C}^{A}$. Proof. Given a morphism K: $(\imath: A \hookrightarrow B) \rightarrow\left(j: A \hookrightarrow B^{\prime}\right)$ in $\operatorname{Past}(A)$, | |
| $$ | |
| \mathrm{K}^{*}:=\operatorname{Ext}_{C}^{A}(\mathrm{~K}, \mathrm{~F}): \operatorname{Ext}_{C}^{A}(j, \mathrm{~F}) \rightarrow \operatorname{Ext}_{C}^{A}(l, \mathrm{~F}) | |
| $$ | |
| is the functor that acts by precomposition, sending | |
| - $\tilde{\mathrm{F}}: B^{\prime} \rightarrow C$ to $\mathrm{K}_{9} \circ \tilde{\mathrm{F}}: B \rightarrow C$, and | |
| - $\tau: \tilde{\mathrm{F}}_{1} \Rightarrow \tilde{\mathrm{F}}_{2}$ to $\mathrm{K}_{9} \tau: \mathrm{K}_{9} \tilde{\mathrm{F}}_{1} \Rightarrow \mathrm{K}_{9} \tilde{\mathrm{F}}_{2}$. | |
| This is well-defined as | |
| $$ | |
| \iota_{9}^{\circ} \mathrm{K}_{9}^{\circ} \tilde{\mathrm{F}}=j_{9}^{\circ} \tilde{\mathrm{F}}=\mathrm{F}, \quad \iota_{9}^{\circ} \mathrm{K}_{9}^{\circ} \tau=j_{9}^{\circ} \tau=\mathrm{id}_{\mathrm{F}} . | |
| $$ | |
| Moreover, it is straightforward to check that | |
| $$ | |
| \left(\mathrm{id}_{l}\right)^{*}=\mathrm{id}_{\mathrm{Ext}_{C}^{A}(l, \mathrm{~F})}, \quad\left(\mathrm{K}_{q} \mathrm{~L}\right)^{*}=\mathrm{L}^{*} ; \mathrm{K}^{*} | |
| $$ | |
| for any composable pair $\mathrm{K}, \mathrm{L}$ of morphisms in $\operatorname{Past}(A)$. | |
| Given a natural transformation $\alpha: \mathrm{F} \Rightarrow \mathrm{G}$ between functors $\mathrm{F}, \mathrm{G}: A \rightarrow C$, the functor | |
| $$ | |
| \alpha_{*}:=\operatorname{Ext}_{C}^{A}(l, \alpha): \operatorname{Ext}_{C}^{A}(\imath, \mathrm{F}) \rightarrow \operatorname{Ext}_{C}^{A}(l, \mathrm{G}) | |
| $$ | |
| is defined as follows. Given an object $\tilde{\mathrm{F}}: B \rightarrow C$ of $\operatorname{Ext}_{C}^{A}(l, \mathrm{~F})$, the functor $\alpha_{*} \tilde{\mathrm{F}}: B \rightarrow C$ is defined, on each morphism $f: x \rightarrow y$ in $B$, by | |
| $$ | |
| \alpha_{*} \tilde{\mathrm{F}}(f):= \begin{cases}\mathrm{G}\left(f^{\prime}\right) & \text { if } \chi_{A}(f)=1 \text { and } f=\imath\left(f^{\prime}\right), \\ \tilde{\mathrm{F}}(f) ; \alpha_{y^{\prime}} & \text { if } \chi_{A}(f)=a \text { and } y=\imath\left(y^{\prime}\right), \\ \tilde{\mathrm{F}}(f) & \text { if } \chi_{A}(f)=0 .\end{cases} | |
| $$ | |
| By construction $\iota_{9}^{\circ} \alpha_{*} \tilde{\mathrm{F}}=\mathrm{G}$. The following picture illustrates the definition. | |
|  | |
| Let us show that $\alpha_{*} \tilde{F}$ is well-defined as a functor. | |
| 1. Given an identity $\mathrm{id}_{x}$ in $B$, necessarily $\chi_{A}\left(\operatorname{id}_{x}\right)=0$, in which case | |
| $$ | |
| \alpha_{*} \tilde{\mathrm{F}}\left(\mathrm{id}_{x}\right)=\tilde{\mathrm{F}}\left(\mathrm{id}_{x}\right)=\operatorname{id}_{\tilde{\mathrm{F}}(x)}, | |
| $$ | |
| or $\chi_{A}\left(\mathrm{id}_{x}\right)=1$, in which case | |
| $$ | |
| \alpha_{*} \tilde{\mathrm{F}}\left(\mathrm{id}_{x}\right)=\mathrm{G}\left(\mathrm{id}_{x^{\prime}}\right)=\mathrm{id}_{\mathrm{G}\left(x^{\prime}\right)}, | |
| $$ | |
| where $x^{\prime}$ is the unique lift of $x$ to $A$. Thus $\alpha_{*} \tilde{\mathrm{F}}$ preserves identities. 2. Given a composable pair $f: x \rightarrow y, g: y \rightarrow z$, we have the following cases. | |
| - If $\chi_{A}(f)=\chi_{A}(g)=1$, then $\chi_{A}(f \circ g)=1$, and | |
| $$ | |
| \alpha_{*} \tilde{\mathrm{F}}(f) ; \alpha_{*} \tilde{\mathrm{F}}(g)=\mathrm{G}\left(f^{\prime}\right) ; \mathrm{G}\left(g^{\prime}\right)=\mathrm{G}\left(f^{\prime} ; g^{\prime}\right)=\alpha_{*} \tilde{\mathrm{F}}\left(f^{\circ} g\right), | |
| $$ | |
| where $f^{\prime}, g^{\prime}$ are the unique lifts of $f, g$ to $A$. | |
| - If $\chi_{A}(f)=\chi_{A}(g)=0$, then $\chi_{A}(f \circ g)=0$, and | |
| $$ | |
| \alpha_{*} \tilde{\mathrm{F}}(f){ }_{q} \alpha_{*} \tilde{\mathrm{F}}(g)=\tilde{\mathrm{F}}(f) \circ \tilde{\mathrm{F}}(g)=\tilde{\mathrm{F}}\left(f_{9} g\right)=\alpha_{*} \tilde{\mathrm{F}}(f \circ g) . | |
| $$ | |
| - If $\chi_{A}(f)=0$ and $\chi_{A}(g)=a$, then $\chi_{A}\left(f_{\circ}^{\circ} g\right)=a$, and | |
|  | |
| where $z^{\prime}$ is the unique lift of $z$ to $A$. | |
| - If $\chi_{A}(f)=a$ and $\chi_{A}(g)=1$, then $\chi_{A}(f \circ g)=a$, and | |
| $$ | |
| \alpha_{*} \tilde{\mathrm{F}}(f){ }_{9} \alpha_{*} \tilde{\mathrm{F}}(g)=\tilde{\mathrm{F}}(f){ }_{9} \alpha_{y^{\prime}}{ }^{\circ} \mathrm{G}\left(g^{\prime}\right)=\tilde{\mathrm{F}}(f){ }_{9} \mathrm{~F}\left(g^{\prime}\right){ }_{9} \alpha_{z^{\prime}} | |
| $$ | |
| where $g^{\prime}: y^{\prime} \rightarrow z^{\prime}$ is the unique lift of $g$ to $A$, and we used naturality of $\alpha$. Since $\mathrm{F}\left(g^{\prime}\right)=\tilde{\mathrm{F}}\left(l\left(g^{\prime}\right)\right)=\tilde{\mathrm{F}}(g)$, this is equal to | |
| $$ | |
| \tilde{\mathrm{F}}(f) \varsubsetneqq \tilde{\mathrm{F}}(g) \% \alpha_{z^{\prime}}=\alpha_{*} \tilde{\mathrm{F}}(f \circ g) \text {. } | |
| $$ | |
| No other cases are possible. | |
| This proves that $\alpha_{*} \tilde{\mathrm{F}}$ is well-defined. | |
| Given a morphism $\tau: \tilde{\mathrm{F}}_{1} \Rightarrow \tilde{\mathrm{F}}_{2}$ of $\operatorname{Ext}_{C}^{A}(l, \mathrm{~F})$, the natural transformation $\alpha_{*} \tau: \alpha_{*} \tilde{\mathrm{F}}_{1} \Rightarrow \alpha_{*} \tilde{\mathrm{F}}_{2}$ is defined, on each object $x$ in $B$, by | |
| $$ | |
| \left(\alpha_{*} \tau\right)_{x}:= \begin{cases}\operatorname{id}_{\mathrm{G}\left(x^{\prime}\right)} & \text { if } \chi_{A}(x)=1 \text { and } x=\imath\left(x^{\prime}\right), \\ \tau_{x} & \text { if } \chi_{A}(x)=0\end{cases} | |
| $$ | |
| To show that this is well-defined as a natural transformation, consider a morphism $f: x \rightarrow y$ in $B$. | |
| - If $\chi_{A}(f)=1$ and $f^{\prime}: x^{\prime} \rightarrow y^{\prime}$ is the unique lift of $f$ to $A$, then | |
|  | |
| - If $\chi_{A}(f)=a$ and $y^{\prime}$ is the unique lift of $y$ to $A$, then | |
|  | |
| since $\tau_{y}=\tau_{l\left(y^{\prime}\right)}=\mathrm{id}_{\mathrm{F}\left(y^{\prime}\right)}$. By naturality of $\tau$, this is equal to | |
| $$ | |
| \tau_{x} \circ \tilde{\mathrm{F}}_{2}(f) ; \alpha_{y^{\prime}}=\left(\alpha_{*} \tau\right)_{x} \circ \alpha_{*} \tilde{\mathrm{F}}_{2}(f) | |
| $$ | |
| - If $\chi_{A}(f)=0$, then | |
| $$ | |
| \alpha_{*} \tilde{\mathrm{F}}_{1}(f) \stackrel{\circ}{ }\left(\alpha_{*} \tau\right)_{y}=\tilde{\mathrm{F}}_{1}(f) \stackrel{\circ}{ } \tau_{y}=\tau_{x} \circ \tilde{\mathrm{F}}_{2}(f)=\left(\alpha_{*} \tau\right)_{x}{ }^{\circ} \alpha_{*} \tilde{\mathrm{F}}_{2}(f) . | |
| $$ | |
| This concludes the definition of $\alpha_{*}$. It is straightforward to check that | |
| $$ | |
| \left(\mathrm{id}_{\mathrm{F}}\right)_{*}=\operatorname{id}_{\mathrm{Ext}_{C}^{A}(l, \mathrm{~F})}, \quad(\alpha \varsubsetneqq \beta)_{*}=\alpha_{*} \circ \beta_{*} | |
| $$ | |
| for all pairs of natural transformations $\alpha, \beta$ composable as morphisms in $C^{A}$. Finally, one can verify that, for all morphisms K: $\mathrm{K} \rightarrow j$ in $\operatorname{Past}(A)$ and $\alpha: \mathrm{F} \rightarrow \mathrm{G}$ in $C^{A}$, the diagram of functors | |
|  | |
| commutes in Cat. Thus we can define $\operatorname{Ext}_{C}^{A}(\mathrm{~K}, \alpha)$ as either path in the commutative diagram, and conclude that $\operatorname{Ext}_{C}^{A}$ is well-defined as a functor. | |
| Proposition 19 (Covariance of the $\mathrm{Ext}_{C}^{A}$ ). The assignment $C \mapsto \operatorname{Ext}_{C}^{A}$ extends to a functor | |
| $$ | |
| \mathrm{Ext}^{A}: \text { Cat } \rightarrow \mathscr{C} \text { at } \uparrow \text { Cat } | |
| $$ | |
| Proof. Given a functor $\mathrm{P}: C \rightarrow D$, post-composition with $\mathrm{P}$ defines a functor $\mathrm{P}_{*}: C^{A} \rightarrow D^{A}$. Then there is a natural transformation | |
|  | |
| defined as follows: given a past extension $\imath: A \hookrightarrow B$ and a functor $\mathrm{F}: A \rightarrow C$, the functor | |
| $$ | |
| \operatorname{Ext}_{\mathrm{P}}^{A}(l, \mathrm{~F}): \operatorname{Ext}_{C}^{A}(l, \mathrm{~F}) \rightarrow \operatorname{Ext}_{D}^{A}(l, \mathrm{~F} \circ \mathrm{P}) | |
| $$ | |
| acts both on objects and on morphisms by post-composition with P. It is straightforward to check that the assignment $P \mapsto$ Ext $_{\mathrm{P}}^{A}$ respects identities and composition in Cat. | |
| Remark 6 (General functoriality pattern). A fixed morphism $\mathrm{K}$ in $\operatorname{Past}(A)$ is classified by a functor $\vec{I} \rightarrow \operatorname{Past}(A)$. Evaluating $\operatorname{Ext}_{C}^{A}$ at $\mathrm{K}$ thus determines a functor | |
| $$ | |
| \operatorname{Ext}_{C}^{A}(\mathrm{~K},-): \vec{I} \times C^{A} \rightarrow \mathbf{C a t} | |
| $$ | |
| which we can curry to obtain a functor | |
| $$ | |
| \Lambda . \operatorname{Ext}_{C}^{A}(\mathrm{~K},-): C^{A} \rightarrow \mathbf{C a t}^{\vec{I}} | |
| $$ | |
| Given a functor P: $C \rightarrow D$, we can also "curry the natural transformation" in (4) to obtain a diagram | |
|  | |
| which is part of a functor $\mathbf{C a t} \rightarrow \mathscr{C}$ at $\rceil \mathbf{C a t}^{\vec{I}}$. | |
| Post-composing with the functor $\mathbf{C a t}^{\vec{I}} \rightarrow$ Pos. from (1) we obtain a covariant family of functors $C^{A} \rightarrow$ Pos. | |
| We will show that, for suitable choices of $A$ and $\mathrm{K}$, the image of these functors is included in the subcategory of Pos. on the zeroth and first homotopy posets of $C$ or categories associated with $C$, exhibiting various kinds of functorial dependence of homotopy posets. | |
| Proposition 10 (Functoriality of the homotopy posets). Let $C$ be a category, $i \in\{0,1\}$. Then: | |
| 1. the assignment $x \mapsto \pi_{i}(C / x)$ extends to a functor $\pi_{i}(C /-): C \rightarrow$ Pos $_{\bullet}$; | |
| 2. a functor $\mathrm{F}: C \rightarrow D$ induces a natural transformation $\pi_{i}(\mathrm{~F}): \pi_{i}(C /-) \Rightarrow \pi_{i}(D / \mathrm{F}-)$. | |
| Given another functor $\mathrm{G}: D \rightarrow E$, this assignment satisfies | |
| $$ | |
| \pi_{i}(\mathrm{~F} \% \mathrm{G})=\pi_{i}(\mathrm{~F}) ; \pi_{i}(\mathrm{G}), \quad \pi_{i}\left(\mathrm{id}_{C}\right)=\mathrm{id}_{\pi_{i}(C /-)} . | |
| $$ | |
| Proof. We will derive the results for both $i \in\{0,1\}$ from the general functoriality pattern of Remark 6. | |
| First we consider the case $i=0$. Let 1 be the terminal category. The inclusion $\mathrm{K}_{0}$ of the endpoints of the walking arrow induces a morphism in $\operatorname{Past}(\mathbf{1})$, depicted as follows: | |
|  | |
| We claim that, up to isomorphism of categories, | |
| $$ | |
| \Lambda . \operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{0},-\right): C^{1} \rightarrow \mathbf{C a t}^{\vec{I}} | |
| $$ | |
| sends an object $x$ of $C^{\mathbf{1}}$ - which is, equivalently, an object of $C$ - to the slice projection functor | |
| $$ | |
| \text { dom: } C / x \rightarrow C \text {. } | |
| $$ | |
| The domain of $\Lambda . \operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{0}, x\right)$ is the category $\operatorname{Ext}_{C}^{1}(1, x)$ whose | |
| - objects are functors $f: \vec{I} \rightarrow C$ such that | |
|  | |
| commutes, which are in bijection with morphisms $f$ of $C$ whose codomain is $x$, and - morphisms from $f$ to $g$ are natural transformations $h: f \Rightarrow g$ - which are in bijection with commutative squares | |
|  | |
| in $C$ - that restrict to the identity along 1: $\mathbf{\hookrightarrow} \vec{I}$, that is, are such that $h_{1}=\mathrm{id}_{x}$. These are in bijection with factorisations of $f$ through $g$. | |
| This establishes an isomorphism between $\operatorname{Ext}_{C}^{1}(1, x)$ and $C / x$. The codomain of $\Lambda . \operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{0}, x\right)$ is the category $\operatorname{Ext}_{C}^{1}\left(l_{1}, x\right)$ whose | |
| - objects are functors $\left(y_{0}, y_{1}\right): \mathbf{1}+\mathbf{1} \rightarrow C$ such that | |
|  | |
| commutes, which are in bijection with pairs of objects $\left(y_{0}, y_{1}\right)$ of $C$ such that $y_{1}=x$, which are in bijection with objects of $C$, and | |
| - morphisms from $(y, x)$ to $(z, x)$ are in bijection with pairs of morphisms | |
|  | |
| in $C$ that restrict to the identity along $l_{1}$, that is, are such that $h_{1}=\mathrm{id}_{x}$. These are in bijection with morphisms $y \rightarrow z$. | |
| This establishes an isomorphism between $\operatorname{Ext}_{C}^{1}\left(l_{1}, x\right)$ and $C$. The functor $\operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{0}, x\right)$ acts by restriction of $f: \vec{I} \rightarrow C$ along $\mathrm{K}_{0}: \mathbf{1}+\mathbf{1} \hookrightarrow \vec{I}$; through the isomorphisms, this acts by mapping $f: y \rightarrow x$ to its domain $y$. This is, by inspection, the same as the action of dom. | |
| We define | |
| $$ | |
| \pi_{0}(C /-): C \rightarrow \text { Pos. } | |
| $$ | |
| to be the post-composition of $\Lambda . \operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{0},-\right)$ with the functor of Equation 1. It follows from our argument that, up to isomorphism, this sends $x$ to the homotopy poset $\pi_{0}(C / x)$. The covariance in $C$ then follows as an instance of Equation 6: given a functor $\mathrm{F}: C \rightarrow D$, we whisker the natural transformation $\Lambda . \operatorname{Ext}_{\mathrm{F}}^{1}\left(\mathrm{~K}_{0},-\right)$ with the functor of (1) to obtain $\pi_{0}(\mathrm{~F}): \pi_{0}(C /-) \Rightarrow \pi_{0}(D / \mathrm{F}-)$. | |
| Now, let us focus on the first homotopy poset. The functor $\mathrm{K}_{1}$ identifying two parallel arrows also induces a morphism in $\operatorname{Past}(\mathbf{1})$, depicted as follows: | |
| Here, Par denotes the "walking parallel pair of arrows". We claim that, up to isomorphism of categories, | |
| $$ | |
| \Lambda . \operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{1},-\right): C \rightarrow \mathbf{C a t}^{\vec{I}} | |
| $$ | |
| sends an object $x$ of $C$ to the slice projection functor | |
| $$ | |
| \text { dom: } \operatorname{Par}(C / x) /\left(\operatorname{id}_{x}, \operatorname{id}_{x}\right) \rightarrow \operatorname{Par}(C / x) . | |
| $$ | |
| We have already established that the domain of $\Lambda . \operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{1}, x\right)$, which is the category $\operatorname{Ext}_{C}^{1}(1, x)$, is isomorphic to $C / x$, which can be shown to be isomorphic to $\operatorname{Par}(C / x) /\left(\mathrm{id}_{x}, \mathrm{id}_{x}\right)$ using Proposition 7 . | |
| The codomain of $\Lambda . \operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{1}, x\right)$ is the category $\operatorname{Ext}_{C}^{1}(c, x)$ whose | |
| - objects are functors $\left(f_{0}, f_{1}\right):$ Par $\rightarrow C$ such that | |
|  | |
| commutes, which are in bijection with pairs of morphisms $\left(f_{0}, f_{1}\right)$ of $C$ whose codomain is $x$, and | |
| - morphisms from the pair $\left(f_{0}, f_{1}\right)$ to $\left(g_{0}, g_{1}\right)$ are natural transformations $h:\left(f_{0}, f_{1}\right) \Rightarrow\left(g_{0}, g_{1}\right)$ that restrict to the identity along $c$, which are in bijection with morphisms $h$ such that $f_{0}=h ; g_{0}$ and $f_{1}=h ; g_{1}$. | |
| This establishes an isomorphism between $\operatorname{Ext}_{C}^{1}(c, x)$ and $\operatorname{Par}(C / x)$. | |
| The functor $\operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{1}, x\right)$ acts by precomposing $f: \vec{I} \rightarrow C$ with $\mathrm{K}_{1}:$ Par $\rightarrow \vec{I}$, which through the isomorphisms sends a pair $(f, f)$ with its unique morphism to $\left(\mathrm{id}_{x}, \mathrm{id}_{x}\right)$ to the pair $(f, f)$ on its own. This is, by inspection, the same as the action of dom. | |
| We define | |
| $$ | |
| \pi_{1}(C /-): C \rightarrow \text { Pos. } | |
| $$ | |
| to be the post-composition of $\Lambda . \operatorname{Ext}_{C}^{1}\left(\mathrm{~K}_{1},-\right)$ with the functor of Equation 1. It follows from our argument that, up to isomorphism, this sends $x$ to the homotopy poset $\pi_{1}(C / x)$. Again, we obtain covariance in $C$ by whiskering instances of Equation 6 . This completes the proof. | |
| \section{Obstructions to a morphism being iso} | |
| Proposition 11. Let $f: X \rightarrow Y$ be a morphism in a category $C$. Then: | |
| - $f$ is split epi in $C$ if and only if $f$ is weak terminal in $C / Y$, | |
| - $f$ is mono in $C$ if and only if $f$ is subterminal in $C / Y$. | |
| Proof. As for the first point, $f: X \rightarrow Y$ being split epi in $C$ means that there is a morphism $e: Y \rightarrow X$ in $C$ such that $e_{9} f=\mathrm{id}_{Y}$. This means that for every morphism $g: Z \rightarrow Y$ the following triangle commutes: | |
|  | |
| implying subterminality of $f$ in $C / Y$. | |
| The other way around, $f$ weak terminal in $C / Y$ means that for each $g: Z \rightarrow Y$ there exists a morphism $e: Z \rightarrow X$ making the following triangle commute: | |
|  | |
| In particular, for $g:=\mathrm{id}_{Y}$, we get $e: Y \rightarrow X$ such that $e_{9}^{\circ} f=\mathrm{id}_{Y}$, proving that $f$ is split epi in $C$. | |
|  | |
| equivalent to commutativity of the following diagram: | |
|  | |
| From this, it follows immediately that $f$ being mono in $C$ implies $g_{1}=g_{2}$, hence subterminality in $C / Y$, and vice-versa. | |
| Corollary 2. Let $f: X \rightarrow Y$ be a morphism in a category $C$. Then: | |
| - $f$ is split epi if and only if $\pi_{0}((C / Y) / f)$ is trivial; | |
| - $f$ is mono if and only if $\pi_{1}((C / Y) / f)$ is trivial, and: | |
| - $f$ is iso if and only if both $\pi_{0}((C / Y) / f)$ and $\pi_{1}((C / Y) / f)$ are trivial. | |
| Proof. First notice that a morphism is iso if and only if it is split epi and mono, so the third condition is a consequence of the first two. Proposition 11 reduces the problem to proving: | |
| - $\mathbb{1}$ is weak terminal in $C$ iff $\pi_{0}(C / \mathbb{1},[\mathbb{1}])$ is trivial; | |
| - $\mathbb{1}$ is subterminal in $C$ iff $\pi_{1}(C / \mathbb{1},[\mathbb{1}])$ is trivial; | |
| For the first point, $\mathbb{1}$ is weak terminal in $C$ iff $\|\mathbb{1}\|$ is the greatest element in $\|C\|$ (Proposition 2), which in turn is equivalent to say that the downward closure of $\|\mathbb{1}\|$ contains all $\|C\|$. Since the quotient functor $\mathrm{Q}$ collapses the whole downward closure of $\|\mathbb{1}\|$ to a single point, this is equivalent to say that $\pi_{0}(C / \mathbb{1},[\mathbb{1}])$ is trivial. | |
| As for the second point, the proof is the same by remembering that by Definition 9 | |
| $$ | |
| \left(\pi_{1}(C / \mathbb{1}),[\mathbb{1}]\right):=\left(\pi_{0}\left(\operatorname{Par}(C / \mathbb{1}) /\left(\mathrm{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)\right),\left[\left(\mathrm{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)\right]\right) | |
| $$ | |
| and that $\mathbb{1}$ is subterminal in $C$ iff $\left(\mathrm{id}_{\mathbb{1}}, \mathrm{id}_{\mathbb{1}}\right)$ is weak terminal in $\operatorname{Par}(C / \mathbb{1})$ (Proposition 7 ). | |
| Proposition 12. Let $f: X \rightarrow Y$ be a function between sets. $\|$ Set $/ Y \|$ is isomorphic, as a poset, to the power set $\mathscr{P} Y$, via the assignment $(S \subseteq Y) \mapsto\left\|l_{S}\right\|$, where $l_{S}$ is the injective function including $S$ into $Y$. Through this bijection, $\|f\|$ corresponds to the image $f(X)$ of $f$. Proof. Fix $S$ a subset of $\mathscr{P} Y$. The injection $\iota_{S}: S \hookrightarrow Y$ is a function of sets with codomain $Y$, hence is an object of Set $/ Y$, and, as a consequence, part of the equivalence class $\|l: S \hookrightarrow Y\|$ in $\|$ Set $/ Y \|$. So the assignment $S \mapsto\|l: S \hookrightarrow Y\|$ makes sense. We now have to prove that this assignment is order preserving, injective and surjective. | |
| If $S \subseteq T$, then letting $j: S \hookrightarrow T$ be the corresponding inclusion of sets, we have | |
|  | |
| So $j$ defines a morphism $\iota_{S} \rightarrow l_{T}$ in Set $/ Y$, so by definition $\left\|\iota_{S}: S \hookrightarrow Y\right\| \leq\left\|l_{T}: T \hookrightarrow Y\right\|$, and the order is preserved. | |
| As for injectivity, suppose that $S \neq T$, and suppose without loss of generality that there is an element $s \in S \backslash T$. Then there is no function $g: T \rightarrow S$ such that the following triangle commutes: | |
|  | |
| since for all $g$ we have $l_{S}(s)=s \neq f(s)=l_{T}(f(s))$. Then $\left\|l_{S}: S \hookrightarrow Y\right\| \not \subset\left\|l_{T}: T \hookrightarrow Y\right\|$, and injectivity is proved. | |
| Finally, let $\|f: X \rightarrow Y\|$ be any element of $\|$ Set $/ Y \|$, and recall that | |
| $$ | |
| f(X):=\{y \in Y \mid \text { there exists } x \in X \text { such that } y=f(x)\} . | |
| $$ | |
| Then we have a surjective function $\tilde{f}: X \rightarrow f(X)$, defined as $f$ with codomain restricted to its image, which assuming the axiom of choice has a section $s: f(X) \rightarrow X$ so that | |
|  | |
| commute. It follows that $\left\|l_{f(X)}\right\| \geq\|f\|$ and $\left\|l_{f(X)}\right\| \leq\|f\|$, so we can conclude that $\|f\|=\left\|l_{f(X)}\right\|$. This proves both that the assignment $S \mapsto\left\|l_{S}\right\|$ is surjective and that $f(X) \mapsto\|f\|$, concluding the proof. | |
| Proposition 13. Let $X \times_{f} X$ be the pullback of $f$ along itself - that is, the set $\left\{\left(x_{0}, x_{1}\right) \mid f\left(x_{0}\right)=f\left(x_{1}\right)\right\}$ - and let $p_{f}: X \times_{f} X \rightarrow Y$ be the function $\left(x_{0}, x_{1}\right) \mapsto f\left(x_{0}\right)=f\left(x_{1}\right)$. Then: | |
| 1. $\|\operatorname{Par}((\mathbf{S e t} / Y) / f)\|$ is isomorphic to $\mathscr{P}\left(X \times_{f} X\right)$ via the assignment $\left(S \subseteq X \times_{f} X\right) \mapsto\left\|\left(\left.p_{0}\right|_{S},\left.p_{1}\right|_{S}\right)\right\|$, where $\left.p_{i}\right|_{S}$ are the projections $X \times_{f} X \rightarrow Y$, restricted to $S$, seen as morphisms $\left.p_{f}\right|_{S} \rightarrow f$ in $\|\operatorname{Par}((\operatorname{Set} / Y) / f)\|$ | |
| 2. through this bijection, $\left\|\left(\mathrm{id}_{f}, \mathrm{id}_{f}\right)\right\|$ is identified with the diagonal $\Delta X$. Proof. To understand how the assignment works, look at the following diagram. The blue arrow $S \rightarrow Y$ is just $\left.p_{f}\right|_{S}$. The black diagram commutes because of the property of pullbacks. The two sides of the square are both $f$, hence can be identified. The parallel pair of arrows $\left(\left.p_{0}\right|_{S},\left.p_{1}\right|_{S}\right)$ are hence a couple of morphisms from $\left.p_{f}\right|_{S}$ to $f$ in Set $/ Y$, hence by definition an object in $\operatorname{Par}((\mathbf{S e t} / Y) / f)$. Then it makes sense to send the subset $S$ to $\left\|\left(\left.p_{0}\right|_{S},\left.p_{1}\right|_{S}\right)\right\|$ in $\|\operatorname{Par}((\mathbf{S e t} / Y) / f)\|$. | |
|  | |
| Verifying that this is a order-preserving bijection is tedious, but not difficult, as it mimicks the proof of Proposition 12. From the picture it should also be clear that when $S$ is $X$ and $S \rightarrow X \times_{f} X$ is the diagonal morphism, the blue arrow $S \rightarrow Y$ becomes $f$, and $\left.p_{0}\right|_{S}$ and $\left.p_{1}\right|_{S}$ are just $\mathrm{id}_{X}$ in $C$. $\operatorname{But~}_{X}$ can also be seen as a morphism from $f$ to itself in Set $/ Y$, hence $\operatorname{id}_{X}$ in $C$ is also $\operatorname{id}_{f}$ in Set $/ Y$. So the diagonal $\Delta X$ corresponds to $\left\|\left(\operatorname{id}_{f}, \operatorname{id}_{f}\right)\right\|$ in $\|\operatorname{Par}((\operatorname{Set} / Y) / f)\|$. | |
| Definition 14 (Join of categories). Let $C, D$ be categories. The join of $C$ and $D$ is the collage $C \star D$ of the unique profunctor $C^{\mathrm{op}} \times D \rightarrow$ Set sending every pair of objects to the one-element set. | |
| More explicitly, $C \star D$ is obtained from the disjoint union of $C$ and $D$ by adding a unique morphism from each object $x$ in $C$ to each object $y$ in $D$. With the empty category as unit, the join determines a non-symmetric, semicocartesian monoidal structure on Cat. We refer to [16] for more details. | |
| Proposition 20. Let $\imath: A \hookrightarrow B$ be a past extension, and $X$ a category. Then $\iota \star \operatorname{id}_{X}: A \star X \hookrightarrow B \star X$ is $a$ past extension. | |
| Proof. We use the characterisation of past extensions with collages of profunctors, given in Remark 4. Suppose $t$ is induced by the profunctor $\mathrm{H}: \bar{A}^{\mathrm{op}} \times A \rightarrow$ Set. We define a profunctor $\tilde{\mathrm{H}}: \bar{A}^{\mathrm{op}} \times(A \star X) \rightarrow$ Set by | |
| $$ | |
| \tilde{\mathrm{H}}(x, y):= \begin{cases}\mathrm{H}(x, y) & \text { if } y \text { is an object of } A, \\ 1 & \text { if } y \text { is an object of } X,\end{cases} | |
| $$ | |
| with the only action of morphisms compatible with $\mathrm{H}$. Then the collage of $\tilde{\mathrm{H}}$ is isomorphic to $B \star X$, and the inclusion of $A \star X$ into the collage is isomorphic to $l \star \operatorname{id}_{X}$. | |
| Remark 7. It follows from functoriality of joins and Proposition 20 that $-\star \operatorname{id}_{X}$ determines a functor $\operatorname{Past}(A) \rightarrow \operatorname{Past}(A \star X)$ for each pair of categories $A, X$. | |
| Proposition 14 (Covariance over the domain of a natural transformation). Let $\mathrm{F}, \mathrm{G}: C \rightarrow D$ be two functors and let $\alpha: \mathrm{F} \Rightarrow \mathrm{G}$ be a natural transformation. For all $i \in\{0,1\}$, the assignment | |
| $$ | |
| x \mapsto \pi_{i}\left((D / G x) / \alpha_{x}\right) | |
| $$ | |
| extends to a functor $C \rightarrow$ Pos. Proof. Since $\vec{I}$ is isomorphic to $\mathbf{1} \star \mathbf{1}$, there is a functor | |
| $$ | |
| -\star \mathrm{id}_{1}: \operatorname{Past}(\mathbf{1}) \rightarrow \operatorname{Past}(\vec{I}) | |
| $$ | |
| as described in Remark 7, and we can take | |
| $$ | |
| \mathrm{K}_{0} \star \mathrm{id}_{1}, \quad \mathrm{~K}_{1} \star \mathrm{id}_{1} | |
| $$ | |
| for the morphisms we considered in the proof of Proposition 10, to get morphisms in $\operatorname{Past}(\vec{I})$. These can be pictured as follows: | |
|  | |
| These induce functors | |
| $$ | |
| \begin{aligned} | |
| & \Lambda . \operatorname{Ext}_{C} \vec{I}^{2}\left(\mathrm{~K}_{0} \star \mathrm{id}_{\mathbf{1}},-\right): C^{\vec{I}} \rightarrow \mathbf{C a t}^{\vec{I}} \\ | |
| & \Lambda . \operatorname{Ext}_{C} \vec{I}^{\prime}\left(\mathrm{K}_{1} \star \mathrm{id}_{\mathbf{1}},-\right): C^{\vec{I}} \rightarrow \mathbf{C a t}^{\vec{I}} | |
| \end{aligned} | |
| $$ | |
| according to the general functoriality pattern of Remark 6. We claim that, up to isomorphism of categories, these functors send an object of $C^{\vec{I}}$, that is, a morphism $f: x \rightarrow y$ in $C$, to the slice projection functors | |
| $$ | |
| \begin{aligned} | |
| & \text { dom: }(C / y) / f \rightarrow C / y, \\ | |
| & \text { dom: } \operatorname{Par}((C / y) / f) /\left(\operatorname{id}_{f}, \operatorname{id}_{f}\right) \rightarrow \operatorname{Par}((C / y) / f), | |
| \end{aligned} | |
| $$ | |
| hence their composites with the functor of Equation 1 act as | |
| $$ | |
| \begin{aligned} | |
| & (f: x \rightarrow y) \mapsto \pi_{0}((C / y) / f), \\ | |
| & (f: x \rightarrow y) \mapsto \pi_{1}((C / y) / f) . | |
| \end{aligned} | |
| $$ | |
| This can be verified as in the proof of Proposition 10 using the general fact that commutative diagrams of the form | |
|  | |
| are in natural bijection with commutative diagrams of the form | |
|  | |
| because the functor | |
| $$ | |
| \begin{aligned} | |
| -\star \mathbf{1}: \text { Cat } & \rightarrow 1 / \text { Cat } \\ | |
| A & \mapsto\left(\varnothing \star \mathrm{id}_{\mathbf{1}}: \mathbf{1} \rightarrow A \star \mathbf{1}\right) | |
| \end{aligned} | |
| $$ | |
| is left adjoint to the slicing functor $(x: \mathbf{1} \rightarrow C) \mapsto C / x$. | |
| Now, a natural transformation $\alpha: \mathrm{F} \Rightarrow \mathrm{G}$ between functors $\mathrm{F}, \mathrm{G}: C \rightarrow D$ can be seen as a functor | |
| $$ | |
| \alpha: C \rightarrow D^{\vec{I}} | |
| $$ | |
| sending $x$ to $\left(\alpha_{x}: \mathrm{F} x \rightarrow \mathrm{G} x\right)$, which post-composed with (7) and (8) defines functors $C \rightarrow$ Pos. acting on objects as | |
| $$ | |
| x \mapsto \pi_{i}\left((D / \mathrm{G} x) / \alpha_{x}\right), \quad i \in\{0,1\} | |
| $$ | |
| This completes the proof. | |
| \section{Qualifying compositionality} | |
| Proposition 15 (Laxity of the state functor). The state functor lifts to a lax monoidal functor from $(C, \otimes, I)$ to $($ Set,$\times,\{*\})$. | |
| Proof. We need to define a natural transformation and a morphism | |
| $$ | |
| \begin{gathered} | |
| \Phi: \operatorname{Hom}_{C}(I,-) \times \operatorname{Hom}_{C}(I,-) \Rightarrow \operatorname{Hom}_{C}(I,-\otimes-) \\ | |
| \varphi:\{*\} \rightarrow \operatorname{Hom}_{C}(I, I) | |
| \end{gathered} | |
| $$ | |
| Switching to components, we need to define functions | |
| $$ | |
| \Phi_{A, B}:\left\{I \stackrel{\psi_{A}}{\longrightarrow} A\right\} \times\left\{I \stackrel{\psi_{B}}{\longrightarrow} B\right\} \rightarrow\left\{I \stackrel{\psi_{A, B}}{\longrightarrow} A \otimes B\right\} | |
| $$ | |
| whereas $\varphi$ is just picking an element $I \stackrel{\phi_{I}}{\rightarrow} I$ of $\operatorname{Hom}_{C}(I, I)$. We define them by setting: | |
| $$ | |
| \begin{aligned} | |
| & \Phi_{A, B}\left(\psi_{A}, \psi_{B}\right)=\rho_{I}^{-1} \stackrel{\circ}{ }\left(\psi_{A} \otimes \psi_{B}\right) \\ | |
| & \varphi(*)=i d_{I} | |
| \end{aligned} | |
| $$ | |
| where $\rho$ is the right unitor of $C$, and its component at $I$ is $\rho: I \otimes I \rightarrow I$. | |
| Verifying that $\Phi$ is a natural transformation and that the coherence diagrams for $\Phi$ and $\varphi$ commute is a long, but simple exercise. | |
| Proposition 16 (Oplaxity of the state functor). Let $(C, \otimes, \mathbf{1})$ be a semicartesian category. Then the state functor lifts to an oplax monoidal functor from $(C, \otimes, \mathbf{1})$ to $(\mathbf{S e t}, \times,\{*\})$. | |
| Proof. If $\mathbf{1}$ is terminal, then for each object $A$ there is a unique morphism $A \stackrel{!_{A}}{\rightarrow} \mathbf{1}$. | |
| We need to define a natural transformation and a morphism: | |
| $$ | |
| \begin{aligned} | |
| & \Phi: \operatorname{Hom}_{C}(\mathbf{1},-\otimes-) \Rightarrow \operatorname{Hom}_{C}(\mathbf{1},-) \times \operatorname{Hom}_{C}(\mathbf{1},-) \\ | |
| & \varphi: \operatorname{Hom}_{C}(\mathbf{1}, \mathbf{1}) \rightarrow \mathbf{1}_{\text {Set }} | |
| \end{aligned} | |
| $$ | |
| Switching to components, we need to define functions | |
| $$ | |
| \Phi_{A, B}:\left\{\mathbf{1} \stackrel{\psi_{A, B}}{\longrightarrow} A \otimes B\right\} \rightarrow\left\{\mathbf{1} \stackrel{\psi_{A}}{\longrightarrow} A\right\} \times\left\{\mathbf{1} \stackrel{\psi_{B}}{\longrightarrow} B\right\} | |
| $$ | |
| Whereas $\varphi$ is just a function $\left\{\stackrel{\phi_{1}}{\longrightarrow} \mathbf{1}\right\} \rightarrow\{*\}$, which is uniquely determined since $\{*\}$ is terminal in Set. We define $\Phi_{A, B}$ by letting | |
|  | |
| As in the previous proposition, verifying that all the required diagrams commute is a straightforward exercise. | |
| Proposition 17 (Strongness of the state functor). If $(C, \times, \mathbf{1})$ is cartesian, then the state functor is strong monoidal. | |
| Proof. The result follows from the fact that $\operatorname{Hom}_{C}(\mathbf{1},-)$ preserves limits, which by definition gives: | |
| $$ | |
| \begin{gathered} | |
| \operatorname{Hom}_{C}(\mathbf{1}, A \times B) \simeq \operatorname{Hom}_{C}(\mathbf{1}, A) \times \operatorname{Hom}_{C}(\mathbf{1}, B) \\ | |
| \operatorname{Hom}_{C}(\mathbf{1}, \mathbf{1}) \simeq\{*\} | |
| \end{gathered} | |
| $$ | |
| naturally in $A$ and $B$. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment