Couldn't we define a small category as a transitive reflexive graph together with an associative operation?

Question

Based on the definition of a small category $\mathcal{C}$ being a category whose objects form a set, coudln't we define a graph $G=(V,E)$ and an operation $\cdot:E\times E\to E$ where $(x,y)\cdot (y,z)=(x,z)$, $V=\text{Ob}(\mathcal{C})$ and $(x,y)\in E\iff \exists f\in\text{Hom}(\mathcal{C})\ \text{s.t.}\ f:x\longrightarrow y$? Because $G$ is reflexive, we have $(x,x)\in E$ or, what it's same, $\exists f\in\text{Hom}(\mathcal{C})\ \text{s.t.}\ f:x\longrightarrow x$; and because of transitivity, we know that if $(x,y)$ and $(y,z)$ are in $E$, then $(x,z)$ is in $E$, so $\exists f,g,h\in\text{Hom}(\mathcal{C})\ \text{s.t.}\ f:x\longrightarrow y\land g:y\longrightarrow z\land h:x\longrightarrow z$, meaning that the identity and associative laws do seem to hold in $\mathcal{C}$.

Answer 1

What you've written seems to only allow for at most one morphism between objects. Now, if you alter it to fix this situation, giving:

A category-graph is a set $V$, a set $E$, a pair of maps $source, target:E\rightarrow V$, and a partial binary operation $\circ$ satisfying [stuff]

then you do indeed capture the notion of a category. But note that the presence of multiple morphisms with the same source/target means that the structure provided by composition is in general extremely complicated, so it really is misleading (in my opinion) to think of a category as "just a graph with a bit of extra stuff."

Answer 2

Yes, something along these lines does indeed hold: a category is a directed graph (possibly with parallel arrows, i.e. allowing more arrows $a\to b$ for points $a,b$) equipped with an associative composition operation on its paths, including paths of length 0, i.e. objects - giving the identity arrows.

A directed graph can be given by a pair of sets $V,E$ and a pair of functions $source,\ target:E\to V$.
(In categorical context these are called the domain and codomain of a morphism (=arrow)).

We can generalize it to get a version of directed 'bipartite graph': a span (in $Set$) from set $A$ to set $B$ is a pair of functions with common domain, $(s:E\to A,\ t:E\to B)$. We can still regard elements of $E$ as arrows, $s$ as source and $t$ as target, and then all arrows of a span go from a point of $A$ to a point of $B$.
If for every $a\in A$ and $b\in B$ there is at most one arrow between them, then we get back the notion of binary relation between $A$ and $B$.

Now, spans $A\leadsto B$ and $B\leadsto C$ can be composed in a natural way (well, only up to isomorphism and just almost associatively), and we can also define morphisms between spans.

So, a directed graph is just an 'endo-'span $G:V\leadsto V$. The arrows of the span composition $GG$ are the paths in $G$ of length 2 (the composable pairs of arrows), and thus giving a composition will be just a span morphism $GG\to G$. We can also formulate the associativity and unit constraints.

All in all:

Sets and spans make a bicategory, in which

• the endomorphisms are the directed graphs,
• and the internal monoids are exactly the categories!