Category theory and graphs

Question

Could most categories , or a finite part of them be represented on a subset of a complete graph of N vertices (Kn) which is connected. and partly directed? Could all the axioms of category theory be written for such graphs?

Answer 1

A category consists of:

• Objects.

• Directed arrows between objects. There can be multiple arrows between any two given objects, or a unique arrow, or none.

• A composition map for arrows that takes an arrow $f$ from $x$ to $y$ and another arrow $g$ from $y$ to $z$ and outputs an arrow $gf$ from $x$ to $z$.

• Depending on the formulation, there might also be a distinguished arrow between every object and itself (the identity arrow).

The composition map has to satisfy the following axioms:

• Associativity: if $f\colon x \to y$, $g\colon y \to z$ and $h\colon z \to w$ then $h(gf) = (hg)f$.

• Identity: if $f\colon x \to y$ and $1_x\colon x \to x$ and $1_y\colon y \to y$ are the distinguished self loops then $f1_x = 1_yf = f$. (If the formulation does not include the distinguished self-loops: there exist arrows $1_x\colon x\to x$ and $1_y\colon y\to y$ such that $f1_x = 1_yf = f$.)

You can represent this data in many ways. A graph with multiple edges is, however, not enough, since you also need to specify the composition map.

Answer 2

Lambek and Scott use this even as a definition for a category:

A deductive system is a graph in which to each object $A$ there is associated an arrow $1_A: A\to A$, the identity arrow, and to each pair of arrows $f:A\to B$ and $g:B\to C$ there is associated an arrow $gf:A\to C$, the composition of $f$ and $g$.

A logician may think of the objects as formulas and of the arrows as deductions or proofs, hence of

$$\frac{f:A\to B \qquad g:B\to C}{gf:A\to C}$$

as a rule of inference.

A category is a deductive system in which the following equations hold for all $f:A\to B$, $g:B\to C$ and $h:C\to D$:

$$f1_A=f=1_Bf$$ $$(hg)f=h(gf)$$

(Lambek & Scott. Introduction to higher order categorical logic, p. 5)

In summary: Lambek and Scott define a deductive system as a (directed) graph with units and compositions (alias modus ponens, alias rule of inference) and a category as a deductive system where the 'ususal' laws hold for units and rule of inference.

Answer 3

A connection between graphs and categories that most introduction book would mention is the free-forgetful adjunction $$(F\colon Graph \rightarrow Cat ) \dashv (U\colon Cat \rightarrow Graph)$$ between categories:

• $Graph$ of small directed graphs and graph homomorphisms
• $Cat$ of small categories and functors

To spell this out naively just the action on objects of $F$ and $U$:

• $F$ takes given graph $g$ and give out the Free category $F(g)$ having as objects the same set of vertices in $g$ and as morphisms the directed paths in $g$. Morphism composition is the concatenation of paths and the identity morphism is the empty paths.
• $U$ takes a category $C$ and gives out the Underlying category $U(C)$ having as vertices the objects in $C$ and as directed edges the morphisms in $C$. The action of $U$ is intuitively to forget that there was composition and identity and extra properties that $C$ used to have.

I think even beginners (who don't yet understand adjunction) could appreciate why $F$ and $U$ is useful because whenever a book describe a "tiny" category by means of drawing a diagram such as

$$\bullet \rightarrow \bullet \rightarrow \bullet$$

and say that it omits the identity anad transitive morphisms. What category it is describing is exactly the free category generated by the above directed graph.

---

I have a feeling that you are misunderstanding something as you mentioned

... represented on a subset of a complete graph of N vertices (Kn) which is connected. and partly directed? ...

I think what you mean is by representing a category $C$ with a graph is $U(C)$. And if that is the case, you would be wrong to say that $U(C)$ has to be "connected and partly directed". The underlying graph of a category doesn't have to be connected. Take for example, a category with just two objects and 2 identity morphisms.

A better description properties of $U(C)$ might be "transitive and reflective".