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


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.

  • $\begingroup$ That you for your answer. However explicit formulas for evaluation and transpose (and proof that they are really evaluation and transpose) are missing. $\endgroup$
    – porton
    Nov 17 '13 at 0:30
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Berci
    Nov 17 '13 at 0:56
  • $\begingroup$ Could you indeed provide explicit formulas for evaluation and transpose? It seems that I misunderstand something, I can't get the formulas to coincide $\endgroup$
    – porton
    Nov 18 '13 at 17:53
  • $\begingroup$ See also math.stackexchange.com/questions/576382/… $\endgroup$
    – porton
    Nov 22 '13 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.