Diagrams, Categorical Limits, and Topoi (Part 1)

Definition. A (small) directed graph [latex]G[/latex] is a 3-tuple [latex](V,E,d)[/latex] where [latex]V[/latex] and [latex]E[/latex] are sets and [latex]d:E\to V\times V[/latex]. Similarly, a subgraph [latex]A[/latex] of [latex]G[/latex] is a 3-tuple [latex](V_A,E_A,d)[/latex] such that [latex]E_A[/latex] is contained in [latex]E[/latex] and [latex]V_A\times V_A\subseteq V\times V[/latex] contains [latex]d(E_A)[/latex].

Definition. If [latex]V\times V[/latex] is replaced with [latex]V\times V / \{(x,y)\sim (y,x)\}[/latex], then the graph is undirected.

Throughout this post, all graphs will be small. Moreover, the first coordinate will be the starting point and the last coordinate will be the end point.

Let [latex]V=\{A,B\}[/latex], [latex]E=\{f\}[/latex], and [latex]d:f\mapsto (A,B)[/latex]. Then the (undirected) graph can be represented by the picture
The remaining examples will be directed graphs.
In full abstraction, we cannot visual graphs, but restricting ourselves to the cardinality [latex]2^{\aleph_0}[/latex], it is somewhat possible.

Finite case: Let [latex]V=\{A,B,C\}[/latex], [latex]E=\{f,g,h,i\}[/latex], and [latex]d:f\mapsto (A,B);g\mapsto (A,C); h\mapsto (B,C); i\mapsto (B,A)[/latex]. Then the graph can be represented by the picture


Slight warning: This is not a commutative diagram. [latex]g=h\circ f[/latex] is not defined.

[latex]\aleph_0[/latex] case: Let [latex]V=\{A_i\}_{i\in\mathbb{N}}[/latex], [latex]E=\{f,g,h,i\}[/latex], and [latex]d:f\mapsto (A_1,A_2);g\mapsto (A_1,A_2); h\mapsto (A_1,A_1); i\mapsto (A_2,A_3); j\mapsto (A_4,A_5)[/latex]. Then the graph [latex]G=(V,E,d)[/latex] can be represented by the picture

In this case, I have illustrated the fact that vertices can be isolated in a graph as well as the fact that subgraphs can be disjoint. Indeed, consider the maps [latex]d_i:E\to V, i=1,2[/latex] obtained by composing [latex]d[/latex] with the two canonical projections; if [latex]A\not\in d_i(E), i=1,2[/latex], then [latex]A[/latex] is called isolated; if [latex]G_1,G_2\subseteq G[/latex] such that [latex]V_{G_1}\cap V_{G_2}=E_{G_1}\cap E_{G_2}=\emptyset[/latex], [latex]G_1[/latex] and [latex]G_2[/latex] are disjoint.

[latex]2^{\aleph_0}[/latex] boring case: Let [latex]V=\{A_i\}_{i\in \mathbb{R}}[/latex], [latex]E=\{f_i\}_{i\in\mathbb{Z}}[/latex], and [latex]d:f_i\mapsto (A_i,A_{i+1})[/latex]. Then the graph can be represented by the picture

where the straight line is the [latex]\{A_i\}_{i\in \mathbb{R}}[/latex].
[latex]2^{\aleph_0}[/latex] exotic case: Let [latex]V=\{A_i\}_{i\in \mathbb{C}}[/latex], [latex]E=\{f_i\}_{i\in\mathbb{N}\times [0,2\pi]}[/latex], and [latex]d:f_{(n,\theta)}\mapsto (A_{ne^{i\theta}},A_{(n+1)e^{i\theta}})[/latex]. Then the graph can be represented by the picture

where the bottom plane is [latex]V[/latex] and [latex]f_i[/latex] is a single arc in each ring, with the arc pointing outwards from [latex](0,0)[/latex].

In general, there are infinitely many ways to pictorially represent a graph.

If [latex]G=(V,E,d)[/latex] and [latex]G’=(V’,E’,d’)[/latex], a morphism of graphs [latex]\varphi:G\to G'[/latex] is a pair [latex]\varphi_V:V\to V'[/latex] and [latex]\varphi_E:E\to E'[/latex], written [latex](\varphi_V,\varphi_E)[/latex], such that the following diagram commutes:

[latex] (\varphi_V\times \varphi_V)d=d’\varphi_E [/latex]

Proposition. The collection of graphs form a category [latex]\operatorname{Grph}[/latex] whose objects are graphs and arrows are morphisms of graphs.

Proof. Let [latex]G_i=(V_i,E_i,d_i), i=1,..4[/latex] be graphs. Observe that as sets, we have the composition

[latex] c_V:\hom_{\operatorname{Set}}(V_1,V_2)\times \hom_{\operatorname{Set}}(V_2,V_3)\to \hom_{\operatorname{Set}}(V_1,V_3). [/latex]
[latex] c_E:\hom_{\operatorname{Set}}(E_1,E_2)\times \hom_{\operatorname{Set}}(E_2,E_3)\to \hom_{\operatorname{Set}}(E_1,E_3). [/latex]

Moreover,

[latex] [c_V(\phi_{V_1},\phi_{V_2}) \times c_V(\phi_{V_1},\phi_{V_2})]d_1=d_3c_E(\phi_{E_1},\phi_{E_2}) [/latex]

so [latex]c=(c_V,c_E)[/latex] satisfies the composition axiom. Associativity is proven similarly, and for identity, take [latex](\operatorname{Id}_V,\operatorname{Id}_E)[/latex] to be the set identities.

[latex]\blacksquare[/latex]

It is clear [latex]\operatorname{Grph}[/latex] can be defined under any category by simply replacing [latex]\operatorname{Sets}[/latex] with another category.

Now any (small) category has an underlying graph (simply forget compositions and identities), so we have a forgetful functor [latex]F_{\operatorname{Grph}}:\operatorname{Cat}\to \operatorname{Grph}[/latex]. Denote the underlying graph of a category [latex]\operatorname{C}[/latex] by [latex]\operatorname{C}_{\operatorname{Grph}}[/latex].

Definition. A diagram of shape [latex]G[/latex] in the category [latex]\operatorname{C}[/latex] is a morphism [latex]D:G\to\operatorname{C}_{\operatorname{Grph}}[/latex].

Now I emphasize the word shape [latex]G[/latex] for two reasons: First is the obvious geometric perspective when given a “nice” graph. Second is the fact that if [latex]G\cong G'[/latex] in [latex]\operatorname{Grph}[/latex], the notion of shape [latex]G[/latex] and shape [latex]G'[/latex] are equivalent. Formally,

Proposition. If [latex]D[/latex] is a diagram of shape [latex]G[/latex] in [latex]\operatorname{C}[/latex] and [latex]G\cong G'[/latex], then there exists a diagram [latex]D'[/latex] of shape [latex]G'[/latex] in [latex]\operatorname{C}[/latex] such that [latex]D(G)=D'(G’)[/latex].

Proof. The claim follows from the diagram

[latex]\blacksquare[/latex]

Some cases to illustrate the preceding points:

Small case: Consider the category [latex]1[/latex] with one object [latex]1[/latex] and one morphism [latex]\operatorname{Id}[/latex]. Then [latex]1_{\operatorname{Grph}}[/latex] is the graph

Large case: Consider the category [latex]\operatorname{Grp}[/latex] whose objects are groups and arrows are morphisms of groups. An example of a subgraph of [latex]\operatorname{Grp}_{\operatorname{Grph}}[/latex] is a sequence

[latex] 1\to A\overset{k}{\to} B\to C\to D\to 1 [/latex]

Let [latex]X[/latex] denote this subgraph and let [latex]G=(V,E,d)[/latex] be a graph with [latex]V=\{1,2\}[/latex], [latex]E=\{f\}[/latex], and [latex]d:f\mapsto (1,2)[/latex]. Define [latex]\phi:G\to X[/latex] by taking [latex]1\mapsto A, 2\mapsto B, f\mapsto k[/latex]. Then [latex]\phi[/latex] is a morphism of graphs, hence a diagram of shape [latex]G[/latex] in [latex]X[/latex]. Considering the inclusion morphisms [latex]i:X\hookrightarrow \operatorname{Grp}_{\operatorname{Grph}}[/latex], [latex]i\phi[/latex] is a diagram of shape [latex]G[/latex] in [latex]\operatorname{Grp}_{\operatorname{Grph}}[/latex].

Remark. As stated before, graphs can be pictorially represented in infinitely many different ways. For example, the category [latex]1[/latex] can also be represented by

[latex] 1\overset{\operatorname{Id}}{\to} 1 [/latex]

or even

[latex] 1\overset{\operatorname{Id}}{\to}1\overset{\operatorname{Id}}{\to}1\overset{\operatorname{Id}}{\to}1 [/latex]

Due to this degeneracy, for any category [latex]\operatorname{C}[/latex], one can show that if [latex]G[/latex] is any graph, then there is a diagram of shape [latex]G[/latex] in [latex]\operatorname{C}[/latex].

Share your thoughts

This site uses Akismet to reduce spam. Learn how your comment data is processed.