Todd Trimble
digraph stuff



The following is written at the request of Victor Porton, and is an extremely nuts-and-bolts description of the cartesian closed structure of the category Dig\mathbf{Dig}, whose objects are sets VV equipped with a binary relation EV×VE \subseteq V \times V and whose morphisms VWV \to W preserve the assigned relations.

From a high-level point of view, Dig\mathbf{Dig} is equivalent to the category of ¬¬\neg\neg-separated presheaves on the presheaf topos Gph\mathbf{Gph} of directed graphs. It is well-known that the (full) inclusion of separated presheaves (for a topology on a presheaf category) has a left adjoint that preserves finite products, and it follows that the separated presheaves forms an exponential ideal within the ambient presheaf topos, and thus in particular is cartesian closed. (Indeed, much more is true: not only is the category of separated presheaves cartesian closed, it is a quasitopos, hence it is locally cartesian closed as well.) As a special case, the cartesian closed structure of Dig\mathbf{Dig} is inherited from the cartesian closed structure of the ambient category Gph\mathbf{Gph}.

Our plan is to descend from the general to the particular. First we give a general description of the cartesian closed structure on presheaf categories, but in very elementary nuts-and-bolts fashion. (That is, we bypass the more conceptual descriptions involving presheaves as colimits of representable functors, the Yoneda lemma, etc. – in other words, we just unwind the definitions, which is straightforward but less than enlightening.) Then we apply this directly to the special case Gph\mathbf{Gph}. Then, we specialize further to the subcategory Dig\mathbf{Dig} and examine the cartesian closed structure directly in this case.

Possibly all this will eventually be extended to “funcoids” and “reloids”.

The cartesian closed category of directed graphs

First we describe the exponential or internal hom in the cartesian closed category of directed graphs (E,V,s:EV,t:EV)(E, V, s: E \to V, t: E \to V).

Consider the category CC with objects and non-identity morphisms as follows:

0ba1.0 \stackrel{\overset{a}{\to}}{\underset{b}{\to}} 1.

The category of directed graphs is equivalent to the category of presheaves F:C opSetF: C^{op} \to Set. Given FF, the set of vertices is V=F(0)V = F(0), the set of edges is E=F(1)E = F(1), the source function is s=F(a):F(1)F(0)s = F(a): F(1) \to F(0), and the target function is t=F(b):F(1)F(0)t = F(b): F(1) \to F(0).

Cartesian closed structure on presheaf toposes

Consider any small category CC. If F,G:C opSetF, G: C^{op} \to Set are presheaves on CC, their exponential G FG^F is (by abstract nonsense) given by the formula

(G F)(U)=Nat(C(,U)×F,G)(G^F)(U) = Nat(C(-, U) \times F, G)

where for an object UU of CC, we let C(,U)C(-, U) denote the hom-functor hom C(,U):C opSet\hom_C(-, U): C^{op} \to Set, and NatNat a set of natural transformations. (Note: if α:XY\alpha: X \to Y is a natural transformation, we denote its component at an object UU by α(U)\alpha (U).) Given a morphism f:VUf: V \to U of CC, the map G F(f):G F(U)G F(V)G^F(f): G^F(U) \to G^F(V) takes a natural transformation α:C(,U)×FG\alpha: C(-, U) \times F \to G to the composite transformation

C(,V)×FC(,f)×1 FC(,U)×FαG.C(-, V) \times F \stackrel{C(-, f) \times 1_F}{\to} C(-, U) \times F \stackrel{\alpha}{\to} G.

The evaluation transformation ϵ F,G:G F×FG\epsilon_{F, G}: G^F \times F \to G is the one whose component at an object UU is the map G F(U)×F(U)G(U)G^F(U) \times F(U) \to G(U) which takes a pair (α:C(,U)×FG,xF(U))(\alpha: C(-, U) \times F \to G, x \in F(U)) to the element α(U)(1 U,x)G(U)\alpha(U)(1_U, x) \in G(U).

Suppose given a natural transformation θ:H×FG\theta: H \times F \to G. We define the exponential transpose θ˜:HG F\tilde{\theta}: H \to G^F to be the transformation whose component at UU is the map that takes an element yH(U)y \in H(U) to the transformation θ˜y:C(,U)×FG\tilde{\theta}\cdot y: C(-, U) \times F \to G whose component at an object VV is defined to be the function

C(V,U)×F(V)G(V)C(V, U) \times F(V) \to G(V)

that sends a pair (f:VU,xF(V))(f: V \to U, x \in F(V)) to θ(V)(H(f)(y),x)\theta (V)(H(f)(y), x).

These definitions specify the cartesian closed structure of the presheaf category. The cartesian closure means that the function

Nat(H×F,G)Nat(H,G F):θθ˜Nat(H \times F, G) \to Nat(H, G^F): \theta \mapsto \tilde{\theta}

(natural in H,F,GH, F, G) is inverse to the function Nat(H,G F)Nat(H×F,G)Nat(H, G^F) \to Nat(H \times F, G) that maps a transformation η:HG F\eta: H \to G^F to the composite

H×Fη×1 FG F×Fϵ F,GG.H \times F \stackrel{\eta \times 1_F}{\to} G^F \times F \stackrel{\epsilon_{F, G}}{\to} G.

The verification that these two functions are mutually inverse is given in the proofs of the following two propositions.


Given θ:H×FG\theta: H \times F \to G, the composite given by

H×Fθ˜×1 FG F×Fϵ F,GGH \times F \stackrel{\tilde{\theta} \times 1_F}{\to} G^F \times F \stackrel{\epsilon_{F, G}}{\to} G

is θ\theta again.


Let UU be any object of the category CC, and let (y,x)H(U)×F(U)(y, x) \in H(U) \times F(U). We must verify that

ϵ F,G(U)(θ˜y,x)=θ(U)(y,x).\epsilon_{F, G}(U)(\tilde{\theta}\cdot y, x) = \theta (U)(y, x).

By definition of ϵ\epsilon, the left-hand side is

(θ˜y)(U)(1 U,x)(\tilde{\theta}\cdot y)(U)(1_U, x)

which by definition of θ˜y\tilde{\theta}\cdot y is θ(U)(H(1 U)(y),x)=θ(U)(1 H(U)(y),x)=θ(U)(y,x)\theta (U)(H(1_U)(y), x) = \theta (U)(1_{H(U)}(y), x) = \theta (U)(y, x), as required.


Given η:HG F\eta: H \to G^F, the exponential transpose of the composite

H×Fη×1 FG F×Fϵ F,GGH \times F \stackrel{\eta \times 1_F}{\to} G^F \times F \stackrel{\epsilon_{F, G}}{\to} G

is η\eta again.


Let UU be an object of the category CC. We must verify that the exponential transpose θ˜\tilde{\theta} of the transformation θ:H×FG\theta: H \times F \to G, where θ(U)\theta (U) takes (y,x)H(U)×F(U)(y, x) \in H(U) \times F(U) to

ϵ F,G(η(y),x)(η(U)(y))(U)(1 U,x),\epsilon_{F, G}(\eta (y), x) \coloneqq (\eta (U)(y))(U)(1_U, x),

is η\eta. In other words, that for any object UU and element yH(U)y \in H(U), we have θ˜(U)(y)=η(U)(y)\tilde{\theta}(U)(y) = \eta (U)(y). In other words, that for any object VV, any morphism f:VUf: V \to U, and any element xF(V)x \in F(V), that

[θ˜(U)(y)](V)(f,x)=[η(U)(y)](V)(f,x).[\tilde{\theta}(U)(y)](V)(f, x) = [\eta (U)(y)](V)(f, x).

By definition, θ˜(U)(y)\tilde{\theta}(U)(y) is the transformation C(,U)×FGC(-, U) \times F \to G which takes an object VV to the function (V,U)×F(V)G(V)(V, U) \times F(V) \to G(V) that sends a pair (f:VU,xF(V))(f: V \to U, x \in F(V)) to

θ(V)(H(f)(y),x)[(η(V))(H(f)(y))](V)(1 V,x).\theta (V)(H(f)(y), x) \coloneqq [(\eta (V))(H(f)(y))](V)(1_V, x).

Here the expression η(V)(H(f)(y))\eta (V)(H(f)(y)) on the right is the result of applying to yy the composite η(V)H(f)\eta (V) \circ H(f) in the naturality diagram

H(U) η(U) Nat(C(,U)×F,G) H(f) Nat(C(,f)×1 F,1 G) H(V) η(V) Nat(C(,V)×F,G)\array{ H(U) & \stackrel{\eta (U)}{\to} & Nat(C(-, U) \times F, G) \\ \mathllap{H(f)} \downarrow & & \downarrow \mathrlap{Nat(C(-, f) \times 1_F, 1_G)} \\ H(V) & \underset{\eta(V)}{\to} & Nat(C(-, V) \times F, G) }

and so it is the same result as applying to yy the composite Nat(C(,f)×1 F,1 G)η(U)Nat(C(-, f) \times 1_F, 1_G) \circ \eta (U). This result is (by definition) the composite transformation

C(,V)×FC(,f)×1 FC(,U)×Fη(U)(y)G.C(-, V) \times F \stackrel{C(-, f) \times 1_F}{\to} C(-, U) \times F \stackrel{\eta (U)(y)}{\to} G.

Putting all this together, we have the equations

[θ˜(U)(y)](V)(f,x) = [(η(V))(H(f)(y))](V)(1 V,x) = [Nat(C(,f)×1 F,1 G)(η(U)(y))](V)(1 V,x) = [η(U)(y)(C(,f)×1 F)](V)(1 V,x) = [(η(U)(y))(V)(C(V,f)×1 F(V))](1 V,x) = [(η(U)(y))(V)(f,x)\array{ [\tilde{\theta}(U)(y)](V)(f, x) & = & [(\eta (V))(H(f)(y))](V)(1_V, x) \\ & = & [Nat(C(-, f) \times 1_F, 1_G)(\eta (U)(y))](V)(1_V, x) \\ & = & [\eta (U)(y) \circ (C(-, f) \times 1_F)](V)(1_V, x) \\ & = & [(\eta (U)(y))(V) \circ (C(V, f) \times 1_{F(V)})](1_V, x) \\ & = & [(\eta (U)(y))(V)(f, x) }

as was to be shown.

Cartesian closed structure on directed graphs

Now we consider apply the previous section to the special case C=0ba1C = 0 \stackrel{\overset{a}{\to}}{\underset{b}{\to}} 1, where the presheaves may be identified with directed graphs.

Taking U=0U = 0, and letting F,G:C opSetF, G: C^{op} \to Set be directed graphs, the set of vertices G F(0)G^F(0) is the set of natural transformations

C(,0)×FGC(-, 0) \times F \to G

where we note that C(1,0)C(1, 0) is empty and C(0,0)C(0, 0) is a singleton, and so this set is naturally identified with the set of functions

F(0)G(0)F(0) \to G(0)

between the sets of vertices of FF and GG.

The set of edges G F(1)G^F(1) is the set of natural transformations

C(,1)×FG.C(-, 1) \times F \to G.

Here C(1,1)C(1, 1) is a singleton and C(0,1)={a,b}C(0, 1) = \{a, b\}, so the data of an edge of G FG^F amounts to a pair of functions

e 1:F(1)G(1),e 0:{a,b}×F(0)G(0)e_1: F(1) \to G(1), \qquad e_0: \{a, b\} \times F(0) \to G(0)

or if you like, a triple of functions e 1,e 0,a,e 0,be_1, e_{0, a}, e_{0, b}, subject to a naturality condition that amounts to asserting commutativity of the diagrams

F(1) e 1 G(1) F(1) e 1 G(1) source source target target F(0) e 0,a G(0) F(0) e 0,b G(0)\array{ F(1) & \stackrel{e_1}{\to} & G(1) & & & & F(1) & \stackrel{e_1}{\to} & G(1) \\ _\mathllap{source} \downarrow & & \downarrow_\mathrlap{source} & & & & _\mathllap{target} \downarrow & & \downarrow_\mathrlap{target} \\ F(0) & \underset{e_{0, a}}{\to} & G(0) & & & & F(0) & \underset{e_{0, b}}{\to} & G(0) }

It is straightforward to check (following the definitions of the preceding section) that the source of an edge (e 1,e 0,a,e 0,b)(e_1, e_{0, a}, e_{0, b}) of G FG^F is the vertex e 0,a:F(0)G(0)e_{0, a}: F(0) \to G(0) of G FG^F, and that the target of (e 1,e 0,a,e 0,b)(e_1, e_{0, a}, e_{0, b}) is the vertex e 0,b:F(0)G(0)e_{0, b}: F(0) \to G(0).

The evaluation map G F×FGG^F \times F \to G consists of a vertex function G F(0)×F(0)G(0)G^F(0) \times F(0) \to G(0) and an edge function G F(1)×F(1)G(1)G^F(1) \times F(1) \to G(1). The vertex function is, according to the above, a function G(0) F(0)×F(0)G(0)G(0)^{F(0)} \times F(0) \to G(0) and is just ordinary evaluation, mapping a pair (f:F(0)G(0),xF(0))(f: F(0) \to G(0), x \in F(0)) to f(x)G(0)f(x) \in G(0). The edge function maps a pair ((e 1,e 0,a,e 0,b)G F(1);eF(1))((e_1, e_{0, a}, e_{0, b}) \in G^F(1); e \in F(1)) to e 1(e)G(1)e_1(e) \in G(1).

Given a map θ:H×FG\theta: H \times F \to G of directed graphs, consisting of a vertex map θ(0):H(0)×F(0)G(0)\theta(0): H(0) \times F(0) \to G(0) and an edge map θ(1):H(1)×F(1)G(1)\theta(1): H(1) \times F(1) \to G(1), the exponential transpose θ˜\tilde{\theta} is described as follows. The vertex map θ˜(0):H(0)G F(0)\tilde{\theta}(0): H(0) \to G^F(0) is just the exponential transpose θ(0)˜:H(0)G(0) F(0)\widetilde{\theta(0)}: H(0) \to G(0)^{F(0)} in the category of sets, taking an vertex vH(0)v \in H(0) to θ(0)(v,):F(0)G(0)\theta(0)(v, -): F(0) \to G(0). The edge map θ˜(1):H(1)G F(1)\tilde{\theta}(1): H(1) \to G^F(1) takes an edge eH(1)e \in H(1) to a triple

(F(1)e 1G(1),F(0)e 0,aG(0),F(0)e 0,bG(0))(F(1) \stackrel{e_1}{\to} G(1), F(0) \stackrel{e_{0, a}}{\to} G(0), F(0) \stackrel{e_{0, b}}{\to} G(0))

where, letting s(e)s(e) and t(e)t(e) be the source and target of ee, we take e 1θ(1)(e,)e_1 \coloneqq \theta(1)(e, -) and e 0,aθ(0)(s(e),)e_{0, a} \coloneqq \theta(0)(s(e), -) and e 0,bθ(0)(t(e),)e_{0, b} \coloneqq \theta(0)(t(e), -).

All of these constructions are just special cases of the general considerations in the previous section, and so these constructions indeed define the cartesian closed structure on the category of directed graphs.

Cartesian closed structure on Dig\mathbf{Dig}

Now we specialize even further to the case where we consider only directed graphs (V,E,i:EV×V)(V, E, i: E \to V \times V) where ii is a monomorphism or injective function. The full subcategory consisting of such graphs and graph morphisms between them is equivalent to Dig\mathbf{Dig}, the category of sets VV equipped with an endorelation EE. (Briefly, any such directed graph is isomorphic to one where we take ii to be a subset inclusion EV×VE \subseteq V \times V, just by replacing a monomorphism by its image.)

In this case, we may verify directly that if F=(V,E,i)F = (V, E, i) and G=(V,E,i)G = (V', E', i') are directed graphs for which the source-target pairings ii, ii' are injective, then the source-target pairing for G FG^F, mapping a triple (e 1,e 0,a,e 0,b)(e_1, e_{0, a}, e_{0, b}) to the pair (e 0,a,e 0,b)(e_{0, a}, e_{0, b}), is also injective. In other words, given (e 0,a,e 0,b)(e_{0, a}, e_{0, b}) there is at most one function e 1:F(1)G(1)e_1: F(1) \to G(1) for which

s Ge 1=e 0,as F,t Ge 1=e 0,bt F.s_G \circ e_1 = e_{0, a} \circ s_F, \qquad t_G \circ e_1 = e_{0, b} \circ t_F.

But this is clear: injectivity of i=s G,t G:G(1)G(0)×G(0)i' = \langle s_G, t_G \rangle: G(1) \to G(0) \times G(0) means there is at most e 1e_1 such that

ie 1=e 0,as F,e 0,bt F.i' \circ e_1 = \langle e_{0, a} \circ s_F, e_{0, b} \circ t_F \rangle.

This shows that Dig\mathbf{Dig} is closed with respect to the cartesian closed structure on GphGph.

Recasting all this in the language of sets equipped with endorelations: if (X, X)(X, \sim_X) and (Y, Y)(Y, \sim_Y) are such structures, then their internal hom is the set Y XY^X of functions f:XYf: X \to Y, where there is an edge or relation f Y Xgf \sim_{Y^X} g if there is an edge f(x) Yg(x)f(x) \sim_Y g(x') whenever there is an edge x Xxx \sim_X x'. (Here ff plays the role of e 0,ae_{0, a} in the previous paragraph, and gg plays the role of e 0,be_{0, b}.)

Created on November 24, 2013 at 10:58:26 by Todd Trimble