A strange contractible space

Here’s a strange phenomenon that I ran into when writing a MathOverflow answer a few years ago.

Lemma. Let X be a set endowed with the cofinite topology, and assume X is path connected. Then X is contractible.

The assumption is for example satisfied when |X| \geq |\mathbf R|, for then any injection f \colon [0,1] \hookrightarrow X is a path from x_0 = f(0) to x_1 = f(1). Path connectedness of cofinite spaces is related to partitioning the interval into disjoint closed subsets; see the remark below for some bounds on the cardinalities.

Proof. The result is trivial if X is finite, for then both are equivalent to |X| = 1. Thus we may assume that X is infinite. Choose a path f \colon [0,1] \to X from some x_0 = f(0) to some x_1 = f(1) \neq x_0. This induces a continuous map [0,1] \times X \to X \times X. Choose a bijection

    \[g \colon (X \setminus \{x_0,x_1\}) \times X \stackrel \sim\to X,\]

and extend to a map \bar g \colon X \times X \to X by g(x_0,x) = x and g(x_1,x) = x_1 for all x \in X. Then \bar g is continuous: the preimage of x \in X is g^{-1}(x) \cup (x_0,x) if x \neq x_1, and g^{-1}(x) \cup (x_0,x) \cup x \times X if x = x_1, both of which are closed. Thus \bar g \circ (f \times \mathbf 1_X) is a homotopy from \mathbf 1_X to the constant map x_1, hence a contraction. \qedsymbol

I would love to see an animation of this contraction as t goes from 0 to 1… I find especially the slightly more direct argument for |X| \geq |\mathbf R| given here elusive yet somehow strangely visual.

Remark. If X is countable (still with the cofinite topology), then X is path connected if and only if |X| = 1. In the finite case this is clear (because then X is discrete), and in the infinite case this is a result of Sierpiński. See for example this MO answer of Timothy Gowers for an easy argument.

There’s also some study of path connectedness of cofinite topological spaces of cardinality strictly between \aleph_0 = |\mathbf N| and \mathfrak c = |\mathbf R|, if such cardinalities exist. See this MO question for some results. In particular, it is consistent with ZFC that the smallest cardinality for which X is path connected is strictly smaller than \mathfrak c.

Limits as equalisers of products

The first and second corollary below are well-known category theory lemmas. We give a slightly different argument than usual (i.e. we took a trivial result and changed it into something much more complicated).

Here is a lovely little definition:

Definition. Given a small diagram D \colon \mathcal I \to \mathbf{Set} of sets, write \bigcup D for the small category with

    \[\operatorname{ob}\left( \bigcup D \right) = \bigcup_{i \in \operatorname{ob} \mathcal I} D(i),\]

and morphisms

    \[\operatorname{Mor}\big(a_i,b_j\big) = \left\{f \in \operatorname{Mor}(i,j)\ \Big|\ D(f)(a_i) = b_j\right\}\]

for a_i \in D(i) and b_j \in D(j) (where i, j \in \operatorname{ob} \mathcal I), with composition induced by composition of maps D(i) \to D(j).

Example 1. If \mathcal I = (\bullet \rightrightarrows \bullet), then a diagram D is a pair of sets S, T with parallel arrows f, g \colon S \rightrightarrows T. Then \bigcup D looks like a ‘bipartite preorder’ where every source object has outgoing valence 2:

    \[\begin{array}{ccc}s_1 & \to & t_1 \\ & \searrow\!\!\!\!\!\!\nearrow & \\ s_2 & & t_2 \\ & \searrow & \\ \vdots & & \vdots \end{array}\]

Example 2. Given a set S, write S^{\operatorname{disc}} for the discrete category on S, i.e. \operatorname{ob}(S^{\operatorname{disc}}) = S and

    \[\operatorname{Mor}(a,b) = \begin{cases}\{\mathbf{1}_a\}, & a = b, \\ \varnothing, & \text{else}.\end{cases}\]

If \mathcal I = I^{\operatorname{disc}} is itself a discrete category, then D is just a collection \mathbf S = \{S_i\ |\ i \in I\} of sets, and

    \[\bigcup D = \left(\bigcup \mathbf S\right)^{\operatorname{disc}}.\]

Remark. Giving a functor F \colon \bigcup D \to \mathscr C is the same thing as giving functors F(i) \colon D(i)^{\operatorname{disc}} \to \mathscr C and natural transformations

    \[F(f) \colon F(i) \to F(j) \circ D(f)^{\operatorname{disc}}\]

of functors D(i)^{\operatorname{disc}} \to \mathscr C for all f \colon i \to j in \mathcal I, such that

    \[F(g \circ f) = \left(F(g) \star \mathbf 1_{D(f)^{\operatorname{disc}}}\right) \circ F(f)\]

for all i \stackrel f\to j \stackrel g\to k in \mathcal I (where \star denotes horizontal composition of natural transformations, as in Tag 003G).

Example 3.  Let \mathcal I be a small category, and consider the diagram D_{\mathcal I} \colon (\bullet \rightrightarrows \bullet) \to \mathbf{Set} given by the source and target maps s, t \colon \operatorname{ar}(\mathcal I) \rightrightarrows \operatorname{ob}(\mathcal I). Then we have a functor

    \[F \colon \bigcup D_{\mathcal I} \to \mathcal I\]

given on objects by

    \begin{align*} \big(f \in \operatorname{ar}(\mathcal I)\big) &\mapsto s(f),\\ \big(i \in \operatorname{ob}(\mathcal I)\big) &\mapsto i \end{align*}

and on morphisms by

    \begin{align*} \big(s \colon f \to s(f)\big) &\mapsto \mathbf 1_{s(f)},\\ \big(t \colon f \to t(f)\big) &\mapsto f. \end{align*}

In terms of the remark above, it is given by the functors F(\operatorname{ar}) \colon \operatorname{ar}(\mathcal I)^{\operatorname{disc}} \to \mathcal I taking f to s(f) and the natural inclusion F(\operatorname{ob}) \colon \operatorname{ob}(\mathcal I)^{\operatorname{disc}} \to \mathcal I, along with the natural transformations

    \begin{align*} F(s)(f) = \mathbf 1_{s(f)} \colon F(\operatorname{ar})(f) &\to F(\operatorname{ob})(s(f)) \\ F(t)(f) = f \colon F(\operatorname{ar})(f) &\to F(\operatorname{ob})(t(f)). \end{align*}

We can now formulate the main result.

Lemma. Let \mathcal I be a small category. hen the functor F \colon \bigcup D_{\mathcal I} \to \mathcal I of Example 3 is cofinal.

Recall that a functor F \colon \mathcal J \to \mathcal I is cofinal if for all i \in \mathcal I, the comma category (i \downarrow F) is nonemptry and connected. See also Tag 04E6 for a concrete translation of this definition.

Proof. Let i \in \operatorname{ob}(\mathcal I). Since F(i) = i, the identity i \to F(i) gives the object (i,\mathbf 1_i) in (i \downarrow F), showing nonemptyness. For connectedness, it suffices to connect any (x,f) (i.e. f \colon i \to F(x)) to the identity (i, \mathbf 1_i) (i.e. \mathbf 1_i \colon i \to F(i)). If x \in \operatorname{ar}(\mathcal I), then the commutative diagram

    \[\begin{array}{ccccccc}i & = & i & = & i & = & i \\ \!\!\!\!\!{\tiny f}\downarrow & & \!\!\!\!\!\!\!\!{\tiny xf}\downarrow & & || & & || \\ s(x) & \overset x\to & t(x) & \overset{xf}\leftarrow & i & = & i \\ || & & || & & || & & || \\ F(x) & \underset{F(t)}\to & F(t(x)) & \underset{F(t)}\leftarrow & F(xf) & \underset{F(s)}\to & F(i) \end{array}\]

gives a zigzag

    \[(x,f) \stackrel t\to (t(x),xf) \stackrel t\leftarrow (xf,\mathbf 1_i) \stackrel s\to (i,\mathbf 1_i)\]

of morphisms in (i \downarrow F) connecting (x,f) to (i,\mathbf 1_i). If instead x \in \operatorname{ob}(\mathcal I), we can skip the first step, and the diagram

    \[\begin{array}{ccccccc} i & = & i & = & i \\ \!\!\!\!\!\!{\tiny f}\downarrow & & || & & || \\ x & \overset{f}\leftarrow & i & = & i \\ || & & || & & || \\ F(x) & \underset{F(t)}\leftarrow & F(f) & \underset{F(s)}\to & F(i) \end{array}\]

gives a zigzag

    \[(x,f) \stackrel t\leftarrow (f,\mathbf 1_i) \stackrel s\to (i,\mathbf 1_i)\]

connecting (x,f) to (i,\mathbf 1_i). \qedsymbol

Corollary 1. Let D \colon \mathcal I^{\operatorname{op}} \to \mathscr C be a small diagram in a category \mathscr C with small products. Then there is a canonical isomorphism

    \[\lim_{\leftarrow} D = \operatorname{Eq}\left( \prod_{i \in \operatorname{ob}(\mathscr I)} D(i) \rightrightarrows \prod_{f \in \operatorname{ar}(\mathscr I)} D(s(i)) \right),\]

provided that either side exists.

Proof. By the lemma, the functor

    \[F \colon \left(\bigcup D_{\mathcal I}\right)^{\operatorname{op}} \to \mathcal I^{\operatorname{op}}\]

is initial. Hence by Tag 002R, the natural morphism

    \[\lim_{\leftarrow} D \to \lim_{\leftarrow} D \circ F\]

is an isomorphism if either side exists. But \left(\bigcup D_{\mathcal I}\right)^{\operatorname{op}} is a category as in Example 1, and it’s easy to see that the limit over a diagram \left(\bigcup D_{\mathcal I}\right)^{\operatorname{op}} \to \mathscr C is computed as the equaliser of a pair of arrows between the products. \qedsymbol

Of course this is not an improvement of the traditional proof, because the “it’s easy to see” step at the end is very close to the same statement as the corollary in the special case where \mathcal I is of the form \bigcup D for some D \colon (\bullet \rightrightarrows \bullet) \to \mathbf{Set}. But it’s fun to move the argument almost entirely away from limits and into the index category.

Corollary 2. Let \mathscr C be a category that has small products and equalisers of parallel pairs of arrows. Then \mathscr C is (small) complete. \qedsymbol

Application of Schur orthogonality

The post that made me google ‘latex does not exist’.

Lemma. Let \epsilon be a finite group of order \Sigma, and write \equiv for the set of irreducible characters of \epsilon. Then

  1.     \[\forall (,) \in \epsilon : \hspace{1em} \sum_{\Xi \in \equiv} \Xi(()\overline\Xi()) = \begin{cases}|C_\epsilon(()|, & \exists \varepsilon \in \epsilon: (\varepsilon = \varepsilon), \\ 0, & \text{else}.\end{cases}\]

  2.     \[\forall \Xi,\underline\Xi \in \equiv : \hspace{1em} \Sigma^{-1}\sum_{\text O)) \in \epsilon} \Xi(\text O)))\overline{\underline\Xi}(\text O))) = \begin{cases}1, & \Xi = \underline\Xi,\\ 0, &\text{else}.\end{cases}\]

Proof. First consider the case \epsilon = 1. This is just an example; it could also be something much better. Then the second statement is obvious, and the first is left as an exercise to the reader. The general case is similar. \qedsymbol

Here is a trivial consequence:

Corollary. Let \mathbf R be a positive integer, and let f \in \mathbf C^\times[\mathbf R] \setminus \{1\}. Then

    \[\sum_{X = 1}^{\mathbf R} f^X = 0.\]

Proof 1. Without loss of generality, f has exact order \mathbf R > 1. Set \epsilon = \mathbf Z/\mathbf {RZ}, let ((,)) = (1,0) \in \epsilon^2, and note that

    \[\nexists \varepsilon \in \epsilon : (\varepsilon = \varepsilon).\]

Part 1 of the lemma gives the result. \qedsymbol

Proof 2. Set \epsilon = \mathbf Z/\mathbf {RZ} as before, let \Xi \colon \epsilon \to \mathbf C^\times be the homomorphism \varepsilon \mapsto f^{3\varepsilon}, and \underline \Xi \colon \epsilon \to \mathbf C^\times the homomorphism \varepsilon \mapsto f^{2\varepsilon}. Then part 1 of the lemma does not give the result, but part 2 does. \qedsymbol

In fact, the corollary also implies the lemma, because both are true (\mathbf 1 \Rightarrow \mathbf 1).

Graph colourings and Hedetniemi’s conjecture II: universal colouring

In my previous post, I stated the recently disproved Hedetniemi’s conjecture on colourings of product graphs (see this post for my conventions on graphs). In the next few posts, I will explain some of the ideas of the proof from an algebraic geometer’s perspective.

Today we will start with the universal colouring on G \times \mathbf{Hom}(G, K_n).

Lemma. Let G be a graph. Then there exists an n-colouring \phi_{\operatorname{univ}} on G \times \mathbf{Hom}(G, K_n) such that for every graph H and every n-colouring \phi on G \times H, there is a unique morphism f \colon H \to \mathbf{Hom}(G, K_n) such that f^*\phi_{\operatorname{univ}} = \phi.

Proof. By this post, we have the adjunction

(1)   \[\operatorname{Hom}(G \times H, K_n) \cong \operatorname{Hom}(H, \mathbf{Hom}(G, K_n)).\]

In particular, the identity \mathbf{Hom}(G,K_n) \to \mathbf{Hom}(G,K_n) gives an n-colouring \phi_{\operatorname{univ}} \colon G \times \mathbf{Hom}(G, K_n) \to K_n under this adjunction. If H is any other graph, (1) gives a bijection between morphisms H \to \mathbf{Hom}(G, K_n) and n-colourings of G \times H, which by naturality of (1) is given by f \mapsto f^* \phi_{\operatorname{univ}} := \phi_{\operatorname{univ}} \circ (\operatorname{id}_G \times f). \qedsymbol

Corollary. To prove Hedetniemi’s conjecture, it suffices to treat the ‘universal’ case H = \mathbf{Hom}(G,K_n), for every n and every loopless graph G.

Proof. Suppose by contradiction that there is a counterexample (G,H), i.e. there are loopless graphs G and H such that

(2)   \[n = \chi(G \times H) < \min(\chi(G), \chi(H)).\]

Then there exists an n-colouring \phi \colon G \times H \to K_n, so the lemma gives a map f \colon H \to \mathbf{Hom}(G,K_n) such that \phi = f^*\phi_{\operatorname{univ}}. This forces \chi(H) \leq \chi(\mathbf{Hom}(G,K_n)) since an m-colouring on \mathbf{Hom}(G,K_n) induces an m-colouring on H by pullback. Thus, (2) implies

    \[\chi(G \times \mathbf{Hom}(G,K_n)) \leq n < \min(\chi(G),\chi(H)) \leq \min(\chi(G), \chi(\mathbf{Hom}(G,K_n))),\]

showing that (G,\mathbf{Hom}(G,K_n)) is a counterexample as well. \qedsymbol

Corollary. Hedetniemi’s conjecture is equivalent to the statement that for any loopless graph G and any n \in \mathbf Z_{>0}, either G or \mathbf{Hom}(G,K_n) admits an n-colouring. \qedsymbol

Example. By the final example of my previous post and the proof of the first corollary above, the cases n \leq 2 are trivially true. We can also check this by hand:

  • If G does not have a 1-colouring, then it has an edge. Then \mathbf{Hom}(G,K_1) has no edges by construction, since K_1 has no edges. See also Example 2 of this post.
  • If G does not have a 2-colouring, then it has an odd cycle C_m \subseteq G. We need to produce a 2-colouring on \mathbf{Hom}(G,K_2). Choose identifications V(K_2) \cong \mathbf Z/2 and V(C_m) \cong \mathbf Z/m with adjacencies \{i,i+1\}. Consider the map

        \begin{align*}\Sigma \colon \mathbf{Hom}(G,K_2) &\to K_2\\f &\mapsto \sum_{c \in C_m} f(c) \in \mathbf Z/2.\end{align*}

    To show this is a graph homomorphism, we must show that for adjacent f, g we have \Sigma(f) \neq \Sigma(g). If two maps f, g \colon G \to K_2 are adjacent, then for adjacent x, y \in G we have f(x) \neq g(y). Taking (x,y) = (c_i, c_{i+1}) shows that f(c_i) = g(c_{i+1}) + 1, so

        \[\Sigma(f) = \sum_{i = 1}^m f(c_i) = \sum_{i=1}^m \Big(g(c_{i+1}) + 1 \Big) = \Sigma(g)  + 1 \in \mathbf Z/2,\]

    since m is odd. \qedsymbol

The case n = 3 is treated in [EZS85], which seems to be one of the first places where the internal Hom of graphs appears (in the specific setting of \mathbf{Hom}(-,K_n)).


References.

[EZS85] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4. Combinatorica 5.2, p. 121–126 (1985).

Graph colourings and Hedetniemi’s conjecture I: statement of conjecture

The past three posts have been building up to the statement of the recently disproved Hedetniemi’s conjecture. I wanted to make an attempt to write about this, because from a first reading the main ideas of the counterexample seemed very familiar to an algebraic geometer. (More about this in a future post, hopefully.)

Definition. A colouring of a loopless graph G with n colours is a graph homomorphism G \to K_n. The chromatic number \chi(G) of G is the smallest positive integer n such that G admits a colouring with n colours.

Note that if G has a loop, then it cannot admit a colouring with any number of colours. In the loopless case, a trivial upper bound is \chi(G) \leq \# V(G), since G is a subgraph of the complete graph on V(G).

Example. We have \chi(G) = 1 if and only if G has no edges (we say that G is discrete), and \chi(G) \leq 2 if and only if G contains no odd cycles (we say that G is bipartite). Indeed, if you try to produce a 2-colouring by colouring adjacent vertices opposite colours, either this produces a 2-colouring or you find an odd cycle.

Conjecture (Hedetniemi). Let G and H be graphs. Then

    \[\chi(G \times H) = \min(\chi(G), \chi(H)).\]

Remark. Note that \chi(G \times H) \leq \min(\chi(G), \chi(H)): if G \to K_n is a colouring, then the composition G \times H \to G \to K_n is a colouring of G \times H, and similarly for H. Thus, it remains to rule out \chi(G \times H) = n with \chi(G) > n and \chi(H) > n.

Example. The case where \chi(G \times H) \leq 2 is easy to check:

  • If \chi(G) > 1 and \chi(H) > 1, then both G and H have an edge, hence so does G \times H. Then \chi(G \times H) > 1.
  • If \chi(G) > 2 and \chi(H) > 2, then both G and H contain an odd cycle. If G has an n-cycle and H an m-cycle with n and m odd, then these give morphisms C_n \to G and C_m \to H. Wrapping around m (resp. n) times gives morphisms C_{mn} \to G, C_{mn} \to H, hence to the product: C_{mn} \to G \times H. Thus, G \times H does not admit a 2-colouring since C_{mn} doesn’t.

Thus, if \chi(G \times H) \leq 2, then \chi(G \times H) = \min(\chi(G), \chi(H)).

Internal Hom in the category of graphs

In this earlier post, I described what products in the category of graphs look like. In my previous post, I gave some basic examples of internal Hom. Today we will combine these and describe the internal Hom in the category of graphs.

Definition. Let G and H be graphs. Then the graph \mathbf{Hom}(G, H) has vertices \operatorname{Map}(V(G), V(H)), and an edge from f \colon V(G) \to V(H) to g \colon V(G) \to V(H) if and only if \{x,y\} \in E(G) implies \{f(x), g(y)\} \in E(H) (where we allow x = y as usual).

Lemma. If G, H, and K are graphs, then there is a natural isomorphism

    \[\operatorname{Hom}(G \times H, K) \stackrel\sim\to \operatorname{Hom}(G, \mathbf{Hom}(H, K)).\]

In other words, \mathbf{Hom}(H,K) is the internal Hom in the symmetric monoidal category (\mathbf{Grph}, \times).

Proof. There is a bijection

    \begin{align*}\alpha \colon \operatorname{Map}(V(G), V(\mathbf{Hom}(H, K))) &\stackrel\sim\to \operatorname{Map}(V(G \times H), V(K))\\\phi &\mapsto \bigg((g,h) \mapsto \phi(g)(h)\bigg).\end{align*}

So it suffices to show that \phi is a graph homomorphism if and only if \psi = \alpha(\phi) is. The condition that \phi is a graph homomorphism means that for any \{x,y\} \in E(G), the functions \phi(x), \phi(y) \colon V(H) \to V(K) have the property that \{a,b\} \in E(H) implies \{\phi(x)(a), \phi(y)(b)\} \in E(K). This is equivalent to \{\psi(x,a),\psi(y,b)\} \in E(K) for all \{x,y\} \in E(G) and all \{a,b\} \in E(H). By the construction of the product graph G \times H, this is exactly the condition that \psi is a graph homomorphism. \qedsymbol

Because the symmetric monoidal structure on \mathbf{Grph} is given by the categorical product, it is customary to refer to the internal \mathbf{Hom}(G,H) as the exponential graph H^G.

Example 1. Let S^{\operatorname{disc}} be the discrete graph on a set S. Then \mathbf{Hom}(S^{\operatorname{disc}}, K) is the complete graph with loops on the set V(K)^S. Indeed, the condition for two functions f, g \colon S \to V(K) to be adjacent is vacuous since S^{\operatorname{disc}} has no edges.

In particular, any function V(G) \to V(\mathbf{Hom}(S^{\operatorname{disc}}, K)) is a graph homomorphism. Under the adjunction above, this corresponds to the fact that any function V(G \times S^{\operatorname{disc}}) \to V(H) is a graph homomorphism, since G \times S^{\operatorname{disc}} is a discrete graph.

Example 2. Conversely, \mathbf{Hom}(H, S^{\operatorname{disc}}) is discrete as soon as H has an edge, and complete with loops otherwise. Indeed, the condition

    \[\{x,y\} \in E(H) \Rightarrow \{f(x),g(y)\} \in E(S^{\operatorname{disc}}) = \varnothing\]

can only be satisfied if E(H) = \varnothing, and in that case is true for all f and g.

In particular, a function V(G) \to V(\mathbf{Hom}(H, S^{\operatorname{disc}})) is a graph homomorphism if and only if either G or H has no edges. Under the adjunction above, this corresponds to the fact that a function V(G \times H) \to S is a graph homomorphism to S^{\operatorname{disc}} if and only if G \times H has no edges, which means either G or H has no edges.

Example 3. Let S^{\operatorname{loop}} be the discrete graph on a set S with loops at every point. Then \mathbf{Hom}(S^{\operatorname{loop}}, K) = K^S is the S-fold power of K. Indeed, the condition that two functions f, g \colon S \to V(K) are adjacent is that \{f(s), g(s)\} \in E(K) for all s \in S, which means exactly that \{\pi_s(f), \pi_s(g)\} \in E(K) for each of the projections \pi_s \colon K^S \to K.

In particular, graph homomorphisms f \colon G \to \mathbf{Hom}(S^{\operatorname{loop}}, K) correspond to giving S graph homomorphisms f_s \colon G \to K. Under the adjunction above, this corresponds to the fact that a graph homomorphism g \colon G \times S^{\operatorname{loop}} \to K is the same thing as S graph homomorphisms g_s \colon G \to K, since G \times S^{\operatorname{loop}} is the S-fold disjoint union of G.

Example 4. Let * = \{\operatorname{pt}\}^{\operatorname{loop}} be the terminal graph consisting of a single point with a loop (note that we used * instead for \{\operatorname{pt}\}^{\operatorname{disc}} in this earlier post). The observation above that G \times * \cong G also works the other way around: * \times G \cong G. Then the adjunction gives

    \[\operatorname{Hom}(G, K) \cong \operatorname{Hom}(*, \mathbf{Hom}(G,K)).\]

This is actually true in any symmetric monoidal category with internal hom and identity object *. We conclude that a function f \colon V(G) \to V(K) is a graph homomorphism if and only if \mathbf{Hom}(G, K) has a loop at f. This is also immediately seen from the definition: \mathbf{Hom}(G, K) has a loop at f if and only if \{x,y\} \in E(G) implies \{f(x), f(y)\} \in E(H).

Example 5. Let K_n and K_m be the complete graphs on n and m vertices respectively. Then \mathbf{Hom}(K_n, K_m) has as vertices all n-tuples (a_1,\ldots,a_n) \in \{1,\ldots,m\}^n, and an edge from (a_1,\ldots,a_n) to (b_1,\ldots,b_n) if and only if a_i \neq b_j when i \neq j. For example, for n = 2 we get an edge between (a_1, a_2) and (b_1, b_2) if and only if a_1 \neq b_2 and a_2 \neq b_1.

Internal Hom


This is an introductory post about some easy examples of internal Hom.

Definition. Let (\mathscr C, \otimes) be a symmetric monoidal category, i.e. a category \mathscr C with a functor \otimes \colon \mathscr C \times \mathscr C \to \mathscr C that is associative, unital, and commutative up to natural isomorphism. Then an internal Hom in \mathscr C is a functor

    \[\mathbf{Hom}(-,-) \colon \mathscr C\op \times \mathscr C \to \mathscr C\]

such that -\otimes Y is a left adjoint to \mathbf{Hom}(Y,-) for any Y \in \mathscr C, i.e. there are functorial isomorphisms

    \[\operatorname{Hom}(X \otimes Y, Z) \stackrel\sim\to \operatorname{Hom}(X, \mathbf{Hom}(Y,Z)).\]

Remark. In the easiest examples, we typically think of \mathbf{Hom}(Y,Z) as ‘upgrading \operatorname{Hom}(Y,Z) to an object of \mathscr C‘:

Example. Let R be a commutative ring, and let \mathscr C = \mathbf{Mod}_R be the category of R-modules, with \otimes the tensor product. Then \mathbf{Hom}(M,N) = \operatorname{Hom}_R(M,N) with its natural R-module structure is an internal Hom, by the usual tensor-Hom adjunction:

    \[\operatorname{Hom}_R(M \otimes_R N, K) \cong \operatorname{Hom}_R(M, \mathbf{Hom}(N, K)).\]

The same is true when \mathscr C =\!\ _R\mathbf{Mod}_R is the category of (R,R)-bimodules for a not necessarily commutative ring R.

However, we cannot do this for left R-modules over a noncommutative ring, because there is no natural R-module structure on \operatorname{Hom}_R(M,N) for left R-modules M and N. In general, the tensor product takes an (A,B)-bimodule M and a (B,C)-bimodule N and produces an (A,C)-bimodule M \otimes_B N. Taking A = C = \mathbf Z gives a way to tensor a right R-module with a left R-module, but there is no standard way to tensor two left R-modules, let alone equip it with the structure of a left R-module.

Example. Let \mathscr C = \mathbf{Set}. Then \mathbf{Hom}(X,Y) = \operatorname{Hom}(X,Y) = Y^X is naturally a set, making it into an internal Hom for (\mathscr C, \times):

    \[\operatorname{Hom}(X \times Y, Z) \stackrel\sim\to \operatorname{Hom}(X, \mathbf{Hom}(Y,Z)).\]

When \otimes is the categorical product \times, the internal \mathbf{Hom}(X,Y) (if it exists) is usually called an exponential object, in analogy with the case \mathscr C = \mathbf{Set} above.

Example. Another example of exponential objects is from topology. Let \mathscr C = \mathbf{Haus} be the category of locally compact Hausdorff topological spaces. Then the compact-open topology makes \mathbf{Hom}(X,Y) := Y^X into an internal Hom of topological spaces. (There are mild generalisations of this beyond the compact Hausdorff case, but for an arbitrary topological space X the functor - \times X does not preserve colimits and hence cannot admit a right adjoint.)

Example. An example of a slightly different nature is chain complexes: let R be a commutative ring, and let \mathscr C = \mathbf{Ch}(\mathbf{Mod}_R) be the category of cochain complexes

    \[\ldots \to C^{i-1} \to C^i \to C^{i+1} \to \ldots\]

of R-modules (meaning each C^i is an R-module, and the d^i \colon C^i \to C^{i+1} are R-linear maps satisfying d \circ d = 0). Homomorphisms f \colon C \to D are commutative diagrams

    \[\begin{array}{ccccccc}\ldots & \to & C^i & \to & C^{i+1} & \to & \ldots \\ & & \!\!\!\!\! f^i\downarrow & & \downarrow f^{i+1}\!\!\!\!\!\!\! & & \\ \ldots & \to & D^i & \to & D^{i+1} & \to & \ldots,\!\!\end{array}\]

and the tensor product is given by the direct sum totalisation of the double complex of componentwise tensor products.

There isn’t a natural way to ‘endow \operatorname{Hom}(C, D) with the structure of a chain complex’, but there is an internal Hom given by

    \[\mathbf{Hom}(C, D)^i = \prod_{m \in \mathbf Z} \operatorname{Hom}(C_m, D_{m+i}),\]

with differentials given by

    \[d^if = d_D f - (-1)^i f d_C.\]

Then we get for example

    \[\operatorname{Hom}(R[0], \mathbf{Hom}(C, D)) \cong \operatorname{Hom}(C, D),\]

since a morphism R[0] \to \mathbf{Hom}(C, D) is given by an element f \in \mathbf{Hom}(C, D)^0 such that df = 0, i.e. d_Df = f d_C, meaning that f is a morphism of cochain complexes.

Example. The final example for today is presheaves and sheaves. If X is a topological space, then the category \mathbf{Ab}(X) of abelian sheaves on X has an internal Hom given by

    \[\mathbf{Hom}(\mathscr F, \mathscr G)(U) = \operatorname{Hom}(\mathscr F|_U, \mathscr G|_U),\]

with the obvious transition maps for inclusions V \subseteq U of open sets. This is usually called the sheaf Hom. A similar statement holds for presheaves.

Limits in the category of graphs

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

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

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.