cograph of a functor


The notion of cograph of a functor is dual to that of graph of a functor: for f:CDf : C \to D a functor between n-categories is the fibration classified by the profunctor correspondence χ f:C op×D(n1)Cat\chi_f : C^{op}\times D \to (n-1)Cat. But ff also determines a morphism f¯:InCat\bar f : I \to n Cat from the interval category II. The cograph of ff is the fibration classified by f¯\bar f.

Recall that the graph of a function f:ABf: A \to B is the subset determined by the monomorphism 1,f:AA×B\langle 1, f \rangle: A \to A \times B. This makes sense in any category with products. Under one definition, the notion of cograph of a function f:ABf: A \to B is the categorically dual notion: it is the quotient determined by the epimorphism (f,1):ABB(f, 1): A \sqcup B \to B.

A more vivid presentation of cograph is given by the pictures we draw of functions f:ABf: A \to B: as directed graphs (in the graph-theoretic sense!) whose vertices are elements in ABA \sqcup B, with an edge drawn from aa to f(a)f(a) for each aa in AA. This can also be conceived as a poset P fP_f with underlying set ABA \sqcup B, in which af(a)a \leq f(a) and all other instances of \leq are the reflexive ones. The connected components function (P f) 0π 0(P f)(P_f)_0 \to \pi_0(P_f) is then the cograph in the sense given above.

In this article we give a definition of cograph which generalizes this poset picture of cograph of a function, and which applies to any functor between nn-categories.


Cographs of functors between 0-categories

In the case that C,DC, D are 0-categories, i.e. sets, a functor f:CDf : C \to D is just a function between sets. The cograph 2-pullback

cograph(f) * I f¯ Set \array{ cograph(f) &\to& {*} \\ \downarrow && \downarrow \\ I &\stackrel{\bar f}{\to}& Set }

is computed by the ordinary pullback

cograph(f) Set * I f¯ Set \array{ cograph(f) &\to& Set_{*} \\ \downarrow && \downarrow \\ I &\stackrel{\bar f}{\to}& Set }

and identifies cograph(f)cograph(f) with the category of elements of f¯\bar f, as described there: the objects of cograph(f)cograph(f) are the disjoint union of CC and DD: Obj(cograph(f))=CDObj(cograph(f)) = C \coprod D and the nontrivial morphisms are of the form xyx \to y whenever xCx \in C, yDy \in D and f(x)=yf(x) = y.

What Bill Lawvere called the cograph of a function is the connected components π 0(Cograph(f))\pi_0(Cograph(f)) of this category.

Cographs of functors between 1-categories

For f:CDf : C \to D an ordinary functor, cograph(f)cograph(f) is the category with Obj(cograph(f))=Obj(C)Obj(D)Obj(cograph(f)) = Obj(C) \coprod Obj(D) and with

Hom cograph(f)(x,y)={Hom C(x,y) ifx,yC Hom D(x,y) ifx,yD Hom D(f(x),y) ifxC,yD ifxD,yC Hom_{cograph(f)}(x,y) = \left\{ \array{ Hom_C(x,y) & if\; x,y \in C \\ Hom_D(x,y) & if\; x,y \in D \\ Hom_D(f(x),y) & if\; x \in C ,y \in D \\ \emptyset & if\; x \in D ,y \in C } \right.

with composition defined as induced from CC, from DD, and from the action of ff. This is a special case of the cograph of a profunctor, specialized to the representable profunctor D(f,)D(f-,-).

This cograph is denoted C fDC \star^f D in section 2.3.1 (_Correspondences_) in

where it is understood as a generalization of the join of simplicial sets and where it serves as a motivation for the study of cographs of functors between (∞,1)-categories discussed below.

Adjoint functors in terms of cographs

As emphasized in the beginning of section 5.2 there, cographs of functors may be used to characterize adjoint functors. This is just one way of stating the characterization of adjoints in terms of profunctors (which in turn makes sense in any 2-category equipped with proarrows).


Two functors L:CDL : C \to D and R:DCR : D \to C are adjoint functors precisely if cograph(L)cograph(L) and cograph(R op) opcograph(R^{op})^{op} are isomorphic under CC and DD:

(LR)(cograph(L)cograph(R op) op) (L \dashv R) \Leftrightarrow (cograph(L) \cong cograph(R^{op})^{op})

where the isomorphism is in the co-slice category (CD)/Cat(C\sqcup D)/Cat.

More precisely, there is a bijection between adjunctions LRL\dashv R and isomorphisms as above.


The category cograph(L)cograph(L) is the category with Obj(cograph(L))=Obj(C)Obj(D)Obj(cograph(L)) = Obj(C) \coprod Obj(D) and with

Hom cograph(L)(x,y)={Hom C(x,y) ifx,yC Hom D(x,y) ifx,yD Hom D(L(x),y) ifxC,yD ifxD,yC Hom_{cograph(L)}(x,y) = \left\{ \array{ Hom_C(x,y) & if\; x,y \in C \\ Hom_D(x,y) & if\; x,y \in D \\ Hom_D(L(x),y) & if\; x \in C ,y \in D \\ \emptyset & if\; x \in D ,y \in C } \right.

(This set is also called the set of heteromorphisms between objects in CC and DD.)

The category cograph(R op) opcograph(R^{op})^{op} accordingly is the category with Obj(cograph(R))=Obj(C)Obj(D)Obj(cograph(R)) = Obj(C) \coprod Obj(D) and with

Hom cograph(R op) op(x,y)={Hom C(x,y) ifx,yC Hom D(x,y) ifx,yD Hom C(x,R(y)) ifxC,yD ifxD,yC Hom_{cograph(R^{op})^{op}}(x,y) = \left\{ \array{ Hom_C(x,y) & if x,y \in C \\ Hom_D(x,y) & if x,y \in D \\ Hom_C(x,R(y)) & if x \in C ,y \in D \\ \emptyset & if x \in D ,y \in C } \right.

Evidently these categories are isomorphic under CC and DD precisely if for all xC,yDx \in C, y \in D we have

Hom D(L(x),y)Hom C(x,R(y)). Hom_D(L(x),y) \cong Hom_C(x,R(y)) \,.

naturally in xx and yy. It is natural because the isomorphism is an isomorphism of categories, and the functoriality of Hom D(L(),)Hom_D(L(-),-) and Hom C(,R())Hom_C(-,R(-)) is encoded by composition in the cograph. Of course, such a natural isomorphism is precisely the structure of an adjunction LRL\dashv R.

Note also that just as cograph(L)cograph(L) is the cograph of the profunctor D(L,)D(L-,-), also cograph(R op) opcograph(R^{op})^{op} is the cograph of the profunctor C(,R)C(-,R-). Thus, this theorem can be viewed as one way of stating the characterization of adjunctions in terms of homsets, as can be formulated in terms of profunctors in any 2-category equipped with proarrows.

Cographs of functors between (,1)(\infty,1)-categories

In the context of (∞,1)-category theory there is a good theory of Cartesian fibrations XSX \to S and of their classification by (∞,1)-functors S op(,1)CatS^{op} \to (\infty,1)Cat to the (∞,1)-category of (∞,1)-categories as described at universal fibration of (∞,1)-categories.

Accordingly, the above notion of cograph of a functor has a direct generalization to (∞,1)-functors:


For f:CDf : C \to D an (∞,1)-functor, identified with a morphism

f¯:I(,1)Cat \bar f : I \to (\infty,1)Cat

in the (∞,1)-category of (∞,1)-categories, it cograph is the Cartesian fibration cograph(f)Icograph(f) \to I classified by it. In terms of the universal fibration of (∞,1)-categories this is the homotopy pullback

cograph(f) S op I f¯ (,1)Cat. \array{ cograph(f) &\to& S^{op} \\ \downarrow && \downarrow \\ I &\stackrel{\bar f}{\to}& (\infty,1)Cat } \,.

As for every Cartesian fibration the functor f:CDf : C \to D is determined uniquely up to equivalence by its cograph. In general, obtaining the classifying (,1)(\infty,1)-functor from a given Cartesian fibration may be difficult. In the special case of cographs as Cartesian fibrations over the simple interval category it is easier. This is discussed in the following:


The notion of cographs of (,1)(\infty,1)-functors and the theory of how to re-obtain (,1)(\infty,1)-functors from their cographs is the content of section 5.2.1, Correspondences and associated functors, of

Revised on November 28, 2014 08:30:09 by Urs Schreiber (