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 $\mathbf{Dig}$, whose objects are sets $V$ equipped with a binary relation $E \subseteq V \times V$ and whose morphisms $V \to W$ preserve the assigned relations.

From a high-level point of view, $\mathbf{Dig}$ is equivalent to the category of $\neg\neg$-separated presheaves on the presheaf topos $\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 $\mathbf{Dig}$ is inherited from the cartesian closed structure of the ambient category $\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 $\mathbf{Gph}$. Then, we specialize further to the subcategory $\mathbf{Dig}$ and examine the cartesian closed structure directly in this case.

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

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

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

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

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

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

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

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

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

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

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

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

that sends a pair $(f: V \to U, x \in F(V))$ to $\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 \times F, G) \to Nat(H, G^F): \theta \mapsto \tilde{\theta}$

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

$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 $\theta: H \times F \to G$, the composite given by

$H \times F \stackrel{\tilde{\theta} \times 1_F}{\to} G^F \times F \stackrel{\epsilon_{F, G}}{\to} G$

is $\theta$ again.

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

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

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

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

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

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

$H \times F \stackrel{\eta \times 1_F}{\to} G^F \times F \stackrel{\epsilon_{F, G}}{\to} G$

is $\eta$ again.

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

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

is $\eta$. In other words, that for any object $U$ and element $y \in H(U)$, we have $\tilde{\theta}(U)(y) = \eta (U)(y)$. In other words, that for any object $V$, any morphism $f: V \to U$, and any element $x \in F(V)$, that

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

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

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

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

$\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 $y$ the composite $Nat(C(-, f) \times 1_F, 1_G) \circ \eta (U)$. This result is (by definition) the composite transformation

$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

$\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.

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

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

$C(-, 0) \times F \to G$

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

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

between the sets of vertices of $F$ and $G$.

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

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

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

$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, b}$, subject to a naturality condition that amounts to asserting commutativity of the diagrams

$\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})$ of $G^F$ is the vertex $e_{0, a}: F(0) \to G(0)$ of $G^F$, and that the target of $(e_1, e_{0, a}, e_{0, b})$ is the vertex $e_{0, b}: F(0) \to G(0)$.

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

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

$(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)$ and $t(e)$ be the source and target of $e$, we take $e_1 \coloneqq \theta(1)(e, -)$ and $e_{0, a} \coloneqq \theta(0)(s(e), -)$ and $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.

Now we specialize even further to the case where we consider only directed graphs $(V, E, i: E \to V \times V)$ where $i$ is a *monomorphism* or injective function. The full subcategory consisting of such graphs and graph morphisms between them is equivalent to $\mathbf{Dig}$, the category of sets $V$ equipped with an endorelation $E$. (Briefly, any such directed graph is isomorphic to one where we take $i$ to be a subset inclusion $E \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)$ and $G = (V', E', i')$ are directed graphs for which the source-target pairings $i$, $i'$ are injective, then the source-target pairing for $G^F$, mapping a triple $(e_1, e_{0, a}, e_{0, b})$ to the pair $(e_{0, a}, e_{0, b})$, is also injective. In other words, given $(e_{0, a}, e_{0, b})$ there is at most one function $e_1: F(1) \to G(1)$ for which

$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' = \langle s_G, t_G \rangle: G(1) \to G(0) \times G(0)$ means there is at most $e_1$ such that

$i' \circ e_1 = \langle e_{0, a} \circ s_F, e_{0, b} \circ t_F \rangle.$

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

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

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