The 14 closure operations

I’ve been getting complaints that my lemmas have not been so lovely (or little) lately, so let’s do something a bit more down to earth. This is a story I learned from the book Counterexamples in topology by Steen and Seebach [SS].

A topological space X comes equipped with various operations on its power set \mathcal P(X). For instance, there are the maps S \mapsto S^\circ (interior), S \mapsto \bar S (closure), and S \mapsto S^{\text{c}} (complement). These interact with each other in nontrivial ways; for instance (\bar S)^{\text{c}} = (S^{\text{c}})^\circ.

Consider the monoid M generated by the symbols a (interior), b (closure), and c (complement), where two words in a, b, and c are identified if they induce the same action on subsets of an arbitrary topological space X.

Lemma. The monoid M has 14 elements, and is the monoid given by generators and relations

    \[M = \left\langle a,b,c\ \left|\ \begin{array}{cc} a^2=a, & (ab)^2=ab, \\ c^2=1, & cac=b.\end{array}\right.\right\rangle.\]

Proof. The relations a^2 = a, c^2=1, and cac=b are clear, and conjugating the first by c shows that b^2=b is already implied by these. Note also that a and b are monotone, and a(T) \subseteq T \subseteq b(T) for all T \subseteq X. A straightforward induction shows that if v and w are words in a and b, then vaw(S) \subseteq vw(S) \subseteq vbw(S). We conclude that

    \[abab(S) \subseteq abb(S) = ab(S) = aab(S) \subseteq abab(S),\]

so (ab)^2=ab (this is the well-known fact that ab(S) is a regular open set). Conjugating by c also gives the relation (ba)^2 = ba (saying that ba(S) is a regular closed set).

Thus, in any reduced word in M, no two consecutive letters agree because of the relations a^2=a, b^2=b, and c^2=1. Moreover, we may assume all occurrences of c are at the start of the word, using ac=cb and bc=ca. In particular, there is at most one c in the word, and removing that if necessary gives a word containing only a and b. But reduced words in a and b have length at most 3, as the letters have to alternate and no string abab or baba can occur. We conclude that M is covered by the 14 elements

    \[\begin{array}{ccccccc}1, & a, & b, & ab, & ba, & aba, & bab,\\c, & ca, & cb, & cab, & cba, & caba, & cbab. \end{array}\]

To show that all 14 differ, one has to construct, for any i\neq j in the list above, a set S_{i,j} \subseteq X_{i,j} in some topological space X_{i,j} such that i(S_{i,j}) \neq j(S_{i,j}). In fact we will construct a single set S \subseteq X in some topological space X where all 14 sets i(S) differ.

Call the sets i(S) for i \in \langle a,b\rangle the noncomplementary sets obtained from S, and their complements the complementary sets. By the arguments above, the noncomplementary sets always satisfy the following inclusions:
Inclusions between different setsIt suffices to show that the noncomplementary sets are pairwise distinct: this forces a(S) \neq \varnothing (otherwise a(S) = ba(S)), so each noncomplementary set contains a(S) and therefore cannot agree with a complementary set.

For our counterexample, consider the 5 element poset P given by

    \[\begin{array}{ccccc}p\!\!\! & & & & \!\!\!q \\ \uparrow\!\!\! & & & & \!\!\!\uparrow \\ r\!\!\! & & & & \!\!\!s \\ & \!\!\!\nwarrow\!\!\! & & \!\!\!\nearrow\!\!\! & \\ & & \!\!\!t,\!\!\!\!\! & & \end{array}\]

and let X be the disjoint union of P^{\operatorname{Alex}} (the Alexandroff topology on P, see the previous post) with a two-point indiscrete space \{u,v\}. Recall that the open sets in P^{\operatorname{Alex}} are the upwards closed ones and the closed sets the downward closed ones. Let S = \{p,s,u\}. Then the diagram of inclusions becomes Lattice of inclusions for the exampleWe see that all 7 noncomplementary sets defined by S are pairwise distinct. \qedsymbol

Remark. Steen and Seebach [SS, Example 32(9)] give a different example where all 14 differ, namely a suitable subset S \subseteq \mathbf R. That is probably a more familiar type of example than the one I gave above.

On the other hand, my example is minimal: the diagram of inclusions above shows that for all inclusions to be strict, the space X needs at least 6 points. We claim that 6 is not possible either:

Lemma. Let X be a finite T_0 topological space, and S \subseteq X any subset. Then aba(S) = ab(S) and bab(S) = ba(S).

But in a 6-element counterexample X, the diagram of inclusions shows that any point occurs as the difference i(S) \setminus j(S) for some i,j \in \langle a,b\rangle\setminus 1. Since each of i(S) and j(S) is either open or closed, we see that the naive constructible topology on X is discrete, so X is T_0 by the remark from the previous post. So our lemma shows that X cannot be a counterexample.

Proof of Lemma. We will show that ab(S) \subseteq aba(S); the reverse implication was already shown, and the result for bab(S) follows by replacing S with its complement.

In the previous post, we saw that X is the Alexandroff topology on some finite poset (X,\leq). If T \subseteq X is any nonempty subset, it contains a maximal element t, and since X is a poset this means u \geq t \Rightarrow u=t for all u \in T. (In a preorder, you would only get u \geq t \Rightarrow u \leq t.)

The closure of a subset T \subseteq X is the lower set \bigcup_{t \in T} X_{\leq t}, and the interior is the upper set \{t \in T\ |\ X_{\geq t} \subseteq T\}. So we need to show that if x \in ab(S) and y \geq x, then y \in ba(S).

By definition of ab(S), we get y \in b(S), i.e. there exists z \in S with z \geq y. Choose a maximal z with this property; then we claim that z is a maximal element in X. Indeed, if u \geq z, then u \geq x so u \in b(S), meaning that there exists v \in S with v \geq u. Then v \geq z \geq y and v \in S, which by definition of z means v=z. Thus z is maximal in X, hence z \in a(S) since z \in S and X_{\geq z} = \{z\}. From z \geq y we conclude that y \in ba(S), finishing the proof. \qedsymbol

The lemma fails for non-T_0 spaces, as we saw in the example above. More succinctly, if X = \{x,y\} is indiscrete and S = \{x\}, then aba(S) = \varnothing and ab(S) = X. The problem is that x is maximal, but X_{\geq x} \supsetneq \{x\} and x \not\in a(S).

References.

[SS] L.A. Steen, J.A. Seebach, Counterexamples in Topology. Reprint of the second (1978) edition. Dover Publications, Inc., Mineola, NY, 1995.

Finite topological spaces

One of my favourite bits of point set topology is messing around with easy topological spaces. What could be easier than finite topological spaces? The main result (below) is that the category of finite topological spaces is equivalent to the category of finite preorders.

Recall (e.g. from algebraic geometry) the following definition:

Definition. Let X be a topological space. Then the specialisation preorder on (the underlying set of) X is the relation x \leq y if and only if x \in \overline{\{y\}}.

Note that it is indeed a preorder: clearly x \leq x, and if x \leq y and y \leq z, then \{y\} \subseteq \overline{\{z\}}, so x \in \overline{\{y\}} \subseteq \overline{\{z\}}, showing x \leq z. We denote this preorder by X^{\operatorname{sp}}.

Note that the relation x \leq y is usually denoted y \rightsquigarrow x in algebraic geometry, which is pronounced “y specialises to x”.

Definition. Given a preorder (X,\leq), the Alexandroff topology on X is the topology whose opens U \subseteq X are the cosieves, i.e. the upwards closed sets (meaning x \in U and x \leq y implies y \in U).

To see that this defines a topology, note that an arbitrary (possibly empty) union or intersection of cosieves is a cosieve. A subbase for the topology is given by the principal cosieves X_{\geq x} = \{y \in X\ |\ y \geq x\} for any x \in X. We denote the set X with its Alexandroff topology by X^{\operatorname{Alex}}.

Likewise, the closed sets in X are the sieves (or downwards closed sets); for instance the principal sieves X_{\leq x} = \{y \in X\ |\ y \leq x\}. The closure of S \subseteq X is the sieve X_{\leq S} = \bigcup_{s \in S} X_{\leq s} generated by S; for instance the closure of a singleton \{x\} is the principal sieve X_{\leq x}.

Theorem. Let F \colon \mathbf{PreOrd} \to \mathbf{Top} be the functor X \mapsto X^{\operatorname{Alex}}, and G \colon \mathbf{Top} \to \mathbf{PreOrd} the functor Y \mapsto Y^{\operatorname{sp}}.

  1. Let (X,\leq) be a preorder, Y a topological space, and f \colon X \to Y a function. Then f is a monotone function X \to Y^{\operatorname{sp}} if and only if f is a continuous function X^{\operatorname{Alex}} \to Y.
  2. The functors F and G are adjoint: F \dashv G.
  3. The composition GF \colon \mathbf{PreOrd} \to \mathbf{PreOrd} is equal (not just isomorphic!) to the identity functor.
  4. The restriction of FG \colon \mathbf{Top} \to \mathbf{Top} to the category \mathbf{Top}^{\operatorname{fin}} of finite topological spaces is equal to the identity functor.
  5. If Y is a topological space, then Y is T_0 if and only if Y^{\operatorname{sp}} is a poset.
  6. If (X,\leq) is a preorder, then X is a poset if and only if X^{\operatorname{Alex}} is T_0.
  7. The functors F and G give rise to adjoint equivalences

        \begin{align*}F\!:\mathbf{PreOrd}^{\operatorname{fin}} &\leftrightarrows \mathbf{Top}^{\operatorname{fin}}:\!G \\F\!:\mathbf{Pos}^{\operatorname{fin}} &\leftrightarrows \mathbf{Top}^{\operatorname{fin}}_{T_0}:\!G.\end{align*}

Proof. (1) Suppose f \colon X \to Y^{\operatorname{sp}} is monotone, let Z \subseteq Y be a closed subset, and let W = f^{-1}(Z). Suppose b \in W and a \leq b. Since f is monotone and Z is closed, we get f(a) \leq f(b), i.e. f(a) \in \overline{\{f(b)\}} \subseteq Z. We conclude that a \in W, so W is downward closed, hence closed in X^{\operatorname{Alex}}.

Conversely, suppose f \colon X^{\operatorname{Alex}} \to Y is continuous, and suppose a \leq b in X. Then a \in \overline{\{b\}}, so by continuity we get f(a) \in f\left(\overline{\{b\}}\right) \subseteq \overline{\{f(b)\}}, so f(a) \leq f(b).

(2) This is a restatement of (1): the map

    \begin{align*}\operatorname{Hom}_{\mathbf{PreOrd}}\big(X,G(Y)\big) &\stackrel\sim\to \operatorname{Hom}_{\mathbf{Top}}\big(F(X),Y\big) \\f &\mapsto f\end{align*}

is a bijection.

(3) Since \overline{\{x\}} = X_{\leq x}, we conclude that y \in \overline{\{x\}} if and only if y \leq x, so the specialisation preorder on X^{\operatorname{Alex}} is the original preorder on X.

(4) In general, the counit FG(Y) \to Y is a continuous map on the same underlying space, so FG(Y) is finer than Y. Conversely, suppose Z \subseteq FG(Y) is closed, i.e. Z is a sieve for the specialisation preorder on Y. This means that if y \in Z, then x \in \overline{\{y\}} implies x \in Z; in other words \overline{\{y\}} \subseteq Z. If Y and therefore Z is finite, there are finitely many such y, so Z is the finite union

    \[Z = \bigcup_{y \in Z} \overline{\{y\}}\]

of closed subsets of Y. Thus any closed subset of FG(Y) is closed in Y, so the topologies agree.

(5) The relations x \leq y and y \leq x mean x \in \overline{\{y\}} and y \in \overline{\{x\}}. This is equivalent to the statement that a closed subset Z \subseteq Y contains x if and only if it contains y. The result follows since a poset is a preorder where the first statement only happens if x = y, and a T_0 space is a space where the second statement only happens if x = y.

(6) Follows from (5) applied to Y = F(X) since X = G(Y) by (3).

(7) The equivalence \mathbf{PreOrd}^{\operatorname{fin}} \leftrightarrows \mathbf{Top}^{\operatorname{fin}} follows from (3) and (4), and the equivalence \mathbf{Pos}^{\operatorname{fin}} \leftrightarrows \mathbf{Top}^{\operatorname{fin}}_{T_0} then follows from (5) and (6). \qedsymbol

Example. The Alexandroff topology on the poset [1] = \{0 \leq 1\} is the Sierpiński space S = \{0,1\} with topology \{\varnothing, \{1\}, S\}. As explained in this post, continuous maps X \to S from a topological space X to S are in bijection with open subsets U \subseteq X, where f \colon X \to S is sent to f^{-1}(1) \subseteq X (and U \subseteq X to the indicator function \mathbf 1_U \colon X \to S).

Example. Let X = \{x,y\} be a set with two elements. There are 4 possible topologies on X, sitting in the following diagram (where vertical arrows indicate inclusion bottom to top):

    \[{\arraycolsep=-1em\begin{array}{ccccc} & & \{\varnothing,\{x\},\{y\},X\} & & \\ & \ \ / & & \backslash\ \  & \\ \{\varnothing,\{x\},X\} & & & & \{\varnothing,\{y\},X\} \\ & \ \ \backslash & & /\ \  & \\ & & \{\varnothing,X\}.\! & & \end{array}}\]

These correspond to 4 possible preorder relations \{(a,b)\ |\ a \leq b\} \subseteq X\times X, sitting in the following diagram (where vertical arrows indicate inclusion top to bottom):

    \[{\arraycolsep=-1.5em\begin{array}{ccccc} & & \{(x,x),(y,y)\} & & \\ & \ \ / & & \backslash\ \ & \\ \{(x,x),(x,y),(y,y)\} & & & & \{(x,x),(y,x),(y,y)\} \\ & \ \ \backslash & & /\ \ & \\ & & \{(x,x),(x,y),(y,x),(y,y)\}.\!\! & & \end{array}}\]

We see that finer topologies (more opens) have stronger relations (fewer inequalities).

Example. The statement in (4) is false for infinite topological spaces. For instance, if Y is the Zariski topology on a curve, then any set of closed points is downwards closed, but it is only closed if it’s finite. Or if Y is a Hausdorff space, then the specialisation preorder is just the equality relation \Delta_Y \subseteq Y \times Y, whose Alexandroff topology is the discrete topology.

I find the examples useful for remembering which way the adjunction goes: topological spaces generally have fewer opens than Alexandroff topologies on posets, so the continuous map should go X^{\operatorname{Alex}} \to Y.

Remark. On any topological space X, we can define the naive constructible topology as the topology with a base given by locally closed sets U \cap Z for U \subseteq X open and Z \subseteq X closed. In the Alexandroff topology, a base for this topology is given by the locally closed sets X_{\lessgtr x} := X_{\geq x} \cap X_{\leq x}: indeed these sets are clearly naive constructible, and any set of the form S = U \cap Z for U upward closed and Z downward closed has the property x \in S \Rightarrow X_{\lessgtr x} \subseteq S.

Thus, if X is the Alexandroff topology on a preorder, we see that the naive constructible topology is discrete if and only if the preorder is a poset, i.e. if and only if X is T_0.

Simplicial sets

A few weeks ago, I finally struck up the courage to take some baby steps reading Lurie’s Higher topos theory. In a series of posts mostly written for my own benefit, I will untangle some of the basic definitions and provide some easy examples. The first one is one I was already somewhat familiar with: simplicial sets.

Definition. For each n \in \mathbf N, write [n] for the poset 0 \leq \ldots \leq n. The full subcategory of \mathbf{Poset} on these [n] is denoted \Delta, the simplex category. Concretely, it has objects [n] for all n \in \mathbf N, and morphisms

    \[\operatorname{Hom}\big([m],[n]\big) = \left\{f \colon [m] \to [n]\ \Big|\ i \leq j \Rightarrow f(i) \leq f(j)\right\}.\]

A simplicial set is a functor X \colon \Delta^{\operatorname{op}} \to \mathbf{Set}. This can be described rather concretely using the objects X_n = X([n]) and the face and degeneracy maps between them; see e.g. Tag 0169. The category of simplicial sets is usually denoted [\Delta^{\operatorname{op}}, \mathbf{Set}], \mathbf{sSet}, or \mathbf{Set}_{\Delta} (in analogy with cosimplicial sets \mathbf{Set}^\Delta = [\Delta,\mathbf{Set}]).

The representable simplicial set \operatorname{Hom}(-,[n]) is usually denoted \Delta^n or \Delta[n]. Then the Yoneda lemma shows that the functor \mathbf{sSet} \to \mathbf{Set} given by X \mapsto X_n is represented by \Delta^n, i.e.

    \[X_n = \operatorname{Hom}_{\mathbf{sSet}}\big(\Delta^n,X).\]

Definition. The geometric realisation functor | \cdot | \colon \mathbf{sSet} \to \mathbf{Top} is defined as follows: for \Delta^n, the geometric realisation |\Delta^n| is the standard n-simplex

    \[|\Delta^n| := \left\{(x_0,\ldots,x_n) \in \mathbf R^{n+1}\ \Bigg|\ x_i \geq 0, \sum_{i=0}^n x_i = 1\right\} \subseteq \mathbf R^{n+1}.\]

(If no confusion arises, it may also be denoted \Delta^n.) This is functorial in [n]: for a map a \colon [m] \to [n] (equivalently, by the Yoneda lemma, a map a \colon \Delta^m \to \Delta^n) we get a continuous map a \colon |\Delta^m| \to |\Delta^n| by

    \[a(x_0,\ldots,x_m)_j = \sum_{i \in a^{-1}(j)} x_i.\]

For an arbitrary simplicial set X, write

    \[|X| := \underset{\Delta^n \to X}{\operatorname{colim}}\ |\Delta^n|,\]

where the transition map |\Delta^m| \to |\Delta^n| corresponding to a map \Delta^m \to \Delta^n over X is defined via

    \[\operatorname{Hom}_{\mathbf{sSet}}\big(\Delta^m,\Delta^n\big) \stackrel\sim\leftarrow \operatorname{Hom}_\Delta\big([m],[n]\big) \to \operatorname{Hom}_{\mathbf{Top}}\big(|\Delta^m|,|\Delta^n|\big).\]

This is functorial in X, and when X = \Delta^n it coindices with the previous definition because the identity \Delta^n \to \Delta^n is terminal in the index category.

Remark. In a fancier language, | \cdot | is the left Kan extension of the functor [n] \mapsto |\Delta^n| along the Yoneda embedding \Delta \to \mathbf{sSet}. (Those of you familiar with presheaves on spaces will recognise the similarity with the definition of f^{-1}\mathscr F for f \colon X \to Y a continuous map of topological spaces, which is another example of a left Kan extension.)

Remark. It is a formal consequence of the definitions that geometric realisation preserves arbitrary colimits (“colimits commute with colimits”). This also follows because it is a left adjoint to the singular set functor, but we won’t explore this here.

Wisdom. The most geometric way to think about a simplicial set is through its geometric realisation.

For example, we can define the i^{\text{th}} horn \Lambda_i^n in \Delta^n as the union of the images of the maps \Delta^{n-1} \to \Delta^n coming from the face maps \delta^j_n \colon [n-1] \to [n] for j \neq i. Since geometric realisation preserves colimits (alternatively, stare at the definitions), we see that the geometric realisation of \Lambda^i_n is obtained in the same way from the maps |\Delta^{n-1}| \to |\Delta^n|, so it is the n-simplex with its interior and face opposite the i^{\text{th}} vertex removed.

The geometric realisation is a good first approximation for thinking about a simplicial set. However, when thinking about \infty-categories (e.g. in the next few posts), this is actually not the way you want to think about a simplicial set. Indeed, homotopy of simplicial sets (equivalently their geometric realisations) is stronger than equivalence of \infty-categories. (More details later, hopefully.)

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

Note that by the Yoneda lemma, this category is isomorphic (not just equivalent!) to (h \downarrow D)^{\operatorname{op}}, where h \colon \mathcal I^{\operatorname{op}} \to [\mathcal I,\mathbf{Set}] is the Yoneda embedding. Indeed, a_i \in D(i) are in bijection with natural transformations h_i = \operatorname{Mor}_{\mathcal I}(i,-) \to D, and morphisms a_i \to b_j correspond to a morphism f \colon i \to j rendering commutative the associated diagram

    \[\begin{array}{ccccc}h_j\!\!\!\! & & \!\!\!\!\!\!\stackrel{- \circ f}\longrightarrow\!\!\!\!\!\! & & \!\!\!\!h_i \\ & \!\!\!\!\searrow\!\!\!\!\!\!\!\! & & \!\!\!\!\!\!\!\!\swarrow\!\!\!\! \\ & & D.\! & & \end{array}\]

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. Then 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}(\mathcal I)} D(i) \rightrightarrows \prod_{f \in \operatorname{ar}(\mathcal 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.