I would like to study a category that:

Objects: are (finite) Sets.

Arrows: are triples of the form $(A, src:A\rightarrow B,trg:A\rightarrow C)$, such that A, B, C are sets and src and trg are functions.

Source of the arrow $E=(A_E, src_E:A_E\rightarrow B,trg_E:A_E\rightarrow C)$ is the Object B, and its target is the Object C.

Identity arrows are naturally defined as $id_A=(A, src:A\rightarrow A,trg:A\rightarrow A)$ where src and trg are both identity functions.

Now I want to define composition:

$$E_1 \circ E_2 = E_3$$

Question :What is the more concise way to define E3 in terms of components of E1, and E2 to complete my category definition?

my thoughts:if

  • $E_1 : L \rightarrow M$
  • $E_2 : M \rightarrow N$

Then we need to define

  • $E_3 : L \rightarrow N$

Let's assume that

  • $E_1 = (A_{E_1},src_{E_1}:A_{E_1} \rightarrow L, trg_{E_1}:A_{E_1} \rightarrow M)$
  • $E_2 = (A_{E_2},src_{E_2}:A_{E_2} \rightarrow M, trg_{E_1}:A_{E_2} \rightarrow N)$

Then we need to construct

  • $E_3 = (A_{E_3},src_{E_3}:A_{E_3} \rightarrow L, trg_{E_1}:A_{E_3} \rightarrow N)$

Computationally I want $E_3$ to be constructed somehow in the following way:

foreach ($a_1:A_{E1}$) 
   foreach ($a_2:A{E2}$)
        if ($trg_E1(a_1)$ == src_E2(a_2)$)
             var $a_3$=createNewElement();
             put $a_3$ in $A_E3$;
  • $\begingroup$ The types of $src_{Ei}, tgt_{Ei}$ do not match at either head nor tail and so cannot be composed to produced the needed pair of functions for $E3$ ---or so I claim--- and so your definition of the typing for arrows is possibly flawed. Where'd you get this exercise from? $\endgroup$ – Musa Al-hassy Jun 22 '16 at 4:32

It looks like you're trying to give a definition of the category of spans in the category of (finite) sets. In this case, composition will be given by pullback.

Explicitly, given spans $$\begin{matrix} && A && \\ & {}^{f}{\swarrow} && {\searrow}^g \\ B &&&& C \end{matrix} \quad \text{and} \quad \begin{matrix} && A' && \\ & {}^{h}{\swarrow} && {\searrow}^{k} \\ C &&&& D \end{matrix}$$ form the pullback of $g$ and $h$: $$\begin{matrix} && P && \\ & {}^p{\swarrow} && {\searrow}^q & \\ A &&&& A' \\ & {}_g{\searrow} && {\swarrow}_k & \\ && C && \end{matrix}$$ Specifically, $P = \{ (a,a') \in A \times A' \mid g(a)=k(a') \}$ and $p,q$ are the projection maps onto the first and second components, respectively. This then yields a span $$\begin{matrix} && P && \\ & {}^{f \circ p}{\swarrow} && {\searrow}^{k \circ q} \\ B &&&& D \end{matrix}$$ and you can check that this definition of composition satisfies the necessary laws for composition.

  • $\begingroup$ It must be pointed out that what you get is not a category per se but rather a bicategory... $\endgroup$ – Zhen Lin Jun 22 '16 at 12:10

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.