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?


3 Answers 3


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.

  • $\begingroup$ If each vertice represents an object and each directed edge can represent an arrow, can this 'show' part of a composition mapping? Can a non-rigorous representation be useful in Category Theory? $\endgroup$
    – user128932
    Commented Apr 17, 2014 at 2:36
  • $\begingroup$ No, composition cannot be inferred from the raw arrows in general. Regarding the usefulness of this representation, part of the description of a category is this directed graph. The other part is the composition operation on edges. $\endgroup$ Commented Apr 17, 2014 at 2:50
  • $\begingroup$ Could you use Category Theory to simplify Topology? $\endgroup$
    – user128932
    Commented Apr 17, 2014 at 2:54
  • 2
    $\begingroup$ Category theory is a very useful mathematic subject, forming a common language for many areas in modern mathematics. If you're interested in the mathematical implications, I suggest you ask on math.se. $\endgroup$ Commented Apr 17, 2014 at 4:15
  • $\begingroup$ Can something like category theory be applied to logic or philosophy? Is there a Category Theory for Dummies OR a Category Theory Demystified book? $\endgroup$
    – user128932
    Commented Apr 18, 2014 at 2:31

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.


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".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.