Category Archives: Abstract nonsense

Graph colourings and Hedetniemi’s conjecture II: universal colouring

Posted on by
Reply

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).

Internal Hom in the category of graphs

Posted on by
Reply

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

Posted on by
3


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

Posted on by
Reply

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.

Epimorphisms of groups

Posted on by
Reply

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 by
Reply

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 by
Reply

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.

Compact objects in the category of topological spaces

Posted on by
Reply

We compare two competing notions of compactness for topological spaces. Besides the usual notion, there is the following:

Definition. Let \mathscr C be a cocomplete category. Then an object X \in \ob \mathscr C is compact if \Hom(X,-) commutes with filtered colimits.

Exercise. An R-module M is compact if and only if it is finitely generated.

We want to study compact objects in the category of topological spaces. One would hope that this corresponds to compact topological spaces. However, this is very far off:

Lemma. Let X \in \Top be a compact object. Then X is finite.

Proof. Let Y be the set X with the indiscrete topology, i.e. \mathcal T_Y = \{\varnothing, Y\}. It is the union of all its finite subsets, and this gives it the colimit topology because a subset U \subseteq Y is open if and only if its intersection with each finite subset is. Indeed, if U were neither \varnothing nor Y, then there exist y_1, y_2 \in Y with y_1 \in U and y_2 \not\in U. But then U \cap \{y_1,y_2\} is not open, because \{y_1,y_2\} inherits the indiscrete topology from Y.

Therefore, if X is a compact object, then the identity map X \to Y factors through one of these finite subsets, hence X is finite. \qedsymbol

However, the converse is not true. In fact the indiscrete space on a two element set is not a compact object, as is explained here.

Corollary. Let X \in \Top be a compact object. Then X is a compact topological space.

Proof. It is finite by the lemma above. Every finite topological space is compact. \qedsymbol

Originally, this post relied on the universal open covering of my previous post to show that a compact object in \Top is compact; however the above proof shows something much stronger.

A fun example of a representable functor

Posted on by
2

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).

Sites without a terminal object

Posted on by
Reply

Let \mathcal C be a site with a terminal object X. Then the cohomology on the site is defined as the derived functors of the global sections functor \Gamma(X,-). But what do we do if the site does not have a terminal object?

The solution is to define H^i(\mathcal C,-) as \Ext{\mathcal O}{i}(\mathcal O,-), where \mathcal O denotes the structure sheaf if \mathcal C is a ringed site. If \mathcal C is not equipped with a ring structure, we take \mathcal O to be the constant sheaf \underline{\mathbb Z}; this makes \mathcal C into a ringed site.

Lemma. Let \mathcal C be a site with a terminal object X. Then the above definitions agree, i.e.

    \[H^i(X,-) = \Ext{\mathcal O}{i}(\mathcal O,-).\]

Proof. Note that \Hom_{\mathcal O}(\mathcal O, \mathscr F) = \Gamma(X, \mathscr F), since any map \mathcal O(X) \to \mathscr F(X) can be uniquely extended to a morphism of (pre)sheaves \mathcal O \to \mathscr F, and conversely every such morphism is determined by its map on global sections. The result now follows since \Ext{\mathcal O}{i}(\mathcal O, -) and H^i(X,-) are defined as the derived functors of \Hom_{\mathcal O}(\mathcal O,-) and \Gamma(X,-) respectively. \qedsymbol

Remark. From this perspective, it seems quite magical that for a sheaf \mathscr F of \mathcal O_X-modules on a ringed space (X,\mathcal O_X), the cohomology groups \Ext{\mathcal O_X}{i}(\mathcal O_X,\mathscr F) and \Ext{\underline{\Z}}{i}(\underline{\Z},\mathscr F) agree. It turns out that this is true in the setting of ringed sites as well; see Tag 03FD.

So why is this useful? Let’s give some examples of sites that do not have a terminal object.

Example. Let G be a group scheme over k. Then we have a stack BG of G-torsors. The objects of BG are pairs (U,P), where U is a k-scheme and P is a G-torsor over U. Morphisms (U,P) \to (U',P') are pairs (f,g) \colon (U,P) \to (U',P') making the diagram

Rendered by QuickLaTeX.com

commutative. This forces the diagram to be a pullback, since all maps between G-torsors are isomorphisms.

The (large) Zariski site on BG is defined by declaring coverings \{(U_i, P_i) \to (U,P)\} to be families such that \{U_i \to U\} is a Zariski covering (and similarly for the étale and fppf sites).

Now does the category BG have a terminal object? This would be a G-torsor P_0 \to U_0 such that every other G-torsor P \to U admits a unique map to it, realising P as the pullback of P_0 along U \to U_0. But this object would exactly be the classifying stack U_0 = BG, which does not exist as a scheme (or algebraic space). The fact that a terminal object does not exist is the whole reason we need to define it as a stack in the first place!

Example. Let X/k be a variety in characteristic p > 0; for simplicity, let’s say k = \mathbb F_p. Then consider the crystalline site of X/\Spec(\Z/p^n\Z). Roughly speaking, its objects are triples (U,T,\delta), where U \to X is an open immersion, U \to T is a thickening with a map to \Spec{\F_p} \to \Spec{\Z/p^n\Z}, and \delta is a divided power structure on the ideal sheaf \mathcal I_U \subseteq \mathcal O_T (with a compatibility condition w.r.t. \Spec{\F_p} \to \Spec{\Z/p^n\Z}). There is a suitable notion of morphisms.

This site does not have a terminal object, basically because there are many thickenings on U = X with the respective compatibilities. (I am admittedly no expert, and it could very well be true that this is not 100% correct. However, I am certain that the crystalline site in general does not have a terminal object.)