Limits in the category of graphs

Posted on 23 January 2020 by Remy

This is a first post about some categorical properties of graphs (there might be a few more).

Definition. For us, a graph is a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal P(V)$ is a collection of subsets of $V$ of size $1$ or $2$ . An element $\{x,y\} \in E$ with $x \neq y$ is called an edge from $x$ to $y$ , and a singleton $\{x\} \in E$ is a loop at $x$ (or sometimes an edge from $x$ to itself). If $G = (V,E)$ , it is customary to write $V(G) = V$ and $E(G) = E$ .

A morphism of graphs $f \colon G \to H$ is a map $f \colon V(G) \to V(H)$ such that $f(e) \in E(H)$ for all $e \in E(G)$ . The category of graphs will be denoted $\mathbf{Grph}$ , and $V \colon \mathbf{Grph} \to \mathbf{Set}$ will be called the forgetful functor.

Example. The complete graph $K_n$ on $n$ vertices is the graph $(V,E)$ where $V = \{1,\ldots,n\}$ and $E = {V \choose 2}$ is the set of $2$ -element subsets of $V$ . In other words, there is an edge from $x$ to $y$ if and only if $x \neq y$ .

Then a morphism $G \to K_n$ is exactly an $n$ -colouring of $G$ : the condition $f(e) \in E(K_n)$ for $e \in E(G)$ forces $f(x) \neq f(y)$ whenever $x$ and $y$ are adjacent. Conversely, a morphism $f \colon K_n \to G$ to a graph $G$ without loops is exactly an $n$ -clique in $G$ : the condition that $G$ has no loops forces $f(x) \neq f(y)$ for $x \neq y$ .

Lemma. The category $\mathbf{Grph}$ has and the forgetful functor $V \colon \mathbf{Grph} \to \mathbf{Set}$ preserves all small limits.

Proof. Let $D \colon \mathscr J \to \mathbf{Grph}$ be a functor from a small category $\mathscr J$ , and let $V = \lim V \circ D$ be the limit of the underlying sets, with cone maps $f_j \colon V \to V(D(j))$ . We will equip $V$ with a graph structure $G = (V,E)$ such that the maps $G \to D(j)$ for $j \in \mathscr J$ are morphisms and then show that the constructed $G$ is a limit of $D$ in $\mathbf{Grph}$ .

To equip $V$ with an edge set $E$ , simply let $E$ be the set of $e \subseteq \mathcal P(V)$ of size $1$ or $2$ such that $f_j(e) \in E(D(j))$ for all $j \in \mathscr J$ . Then this clearly makes $G = (V,E)$ into a graph such that the $f_j \colon G \to D(j)$ are graph morphisms for all $j \in \mathscr J$ . Moreover, these maps make $G$ into the limit cone over $D$ : for any other cone $g_i \colon H \to D(j)$ , the underlying maps $V(g_i) \colon V(H) \to V(D(j))$ factor uniquely through $g \colon V(H) \to V$ by the definition of $V$ , and the construction of $E(G)$ shows that $g \colon V(H) \to V$ is actually a morphism of graphs $g \colon H \to G$ . $\qedsymbol$

Remark. Note however that $V$ does not create limits. On top of the construction above, this would mean that there is a unique graph structure $G = (V,E)$ on $V$ such that $G$ is a cone over $G$ . However, there are many such structures on $V$ , because we can remove edges all we want (on the same vertex set $V$ ).

Example. As an example, we explicitly describe the product $G \times H$ of two graphs $G$ and $H$ : by the lemma its vertex set is $V(G \times H) = V(G) \times V(H)$ . The ‘largest graph structure’ such that both projections $p \colon G \times H \to G$ and $q \colon G \times H \to H$ are graph morphisms is given by $e \in E(G \times H)$ if and only if $|e| \in \{1,2\}$ and $p(e) \in E(G)$ and $q(e) \in E(H)$ . This corresponds to the structure found in the proof of the lemma.

For a very concrete example, note that the product of two intervals/edges $G = H = K_2$ is a disjoint union of two intervals, corresponding to the diagonals in $\{1,2\} \times \{1,2\}$ . This is the local model to keep in mind.

The literature also contains other types of product graphs, which all have the underlying set $V(G) \times V(H)$ . Some authors use the notation $G \times H$ for the categorical product or tensor product we described. The Cartesian product $G \square H$ is defined by $E(G \square H) = (E(G) \times V(H)) \cup (V(G) \times E(H))$ , so that the product of two intervals is a box. The strong product $G \boxtimes H$ is the union of the two, so that the product of two intervals is a box with diagonals. There are numerous other notions of products of graphs.

Remark. Analogously, we can also show that $\mathbf{Grph}$ has and $V$ preserves all small colimits: just equip the set-theoretic colimit with the edges coming from one of the graphs in the diagram.

Example. For a concrete example of a colimit, let’s carry out an edge contraction. Let $G$ be a graph, and let $e = \{x,y\}$ be an edge. The only way to contract $e$ in our category is to create a loop: let $*$ be the one-point graph without edges, and let $f_x, f_y \colon * \to G$ be the maps sending $*$ to $x$ and $y$ respectively. Then the coequaliser of the parallel pair $f_x, f_y \colon * \rightrightarrows G$ is the graph $H$ whose vertices are $V(G)/\sim$ , where $\sim$ is the equivalence relation $a \sim b$ if and only if $a = b$ or $\{a,b\} = \{x,y\}$ , and whose edges are exactly the images of edges in $G$ . In particular, the edge $\{x,y\}$ gives a loop at the image $z = [x] = [y] \in V(H)$ .

Remark. Note that the preservation of limits also follows since $V$ has a left adjoint: to a set $S$ we can associate the discrete graph $S^{\operatorname{disc}}$ with vertex set $S$ and no edges. Then a morphism $S^{\operatorname{disc}} \to G$ to any graph $G$ is just a set map $S \to V(G)$ .

Similarly, the complete graph with loops gives a right adjoint to $V$ , showing that all colimits that exist in $\mathbf{Grph}$ must be preserved by $V$ . However, these considerations do not actually tell us which limits or colimits exist.

Scales containing every interval

Posted on 20 December 2019 by Remy

This is a maths/music crossover post, inspired by fidgeting around with diatonic chords containing no thirds. The general lemma is the following (see also the examples below):

Lemma. Let $n$ be a positive integer, and $I \subseteq \mathbf Z/n\mathbf Z$ a subset containing $k > \frac{n}{2}$ elements. Then every $a \in \mathbf Z/n\mathbf Z$ occurs as a difference $x - y$ between two elements $x, y \in I$ .

Proof. Consider the translate $I + a = \{x + a\ |\ x \in I\}$ . Since both $I$ and $I + a$ have size $k > \frac{n}{2}$ , they have an element in common. If $x \in I \cap (I + a)$ , then $x = y+a$ for some $y \in I$ , so $a = x - y$ . $\qedsymbol$

Here are some applications to music theory:

Example 1 (scales containing every chromatic interval). Any scale consisting of at least $7$ out of the $12$ available chromatic notes contains every interval. Indeed, $7 > \frac{12}{2}$ , so the lemma shows that every difference between two elements of the scale occurs.

The above proof in this case can be rephrased as follows: if we want to construct a minor third (which is $3$ semitones) in our scale $S$ , we consider the scale $S$ and its transpose $S + 3$ by a minor third. Because $7 + 7 = 14 > 12$ , there must be an overlap somewhere, corresponding to an interval of a minor third in our scale.

In fact, this shows that our scale must contain two minor thirds, since you need at least $2$ overlaps to get from $14$ down to $12$ . For example, the C major scale contains two minor seconds (B to C and E to F), at least two major thirds (C to E and G to B), and two tritones (B to F and F to B).

The closer the original key is to its transpose, the more overlaps there are between them. For example, there are $6$ major fifths in C major, since C major and G major overlap at 6 notes. Conversely, if an interval $a$ occurs many times in a key $S$ , that means that the transposition $S + a$ of $S$ by the interval $a$ has many notes in common with the old key $S$ . (Exercise: make precise the relationship between intervals occurring ‘many times’ and transpositions having ‘many notes in common’.)

We see that this argument is insensitive to enharmonic equivalence: it does not distinguish between a diminished fifth and an augmented fourth. Similarly, a harmonic minor scale contains both a minor third and an augmented second, which this argument does not distinguish.

Remark. We note that the result is sharp: the whole-tone scales $2\mathbf Z/12\mathbf Z$ and $(2\mathbf Z + 1)/12\mathbf Z$ have size $6 = \frac{12}{2}$ , but only contain the even intervals (major second, major third, tritone, minor sixth, and minor seventh).

Example 2 (harmonies containing every diatonic interval). Any cluster of $4$ notes in a major or minor scale contains every diatonic interval. Indeed, modelling the scale as integers modulo $7$ , we observe that $4 > \frac{7}{2}$ , so the lemma above shows that every diatonic interval occurs at least once.

For example, a seventh chord contains the notes¹ $\{1,3,5,7\}$ of the key. It contains a second between $7$ and $1$ , a third between $1$ and $3$ , a fourth between $5$ and $1$ , etcetera.

Thus, the largest harmony avoiding all (major or minor) thirds is a triad. In fact, it’s pretty easy to see that such a harmony must be a diatonic transposition of the sus4 (or sus2, which is an inversion) harmony. But these chords may contain a tritone, like the chord B-F-G in C major.

Example 3. If you work with your favourite $19$ -tone tuning system, then any scale consisting of at least $10$ of those notes contains every chromatic interval available in this tuning.

¹ A strange historical artefact of music is that chords start with $1$ instead of $0$ .

Epimorphisms of groups

Posted on 22 October 2019 by Remy

In my previous post, we saw that injections (surjections) in concrete categories are always monomorphisms (epimorphisms), and in some cases the converse holds.

We now wish to classify all epimorphisms of groups. To show that all epimorphisms are surjective, for any strict subgroup $H \subseteq G$ we want to construct maps $f_1, f_2 \colon G \to G'$ to some group $G'$ that differ on $G$ but agree on $H$ . In the case of abelian groups this is relatively easy, because we can take $G'$ to be the cokernel, $f_1$ the quotient map, and $f_2$ the zero map. But in general the cokernel only exists if the image is normal, so a different argument is needed.

Lemma. Let $f \colon H \to G$ be a group homomorphism. Then $f$ is an epimorphism if and only if $f$ is surjective.

Proof. We already saw that surjections are epimorphisms. Conversely, let $f \colon H \to G$ be an epimorphism of groups. We may replace $H$ by its image in $G$ , since the map $\im(f) \to G$ is still an epimorphism. Let $X = G/H$ be the coset space, viewed as a pointed set with distinguished element $* = H$ . Let $Y = X \amalg_{X\setminus *} X$ be the set “ $X$ with the distinguished point doubled”, and write $*_1$ and $*_2$ for these distinguished points.

Let $S(Y)$ be the symmetric group on $Y$ , and define homomorphisms $f_i \colon G \to S(Y)$ by letting $G$ act naturally on the $i^{\text{th}}$ copy of $X$ in $Y$ (for $i \in \{1,2\}$ ). Since the action of $H$ on $X = G/H$ fixes the trivial coset $*$ , we see that the maps $f_i|_H$ agree. Since $f$ is an epimorphism, this forces $f_1 = f_2$ . But then

$H = \Stab_{f_1}(*_1) = \Stab_{f_2}(*_1) = G,$

showing that $f$ is surjective (and a fortiori $X = \{*\}$ ). $\qedsymbol$

Note however that the result is not true in every algebraic category. For example, the map $\mathbf Z \to \mathbf Q$ is an epimorphism of (commutative) rings that is not surjective. More generally, every localisation $R \to R[S^{-1}]$ is an epimorphism, by the universal property of localisation; these maps are rarely surjective.

Concrete categories and monomorphisms

Posted on 19 October 2019 by Remy

This post serves to collect some background on concrete categories for my next post.

Concrete categories are categories in which objects have an underlying set:

Definition. A concrete category is a pair $(\mathscr C, U)$ of a category $\mathscr C$ with a faithful functor $U \colon \mathscr C \to \mathbf{Set}$ . In cases where $U$ is understood, we will simply say $\mathscr C$ is a concrete category.

Example. The categories $\mathbf{Gp}$ of groups, $\mathbf{Top}$ of topological spaces, $\mathbf{Ring}$ of rings, and $\mathbf{Mod}_R$ of $R$ -modules are concrete in an obvious way. The category $\mathbf{Sh}(X)$ of sheaves on a site $X$ with enough points is concrete by mapping a sheaf to the disjoint union of its stalks (the same holds for any Grothendieck topos, but a different argument is needed). Similarly, the category $\mathbf{Sch}$ of schemes can be concretised by sending $(X,\mathcal O_X)$ to $\coprod_{x \in X} \mathcal P(\mathcal O_{X,x})$ , where $\mathcal P$ is the contravariant power set functor.

Today we will study the relationship between monomorphisms and injections in $\mathscr C$ :

Lemma. Let $(\mathscr C,U)$ be a concrete category, and let $f \colon A \to B$ be a morphism in $\mathscr C$ . If $Uf$ is a monomorphism (resp. epimorphism), then so is $f$ .

Proof. A morphism $f \colon A \to B$ in $\mathscr C$ is a monomorphism if and only if the induced map $\Mor_{\mathscr C}(-,A) \to \Mor_{\mathscr C}(-,B)$ is injective. Faithfulness implies that the vertical maps in the commutative diagram

$\begin{array}{ccc} \Mor_{\mathscr C}(-,A) & \to & \Mor_{\mathscr C}(-,B) \\ \downarrow & & \downarrow \\ \Mor_{\mathbf{Set}}(U-,UA) & \to & \Mor_{\mathbf{Set}}(U-,UB) \end{array}$

are injective, hence if the bottom map is injective so is the top. The statement about epimorphisms follows dually. $\qedsymbol$

For example, this says that any injection of groups is a monomorphism, and any surjection of rings is an epimorphism, since the monomorphisms (epimorphisms) in $\mathbf{Set}$ are exactly the injections (surjections).

In some concrete categories, these are the only monomorphisms and epimorphisms. For example:

Lemma. Let $(\mathscr C,U)$ be a concrete category such that the forgetful functor $U$ admits a left (right) adjoint. Then every monomorphism (epimorphism) in $\mathscr C$ is injective (surjective).

Proof. If $U$ is a right adjoint, it preserves limits. But $f \colon A \to B$ is a monomorphism if and only if the square

$\begin{array}{ccc} A & \overset{\text{id}}\to & A \\ \!\!\!\!\!{\scriptsize \text{id}}\downarrow & & \downarrow {\scriptsize f}\!\!\!\!\! \\ A & \underset{f}\to & B \end{array}$

is a pullback. Thus, $U$ preserves monomorphisms if it preserves limits. The statement about epimorphisms is dual. $\qedsymbol$

For example, the forgetful functors on algebraic categories like $\mathbf{Gp}$ , $\mathbf{Ring}$ , and $\mathbf{Mod}_R$ have left adjoints (a free functor), so all monomorphisms are injective.

The forgetful functor $\mathbf{Top} \to \mathbf{Set}$ has adjoints on both sides: the left adjoint is given by the discrete topology, and the right adjoint by the indiscrete topology. Thus, monomorphisms and epimorphisms in $\mathbf{Top}$ are exactly injections and surjections, respectively.

On the other hand, in the category $\mathbf{Haus}$ of Hausdorff topological spaces, the inclusion $\mathbf Q \hookrightarrow \mathbf R$ is an epimorphism that is not surjective. Indeed, a map $f \colon \mathbf R \to X$ to a Hausdorff space $X$ is determined by its values on $\mathbf Q$ .

Classification of compact objects in Top

Posted on 29 December 2017 by Remy

In my previous post, I showed that compact objects in the category of topological spaces have to be finite. Today we improve this to a full characterisation.

Lemma. Let $X$ be a topological space. Then $X$ is a compact object in $\operatorname{\underline{Top}}$ if and only if $X$ is finite discrete.

This result dates back to Gabriel and Ulmer [GU71, 6.4], as was pointed out to me by Jiří Rosický in reply to my MO question and answer of this account (of which this post is essentially a retelling). Our proof is different from the one given in [GU71], instead using a variant of an argument given in the n-Lab.

Before giving the proof, we construct an auxiliary space against which we will be testing compactness. It is essentially the colimit constructed in the n-Lab, except that we swapped the roles of $0$ and $1$ (the reason for this will become clear in the proof).

Definition. For all $n \in \mathbb N$ , let $X_n$ be the topological space $\mathbb N_{\geq n} \times \{0,1\}$ , where the nonempty open sets are given by $U_{n,m} = \mathbb N_{\geq m} \times \{0\} \cup \mathbb N_{\geq n} \times \{1\}$ for $m \geq n$ . They form a topology since

$\begin{align*} U_{n,m_1} \cap U_{n,m_2} &= U_{n, \max(m_1,m_2)}, \\ \bigcup_i U_{n,m_i} &= U_{n,\min\{m_i\}}. \end{align*}$

Define the map $f_n \colon X_n \to X_{n+1}$ by

$(x,\varepsilon) \mapsto \left\{\begin{array}{ll} (x,\varepsilon), & x > n, \\ (n+1,\varepsilon), & x = n. \end{array}\right.$

This is continuous since $f_n^{-1}(U_{n+1,m})$ equals $U_{n,m}$ if $m > n+1$ and $U_{n,n}$ if $m = n+1$ . Let $X_\infty$ be the colimit of this diagram.

Since the elements $(x,\varepsilon), (y,\varepsilon) \in X_n$ map to the same element in $X_{\max(x,y)}$ , we conclude that $X_\infty$ is the two-point space $\{0,1\}$ , where the map $X_n \to X_\infty = \{0,1\}$ is the second coordinate projection. Moreover, the colimit topology on $\{0,1\}$ is the indiscrete topology. Indeed, neither $\mathbb N_{\geq n} \times \{0\} \subseteq X_n$ nor $\mathbb N_{\geq n} \times \{1\} \subseteq X_n$ are open.

Proof of Lemma. If $X$ is compact, then my previous post shows that $X$ is finite. Let $U \subseteq X$ be any subset, and let $f \colon X \to X_\infty = \{0,1\}$ be the indicator function $\mathbb I_U$ . It is continuous because $X_\infty$ has the indiscrete topology. Since $X$ is a compact object, $f$ has to factor through some $g \colon X \to X_n$ . Let $h \colon X \to X_n \to \N_{\geq n}$ be the first coordinate projection, i.e.

$g(x) = \left\{\begin{array}{ll}(h(x),1), & x \in U, \\ (h(x),0), & x \not\in U. \end{array}\right.$

Let $m \in \N_{\geq n}$ be a number such that $m > h(x)$ for all $x \not\in U$ ; this exists because $X$ is finite. Then $g^{-1}(U_{n,m}) = U$ , which shows that $U$ is open. Since $U$ was arbitrary, we conclude that $X$ is discrete.

Conversely, every finite discrete space $X$ is a compact object. Indeed, any map out of $X$ is continuous, and finite sets are compact in $\operatorname{\underline{Set}}$ . $\qedsymbol$

[GU71] Gabriel, Peter and Ulmer, Friedrich, Lokal präsentierbare Kategorien. Lecture Notes in Mathematics 221. Springer-Verlag, Berlin-New York, 1971. DOI: 10.1007/BFb0059396.

A fun example of a representable functor

Posted on 3 December 2017 by Remy

This post is about representable functors:

Definition. Let $F \colon \mathscr C \to \Set$ be a functor. Then $F$ is representable if it is isomorphic to $\Hom(A,-)$ for some $A \in \ob \mathscr C$ . In this case, we say that $A$ represents $F$ .

Exercise. If such $A$ exists, then it is unique up to unique isomorphism.

Really one should encode the isomorphism $\Hom(A,-) \stackrel\sim\to F$ as well, but this is often dropped from the notation. By the Yoneda lemma, every natural transformation $\Hom(A,-) \to F$ is uniquely determined by the element of $F(A)$ corresponding to the identity of $A$ .

When $\Hom(A,-) \to F$ is a natural isomorphism, the corresponding element $a \in F(A)$ is called the universal object of $F$ . It has the property that for every $B \in \mathscr C$ and any $b \in F(B)$ , there exists a unique morphism $f \colon A \to B$ such that $(Ff)(a) = b$ .

Example. The forgetful functor $\Ab \to \Set$ is represented by $\Z$ . Indeed, the natural map

$\begin{align*} \Hom(\Z,M) &\to M\\ f &\mapsto f(1) \end{align*}$

is an isomorphism. The universal element is $1 \in \Z$ .

Example. Similarly, the forgetful functor $\Ring \to \Set$ is represented by $\Z[x]$ . The universal element is $x$ .

A fun exercise (for the rest of your life!) is to see whether functors you encounter in your work are representable. See for example this post about some more geometric examples.

The main example for today is the following:

Lemma. The functor $\Top\op \to \Set$ that associates to a topological space $(X,\mathcal T_X)$ its topology $\mathcal T_X$ is representable.

Proof. Consider the topological space $Y = \{0,1\}$ with topology $\{\varnothing, \{1\},\{0,1\}\}$ . Then there is a natural map

$\begin{align*} \Hom(X,Y) &\to \mathcal T_X\\ f &\mapsto f^{-1}(\{1\}). \end{align*}$

Conversely, given an open set $U$ , we can associate the characteristic function $\mathbb I_U$ . This gives an inverse of the map above. $\qedsymbol$

The space $Y$ we constructed is called the Sierpiński space. The universal open set is $\{1\}$ .

Remark. The space $Y^I$ represents the data of open sets $U_i$ for $i \in I$ : for any continuous map $f \colon X \to Y^I$ , we have $U_i = f^{-1}(Y_i)$ , where $Y_i = \pi_i^{-1}(\{1\}) \subseteq Y^I$ . If $Z_i$ denotes the complementary open, then the $U_i$ form a cover of $X$ if and only if $\bigcap_{i \in I} Z_i = \varnothing$ . This corresponds to the statement that $f$ lands in $Y^I\setminus\{(0,0,\ldots)\}$ .

Thus, the open cover $Y^I\setminus\{0\} = \bigcup_{i \in I} Y_i$ is the universal open cover, i.e. for every open covering $X = \bigcup U_i$ there exists a unique continuous map $f \colon X \to Y^I\setminus\{0\}$ such that $U_i = f^{-1}(Y_i)$ .

Cardinality of fraction field

Posted on 24 June 2017 by Remy

This is a ridiculous lemma that I came up with.

Lemma. Let $R$ be a (commutative) ring, and let $K$ be its total ring of fractions. Then $R$ and $K$ have the same cardinality.

Proof. If $R$ is finite, my previous post shows that $R = K$ . If $R$ is infinite, then $K$ is a subquotient of $R^2$ , hence $|K| \leq |R^2| = |R|$ . But $R$ injects into $K$ , so $|R| \leq |K|$ . $\qedsymbol$