I'm reading Category Theory by Mac Lane and I'm trying to understand the paragraphs in the pictures included below.

What is the difference between a directed graph and an $O$-graph?
Why is the picture in the blue box considered an $O$-graph?

The blue box picture looks like two parallel morphisms between two digraphs both called $O$, and not an $O$-graph which is defined as a single digraph.

What does it mean by both functions domain and range the identity?

enter image description here


What is the difference between a directed graph and an $O$−graph?

An $O$-graph is a directed graph where $O$ is the set of vertices (although the category of $O$-graphs differs substantially from the category of directed graphs—see Alex Kruckman's comment below). For example, this graph (public domain image from Wikimedia Commons, created by Wikimedia user Booyabazooka) is a $\{1, 2, 3, 4\}$-graph:

tournament graph on four vertices

Why is the picture in the blue box considered an $O$−graph?

The way MacLane defines a graph is as four pieces of information:

  • A set $A$ of arrows
  • A set $O$ of verticies
  • A function $\partial_0: A \rightarrow O$, which defines the tail of each arrow
  • A function $\partial_1: A \rightarrow O$, which defines the head of each arrow

For example, for the graph in the image above:

  • $A$ is a set with 6 elements, which could be $\{e_1, e_2, \dots, e_6\}$.
  • $O = \{1, 2, 3, 4\}$
  • If $e_1$ is the top horizontal arrow from $1$ to $2$, then $\partial_0(e_1) = 1$ and $\partial_1(e_1) = 2$.

MacLane uses the shorthand $A \rightrightarrows O$ for the two functions $\partial_0: A \rightarrow O$ and $\partial_1: A \rightarrow O$.

The graph $O \rightrightarrows O$ means a graph where each element of $O$ is regarded as both a vertex and an arrow. By saying that $\partial_0$ and $\partial_1$ are both identity functions, he's saying that each element of $x \in O$, when regarded as an arrow, is a loop from the vertex $x$ to itself.

  • 3
    $\begingroup$ It's also worth noting that $O$-graphs differ from directed graphs in the definition of their morphisms: A morphism of directed graphs $(O,A,\delta_0,\delta_1)\to (O',A'\delta_0',\delta_1')$ might have any function $D_O\colon O\to O'$ as its map on objects, while a morphism of $O$-graphs $(O,A,\delta_0,\delta_1)\to (O,A'\delta_0',\delta_1')$ is required to have $\text{id}_O\colon O\to O$ as its map on objects. Part of the categorical philosophy is that a class of mathematical objects is determined not just by the definition of the object, but also the definition of the maps between objects. $\endgroup$ – Alex Kruckman Dec 11 '17 at 16:46
  • 2
    $\begingroup$ I believe you recognize this, but for the benefit of the OP I comment that I'm fairly certain the occurrence of the word "range" in that paragraph in the picture is a typo, and what's intended is the "codomain" terminology used in his definition of a directed graph (i.e. $\partial_1$). $\endgroup$ – Malice Vidrine Dec 11 '17 at 16:46
  • 1
    $\begingroup$ @OliverG, in Mac Lane's formulation of a directed graph $A \rightrightarrows O$, the set of arrows $A$ does not have to carry any information about what the head and tail of the arrows are. That is determined by the functions $\partial_0: A \rightarrow O$ and $\partial_1: A \rightarrow O$. In Mac Lane's "simplest" $O$-graph $O \rightrightarrows O$, the set $O$ is serving both as the set of arrows and set of vertices. So, that's what I mean by saying "each element of $O$ is regarded as both a vertex and an arrow". (Continued...) $\endgroup$ – PersonX Dec 12 '17 at 0:45
  • 1
    $\begingroup$ Now, the statement that $\partial_0$ ("domain") and $\partial_1$ ("range", which Malice Vidrine points out should be "co-domain") are both identity is saying that each $x \in O$, as an arrow, has $O$ as both its domain (head) and co-domain (tail). That is saying that each $x \in O$ is a loop from $x$ to $x$. $\endgroup$ – PersonX Dec 12 '17 at 0:56
  • 1
    $\begingroup$ Note that you could have a $O$-graph $O \rightrightarrows O$ without $\partial_0$ and $\partial_1$ both being the identity. For example, let $G$ be any finite group, and $g \in G$ a non-identity element. Then define $\partial_0: G \rightarrow G$ by $\partial_0(x) = x$ and $\partial_1: G \rightarrow G$ by $\partial_1(x) = gx$. This would give you a perfectly good $G$-graph. $\endgroup$ – PersonX Dec 12 '17 at 0:58

The directed graph has $A$ for arrows and $O$ for vertices. The $O$-graph has $O$ for its vertices. The $O$ just seems to be an explicit mention of the underlying set, whereas a graph can have any set of vertices.

I believe that they mean that the "simplest example" of an $O$-graph is the one where both of the arrows $O\to O$ are the identity.

  • 1
    $\begingroup$ So you're saying: An $O-$graph is defined as a digraph where the objects AND arrows are both the set $O$? $\endgroup$ – Oliver G Dec 11 '17 at 16:21
  • $\begingroup$ @OliverG Upon reading the definition I think that an $O$-graph is any graph that has the set $O$ as its vertices. These are clearly ordinary graphs, but not all graphs are $O$-graphs, since graphs can have other ses of vertices as well. $\endgroup$ – neptun Dec 11 '17 at 16:28

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.