# Completing a Category definition with Nodes as sets and Arrows as a triples of a Set and two functions

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$;$src_E3(a_3)=src_E1(a_1)trg_E3(a_3)=trg_E1(a_2)$ • 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? – Musa Al-hassy Jun 22 '16 at 4:32 ## 1 Answer 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.

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