19
$\begingroup$

The following author noted:

Roughly speaking, category theory is graph theory with additional structure to represent composition.

My question is: Is Category Theory similar to Graph Theory?

$\endgroup$
  • 2
    $\begingroup$ Category Theory is distinct from Graph Theory in that Graph Theory can be captured in the language of set-theory whereas Category Theory often cannot be. Category Theory is about general structures of mathematical objects with certain conditions imposed (such as identity arrows, composition of arrows, and associativity of arrows). Certain categories certainly appear to be like directed-graphs but they often have more structure. The following link will provide some more information: plato.stanford.edu/entries/category-theory $\endgroup$ – letsmakemuffinstogether Apr 17 '15 at 13:24
  • 4
    $\begingroup$ Roughly speaking, group theory is set theory with additional structure to represent composition. Can we conclude that group theory is similar to set theory ? $\endgroup$ – Roland Apr 17 '15 at 16:22
  • $\begingroup$ It is like graph theory in the sense that many things are proved using (non) commutative diagrams, which are graphs essentially, since you can't always insert an arrow into a commutative diagram unless doing so would preserve its commutativity. So to represent drawn diagrams, and not diagrams as in category theory, you need to define them so that they don't necc. have identities or compositions. Or, essentially a labeled, directed graph. $\endgroup$ – Shine On You Crazy Diamond Sep 2 at 4:10
20
$\begingroup$

In fact, "Roughly speaking, category theory is graph theory with additional structure to represent composition." is a good summary of the connection between the notion of a graph (meaning here: directed multigraph) and the notion of a category. Here is a way of how to make this precise:

Let $O$ be a set ("set of vertices"). Then we have a category $O-\mathsf{Graph}$ whose objects are sets $M$ ("set of edges") equipped with two maps $s,t : M \rightrightarrows O$ ("source" and "target"). This category is monoidal: The unit is $\mathrm{id} : O \rightrightarrows O$, the tensor product of $s,t : M \rightrightarrows O$ with $u,v : N \rightrightarrows O$ is the fiber product $M \times_{t,O,u} N$ equipped with the maps $\rightrightarrows O$ induced by $s$ and $v$. To any monoidal category, we may associate the category of monoid objects.

Observation. A category with object set $O$ is the same as a monoid object in $O-\mathsf{Graph}$.

This description is quite nice, as it really says in how far categories are "graphs with multiplication". If $O$ is a class, we can make the obvious adjustments; or we use ZFC + Grothendieck universes, so that we can work with sets alone. It is possible to get rid of the $O$ in the statement (which is quite natural, because we never want to fix the object set), but then you will have to use more advanced language: A category is the same as a monad object in the bicategory of spans.

However, this connection between the notion of a category and the notion of a graph does not mean that the theories are similar. Categories have a much richer structure, namely the composition of arrows, and this structure is used in category theory all over the place, for example in the context of commutative diagrams, universal properties, adjunctions etc. In graph theory, though, we just don't have this kind of structure. Also, many notions in graph theory only make sense for finite graphs, whereas finite categories don't appear so often in category theory.

There are some overlappings, though. An object of a category is called initial if it admits a unique morphism to each other object. This only refers to the underlying graph of the category, and in fact, makes sense for arbitrary (directed) graphs. We may call a vertex initial if it admits a unique edge to any other vertex. Similarly, we may speak of final vertices.

A graph is connected if there is a vertex which reaches every other vertex via some zig-zag path of edges. The same notion makes sense for categories (i.e. one doesn't refer to the composition of arrows here). Every category is a coproduct of connected categories, and this is useful sometimes.

Two vertices in a graph are called adjacent if there is an edge between them. This notion is not so important in category theory because often one wants to know more than just the existence of a morphism. Moreover, in some categories, such as the category of abelian groups, there is a zero morphism between any two objects.

PS: I don't agree with the answer by Ove Ahlman, see my comment there.

$\endgroup$
6
$\begingroup$

Category theory and graph theory are similar in the sense that both are visualized by arrows between dots. After this the similarities quite much stop, and both have different reason for their existence.

In category theory, we may have a huge amount of dots, and these dots do often represent some abstract algebraic structure or other object with some meaning. The arrows which go between dots needs to respect very specific rules, which makes it possible to draw conclusion about the category and hence about the objects which the dots represents.

In Graph theory however we can draw the arrows in any way we want do not need to care about rules. This gives us a very free way to draw, but also, we do not get the same implementations as graph theory may draw conclusion about the objects which the dots represent, since in graph theory we have dots without meaning.

Category theory draws from graph theory that we may talk about dots being connected, the degree of a dot etc. And when we do not have an extremly huge amount of dots, a category is a graph. So in this case Category theory is just a special case of graph theory. On the other hand, graph theory (and everything else) may be studied abstractly in category theory, so we could say that graph theory is a special object of study in category theory.

My conclusion Is that the largest similarity (and why people think they are similar) is the way we visualize the two.

$\endgroup$
  • 8
    $\begingroup$ Size issues? That's not the point. Categories allow us to compose arrows. This is the difference to graphs. Composition is not an extra rule. It is extra structure. Also, every graph produces a category, the path category, and conversely any (small) category has an underlying graph. It is not correct that a category is a graph, though. In particular, the conclusion "So in this case Category theory is just a special case of graph theory" is absolutey wrong. What is a commutative diagram in a graph? $\endgroup$ – Martin Brandenburg Apr 17 '15 at 15:23
  • $\begingroup$ Seconded. Just to add two usual alternative technical terms: in the above answer, in "Composition is not an extra rule. It is extra structure." one can replace "rule" with "axiom" and "structure" with "data" to arrive at: Composition is not an extra axiom. It is extra data. $\endgroup$ – Peter Heinig Aug 1 '17 at 10:55
1
$\begingroup$

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.

$\endgroup$

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.