# Explicit formula for exponential objects in category of digraphs

I have already asked a similar question: Exponential object in a category of graphs but earlier I have asked only about existence of exponential object, while in this question I ask for exact formulas for exponential object and exponential transpose:

A category is cartesian closed iff:

• It has finite products.
• For each objects $A$, $B$ is given an object $\operatorname{MOR} ( A ; B)$ (exponentiation) and a morphism (evaluation) $\varepsilon : \operatorname{MOR} ( A ; B) \times A \rightarrow B$.
• For each morphism $f : Z \times A \rightarrow B$ there is given a morphism (exponential transpose) $\sim f : Z \rightarrow \operatorname{MOR} ( A ; B)$.

• $\varepsilon \circ ( \sim f \times 1_A) = f$.

• $\varepsilon \circ \sim ( g \times 1_A) = g$.

Digraphs are relations on a set (or equivalently endomorphisms of category $\mathbf{Rel}$).

The category $\mathbf{Dig}$ of digraphs is the category whose objects are digraphs and morphisms are discretely continuous function. That is morphisms from a digraph $\mu$ to a digraph $\nu$ are functions (or more precisely morphisms of $\mathbf{Set}$) $f$ such that $f \circ \mu \subseteq \nu \circ f$ (or equivalently $\mu \subseteq f^{- 1} \circ \nu \circ f$ or equivalently $f \circ \mu \circ f^{- 1} \subseteq \nu$).

Please provide me with explicit formulas for exponential objects, evaluation, and exponential transposes together with a proof that they are really exponential objects, evaluation, and exponential transposes in the category $\mathbf{Dig}$.

Next follows my attempt to solve this problem:

$\operatorname{Ob} \operatorname{MOR} ( G ; H) = ( \operatorname{Ob} H)^{\operatorname{Ob} G}$;

$( f ; g) \in \operatorname{MOR} ( G ; H) \Leftrightarrow \forall ( v ; w) \in G : ( f ( v) ; g ( w)) \in H$ for every $f, g \in \operatorname{Ob} \operatorname{MOR} ( G ; H) = ( \operatorname{Ob} H)^{\operatorname{Ob} G}$;

If $( f ; g) \in \operatorname{MOR} ( G ; H)$ and $x \in G$ then $\varepsilon ( ( f ; g) ; x) = ( f x ; g x)$;

$\sim f = \lambda a \in Z \lambda y \in A : f ( a ; y)$ that is $( \sim f) ( a) ( y) = f ( a ; y)$.

## 1 Answer

Yes, though your notation is not 100% clear, the exponentials in $\bf Dig$ can be given as you attempted:

The direct product is the usual one.
For digraphs $(B,\mu),\ (C,\nu)$, the exponential $C^B$ can be given on the set of all functions $B\to C$ by setting its relation $\zeta$ as $$f\,\zeta\,g \ :\iff\ \forall b_1,b_2\in B\ \left(b_1\,\mu\,b_2 \implies f(b_1)\,\nu\, g(b_2)\right)\,.$$ To verify that this is indeed the exponential, it is enough to check that $${\rm Mor}(A\times B,\,C)\cong{\rm Mor}(A,\,C^B)$$ for all digraphs $A,B,C$. $\$ And, that's how the above definition arose: a mapping $\psi:A\to C^B$ is homomorphism iff $\ a_1\,\vartheta\,a_2 \implies \psi(a_1)\,\zeta\,\psi(a_2)$, that is $\ \forall a_1,a_2:\, a_1\,\vartheta\,a_2 \implies \left( \forall b_1,b_2:\, b_1\,\mu\,b_2\implies \psi(a_1)(b_1)\,\nu\,\psi(a_2)(b_2)\right)$.
And exactly this is needed in order that the mapping $A\times B\to C$ determined by $\psi$ be a homomorphism.

• That you for your answer. However explicit formulas for evaluation and transpose (and proof that they are really evaluation and transpose) are missing. Nov 17 '13 at 0:30
• Transpose is given implicitly in the answer (anyway this is exactly how you did). Evaluation always arises from the mentioned isomorphism, applying it to $A=C^B$ and considering its identity in ${\rm Mor}(A,C^B)$. Nov 17 '13 at 0:56
• Could you indeed provide explicit formulas for evaluation and transpose? It seems that I misunderstand something, I can't get the formulas to coincide Nov 18 '13 at 17:53
• Nov 22 '13 at 22:30