nLab graph of a functor

Contents

Contents

Idea

In as far as the notion of functor generalizes that of function and that of profunctor generalizes that of relation, the notion of graph of a (pro)functor generalizes that of graph of a function.

Just as the graph of a function f:XYf : X \to Y, or more generally that of a relation RX×YR \subset X \times Y for X,YSet=0CatX,Y \in Set = 0 Cat is nothing but the category of elements of the corresponding characteristic function χ R:X×Y(1)Cat={0,1}\chi_R : X \times Y \to (-1)Cat = \{0,1\}, so the graph of a functor F:CDF\colon C \to D, or more generally that of a profunctor H:C op×D0Cat=SetH : C^{op} \times D \to 0 Cat = Set, is nothing but its category of elements, a.k.a. Grothendieck construction.

However, there are a number of different ways to construct such a category of elements, depending on the variance of morphisms in CC and DD that we include in it. A one-variable functor CSetC\to Set has two categories of elements, one with a projection to CC (which is a discrete opfibration) and one with a projection to C opC^{op} (which is a discrete fibration). Similarly, a two-variable functor such as H:C op×DSetH : C^{op}\times D\to Set has four categories of elements; thus a profunctor has four different “graphs”. In addition, there are two ways to make a functor into a profunctor, so a functor actually has eight graphs.

Definition

Graphs of a profunctor

Let H:C opDH:C^{op}\to D be a profunctor; it has the following four graphs. In each case, the objects are triples (cC,dD,xH(c,d)(c\in C, d\in D, x\in H(c,d), but we can take the morphisms (c,d,x)(c,d,x)(c,d,x) \to (c',d',x') to be any of the following:

  • Pairs (f:cc,g:dd)(f:c\to c', g:d\to d') such that H(1,g)(x)=H(f,1)(x)H(1,g)(x) = H(f,1)(x'). This graph comes with a projection to C×DC\times D, which is a two-sided discrete fibration that is contravariant over CC and covariant over DD.

  • Pairs (f:cc,g:dd)(f:c'\to c, g:d\to d') such that H(f,g)(x)=xH(f,g)(x) = x'. This graph comes with a projection to C op×DC^{op}\times D, which is a discrete opfibration. It is also the comma category (*H)(*\downarrow H):

    Graph(H) * C op×D H Set \array{ Graph(H) &\to& {*} \\ \downarrow & \swArrow & \downarrow \\ C^{op} \times D &\stackrel{H}{\to}& Set }
  • Pairs (f:cc,g:dd)(f:c\to c', g:d'\to d) such that H(f,g)(x)=xH(f,g)(x') = x. This graph comes with a projection to C×D opC\times D^{op}, which is a discrete fibration; it is the opposite of the previous category.

  • Pairs (f:cc,g:dd)(f:c'\to c, g:d'\to d) such that H(1,g)(x)=H(f,1)(x)H(1,g)(x') = H(f,1)(x). This graph comes with a projection to C op×D opC^{op}\times D^{op}, which is a two-sided discrete fibration that is covariant over C opC^{op} and contravariant over D opD^{op}; it is the opposite of the first graph.

If the profunctor is the hom profunctor? of a category CC, then the first graph is the arrow category of CC and the second graph is the twisted arrow category of CC.

Graphs of a functor

Let F:CDF:C\to D be a functor, and let F :C op×DSetF^\bullet : C^{op}\times D \to Set and F F_\bullet be the corresponding representable profunctors:

F (c,d)=D(Fc,d)F (d,c)=D(d,Fc).F^\bullet(c,d) = D(F c, d) \qquad F_\bullet(d,c) = D(d,Fc).

Then the graphs of F F^\bullet yield four graphs of FF, all of whose objects are triples (cC,dD,ϕ:Fcd)(c\in C, d\in D, \phi:F c \to d), and whose morphisms (c,d,ϕ)(c,d,ϕ)(c,d,\phi) \to (c',d',\phi') are:

  • Pairs (f:cc,g:dd)(f:c\to c', g:d\to d') such that ϕFf=gϕ\phi' \circ F f = g \circ \phi. This graph comes with a projection to C×DC\times D, which is a two-sided discrete fibration that is contravariant over CC and covariant over DD. It is also the comma category (FId D)(F\downarrow Id_D):

    Graph(F) C F D Id D D \array{ Graph(F) &\to& C \\ \downarrow & \swArrow & \downarrow^F \\ D &\stackrel{Id_D}{\to}& D }
  • Pairs (f:cc,g:dd)(f:c'\to c, g:d\to d') such that ϕ=gϕFf\phi' = g \circ \phi \circ F f. This graph comes with a projection to C op×DC^{op}\times D, which is a discrete opfibration; it is the comma category (*F )(* \downarrow F^\bullet).

  • Pairs (f:cc,g:dd)(f:c\to c', g:d'\to d) such that ϕ=gϕFf\phi = g \circ \phi' \circ F f. This graph comes with a projection to C×D opC\times D^{op}, which is a discrete fibration; it is the opposite of the preceeding graph.

  • Pairs (f:cc,g:dd)(f:c'\to c, g:d'\to d) such that ϕFf=gϕ\phi \circ F f = g \circ \phi'. This graph comes with a projection to C op×D opC^{op}\times D^{op}, which is a two-sided discrete fibration that is covariant over C opC^{op} and contravariant over D opD^{op}; it is the opposite of the first graph of F F^\bullet.

Similarly, the graphs of F F_\bullet yield four graphs of FF, all of whose objects are triples (cC,dD,ψ:dFc)(c\in C, d\in D, \psi : d \to F c), and whose morphisms (c,d,ψ)(c,d,ψ)(c,d,\psi) \to (c',d',\psi') are:

  • Pairs (f:cc,g:dd)(f:c\to c', g:d\to d') such that Ffψ=ψgF f \circ \psi = \psi\circ g. This graph comes with a projection to C×DC\times D, which is a two-sided discrete fibration that is covariant over C opC^{op} and contravariant over D opD^{op}. It is also the comma category (Id DF)(Id_D \downarrow F):

    Graph(F) D Id D C F D \array{ Graph(F) &\to& D \\ \downarrow & \swArrow & \downarrow^{Id_D} \\ C &\stackrel{F}{\to}& D }
  • Pairs (f:cc,g:dd)(f:c'\to c, g:d\to d') such that ψ=Ffψg\psi' = F f \circ \psi \circ g. This graph comes with a projection to C op×DC^{op}\times D, which is a discrete opfibration; it is the comma category (*F )(* \downarrow F^\bullet).

  • Pairs (f:cc,g:dd)(f:c\to c', g:d'\to d) such that ψ=Ffψg\psi = F f \circ \psi' \circ g. This graph comes with a projection to C×D opC\times D^{op}, which is a discrete fibration; it is the opposite of the preceeding graph.

  • Pairs (f:cc,g:dd)(f:c'\to c, g:d'\to d) such that ψg=Ffψ\psi \circ g = F f \circ \psi'. This graph comes with a projection to C op×D opC^{op}\times D^{op}, which is a two-sided discrete fibration that is contravariant over CC and covariant over DD; it is the opposite of the first graph of F F_\bullet.

For higher categories

In general

For nn \leq \infty, let (n1)Cat(n-1) Cat and nCatn Cat be a realization of the notions of nn-category of (n1)(n-1)-categories and of the (n+1)(n+1)-category of nn-categories, respectively, such that standard constructions of category theory work, in particular a version of the Yoneda lemma. See higher category theory.

Then with C,DnCatC,D \in n Cat let f:CDf : C \to D be a (nn-)functor. By the general logic of profunctors this defines nn-profunctors

F :C op×DF op×IdD op×DD(,)(n1)Cat F^\bullet : C^{op} \times D \stackrel{F^{op} \times Id}{\to} D^{op} \times D \stackrel{D(-,-)}{\to} (n-1) Cat
F :C×D opF×IdD op×DD(,)(n1)Cat F_\bullet : C \times D^{op} \stackrel{F \times Id}{\to} D^{op} \times D \stackrel{D(-,-)}{\to} (n-1) Cat

We can then consider analogues of all eight kinds of graphs. For instance, the second kind of graph of FF is the fibration Graph(f)C op×DGraph(f) \to C^{op} \times D classified by F F^\bullet.

For (,1)(\infty,1)-categories

In the context of (,1)(\infty,1)-category theory, this graph may be taken to be the fibration classified by χ f:C×D op(,0)\chi_f : C \times D^{op} \to (\infty,0) as described at universal fibration of (∞,1)-categories.

For (0,0)-categories (sets)

To reproduce the ordinary notion of graph of a function let (n,r)=(0,0)(n,r) = (0,0). then (n,r)(n,r)-categories X,YX,Y are just sets and a functor f:XYf : X \to Y is just a function between sets. Moreover, the category of (n1,r)=(1,0)(n-1,r) = (-1,0)-categories is the set {0,1}\{0,1\} of truth values, as described at (-1)-category. The profunctor corresponding to f:XYf : X \to Y is therefore the characteristic function

χ f:X×Y{0,1} \chi_f : X \times Y \to \{0,1\}

that maps

χ f(x,y)={1 iff(x)=y 0 otherwise. \chi_f(x,y) = \left\lbrace \array{ 1 & if f(x) = y \\ 0 & otherwise } \right. \,.

(Notice that in this case X op=XX^{op} = X.)

The 2-pullback of *=1{0,1}{*} = {1} \to \{0,1\} along χ f\chi_f is just the ordinary pullback

Graph(f) * X×Y χ f {0,1} \array{ Graph(f) &\to& {*} \\ \downarrow && \downarrow \\ X \times Y &\stackrel{\chi_f}{\to}& \{0,1\} }

which identifies Graph(f)X×YGraph(f) \hookrightarrow X \times Y with the subset of pairs (x,y)(x,y) for which f(x)=yf(x) = y. This is the ordinary notion of graph of a function.

Last revised on December 2, 2022 at 12:50:01. See the history of this page for a list of all contributions to it.