3
$\begingroup$

I'm coming across the following 'commuting' diagram a lot in my work, and I think it should have a neat categorical formulation. But I can't work it out for myself, and don't know what too google for. Maybe somebody can give me a pointer?

Assume I have 4 functions/morphisms.

  • $f : A \rightarrow B$.
  • $down : A \rightarrow A'$.
  • $up : B' \rightarrow B$.
  • $g : A' \rightarrow A' \oplus B'$.

Here $\oplus$ is the disjoint sum of sets. I want to say the following diagram 'commutes':

Should commute but doesn't 'typecheck'

but it doesn't 'typecheck' because the codomain of $g$ doesn't match the domain of $up$. However, it does 'commute eventually' in the following sense. For all $a \in A$ the following holds. There exist $a_0, ..., a_{n-1} \in A'$ and $b' \in B'$ such that:

  • $down(a) = a_0$,
  • $g(a_0) = inl(a_1)$,
  • $g(a_1) = inl(a_2)$,
  • ...
  • $g(a_{n-2}) = inl(a_{n-1})$,
  • $g(a_{n-1}) = inr(b')$, and
  • $up(b') = f(a)$.

Here $inl(a)$ means $a$ is in the 'left' part of the sum $A' \oplus B'$ while $inr(b)$ means $b$ is in the 'right' part of $A' \oplus B'$. In other words, for the diagram to 'commute', $g$ should be applied until it yields something of type $B$. In my application, this will always eventually happen. If we were sloppy and ignored the $inl/inr$ we could write: $\forall a\in A. \exists n. f(a) = up ( g^n(down(a)))$.

What's a good categorical rendering of this? Some abstract conception of iteration or recursion? In which parts of mathematics do similar constructions crop up?

$\endgroup$
4
  • 1
    $\begingroup$ So $g(\text{down}(A))$ is contained in $B'$ ? $\endgroup$ Jun 16, 2015 at 12:32
  • 1
    $\begingroup$ @StefanHamcke Not necessarily. The 'transitive closure' of $g^*$ applied to $down(A)$ is in $B'$. For each individual $a \in A'$, the number of times I need to apply $g$ before I arrive in $B'$ is typically different. $\endgroup$ Jun 16, 2015 at 12:38
  • 1
    $\begingroup$ I see. Is this true for all point in $A'$, or just for those in the image of $A$?. I mean, for each $a\in A'$, can you apply $g$ some finite amount of times until you arrive in $B'$? $\endgroup$ Jun 16, 2015 at 12:46
  • 1
    $\begingroup$ @StefanHamcke In my applications this is true for all of $A'$, It's very important that this is true. $\endgroup$ Jun 16, 2015 at 12:47

1 Answer 1

1
+50
$\begingroup$

Since you're interested in considering objects that have elements I'll assume we are working with $\mathbf{Sets}$ the category of sets and functions.

From the function $g \colon A' \to A' \oplus B'$ and from $inr \colon B' \to A' \oplus B'$ you can obtain the function $\bar g \colon A' \oplus B' \to A' \oplus B'$. By definition this function is such that

  • for every $a \in A'$ we have $\bar g(inl(a))=g(a)$;
  • for every $b \in B'$ we have $\bar g(inr(b))=b$.

Now using your notation we have that $inl(a_1)=\bar g(inl(a_0))$ and an easy induction shows that for every $n=1,\dots,n$ we have that $inl(a_n)=\bar g^n(inl(a_0))$. So your requirement that the sequence of the $a_n$'s eventually falls in $B$ can be expressed as

$$\forall a \in A'\ \exists b \in B'\ \exists n \in \mathbb N\ \bar g^n(inl(a))=inr(b)\ .$$

This should imply that $B'$ is the colimit of the diagram

$$A' \oplus B' \stackrel{\bar g}{\longrightarrow}A' \oplus B' \stackrel{\bar g}{\longrightarrow}A' \oplus B' \stackrel{\bar g}{\longrightarrow}A' \oplus B' \stackrel{\bar g}{\longrightarrow}A' \oplus B' \stackrel{\bar g}{\longrightarrow}A' \oplus B' \dots$$ where the colimit maps $(in^g_i \colon A' \oplus B' \to B')_{i \in \mathbb N}$ should send every $inl(a)$ into the eventual limit of the sequence $\{\bar g^n(inl(a))\}_{n \in \mathbb N}$ and every $inr(b)$ into $b$ (itself).

Now you could express your condition via the commutativity of the following diagram $$ \require{AMScd} \begin{CD} A @>{f}>> B \\ @V{down}VV @A{up}AA\\ A' @>{in^g_1 \circ inl}>> B' \end{CD} $$ where $inl$ is the embedding of $A'$ into $A' \oplus B'$ while $in^g_1$ is the first structure map of the above mentioned colimit diagram $(A' \oplus B' \stackrel{in^g_i}{\longrightarrow} B')_{i \in \mathbb N}$.

Hope this helps.

$\endgroup$

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.