# 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 comes equipped with various operations on its power set . For instance, there are the maps (interior), (closure), and (complement). These interact with each other in nontrivial ways; for instance .

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

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

Proof. The relations , , and are clear, and conjugating the first by shows that is already implied by these. Note also that and are monotone, and for all . A straightforward induction shows that if and are words in and , then . We conclude that

so (this is the well-known fact that is a regular open set). Conjugating by also gives the relation (saying that is a regular closed set).

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

To show that all 14 differ, one has to construct, for any in the list above, a set in some topological space such that . In fact we will construct a single set in some topological space where all 14 sets differ.

Call the sets for the noncomplementary sets obtained from , and their complements the complementary sets. By the arguments above, the noncomplementary sets always satisfy the following inclusions:
It suffices to show that the noncomplementary sets are pairwise distinct: this forces (otherwise ), so each noncomplementary set contains and therefore cannot agree with a complementary set.

For our counterexample, consider the 5 element poset given by

and let be the disjoint union of (the Alexandroff topology on , see the previous post) with a two-point indiscrete space . Recall that the open sets in are the upwards closed ones and the closed sets the downward closed ones. Let . Then the diagram of inclusions becomes We see that all 7 noncomplementary sets defined by are pairwise distinct.

Remark. Steen and Seebach [SS, Example 32(9)] give a different example where all 14 differ, namely a suitable subset . 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 needs at least 6 points. We claim that 6 is not possible either:

Lemma. Let be a finite topological space, and any subset. Then and .

But in a 6-element counterexample , the diagram of inclusions shows that any point occurs as the difference for some . Since each of and is either open or closed, we see that the naive constructible topology on is discrete, so is by the remark from the previous post. So our lemma shows that cannot be a counterexample.

Proof of Lemma. We will show that ; the reverse implication was already shown, and the result for follows by replacing with its complement.

In the previous post, we saw that is the Alexandroff topology on some finite poset . If is any nonempty subset, it contains a maximal element , and since is a poset this means for all . (In a preorder, you would only get .)

The closure of a subset is the lower set , and the interior is the upper set . So we need to show that if and , then .

By definition of , we get , i.e. there exists with . Choose a maximal with this property; then we claim that is a maximal element in . Indeed, if , then so , meaning that there exists with . Then and , which by definition of means . Thus is maximal in , hence since and . From we conclude that , finishing the proof.

The lemma fails for non- spaces, as we saw in the example above. More succinctly, if is indiscrete and , then and . The problem is that is maximal, but and .

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 be a topological space. Then the specialisation preorder on (the underlying set of) is the relation if and only if .

Note that it is indeed a preorder: clearly , and if and , then , so , showing . We denote this preorder by .

Note that the relation is usually denoted in algebraic geometry, which is pronounced “ specialises to ”.

Definition. Given a preorder , the Alexandroff topology on is the topology whose opens are the cosieves, i.e. the upwards closed sets (meaning and implies ).

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 for any . We denote the set with its Alexandroff topology by .

Likewise, the closed sets in are the sieves (or downwards closed sets); for instance the principal sieves . The closure of is the sieve generated by ; for instance the closure of a singleton is the principal sieve .

Theorem. Let be the functor , and the functor .

1. Let be a preorder, a topological space, and a function. Then is a monotone function if and only if is a continuous function .
2. The functors and are adjoint: .
3. The composition is equal (not just isomorphic!) to the identity functor.
4. The restriction of to the category of finite topological spaces is equal to the identity functor.
5. If is a topological space, then is if and only if is a poset.
6. If is a preorder, then is a poset if and only if is .
7. The functors and give rise to adjoint equivalences

Proof. (1) Suppose is monotone, let be a closed subset, and let . Suppose and . Since is monotone and is closed, we get , i.e. . We conclude that , so is downward closed, hence closed in .

Conversely, suppose is continuous, and suppose in . Then , so by continuity we get , so .

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

is a bijection.

(3) Since , we conclude that if and only if , so the specialisation preorder on is the original preorder on .

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

of closed subsets of . Thus any closed subset of is closed in , so the topologies agree.

(5) The relations and mean and . This is equivalent to the statement that a closed subset contains if and only if it contains . The result follows since a poset is a preorder where the first statement only happens if , and a space is a space where the second statement only happens if .

(6) Follows from (5) applied to since by (3).

(7) The equivalence follows from (3) and (4), and the equivalence then follows from (5) and (6).

Example. The Alexandroff topology on the poset is the Sierpiński space with topology . As explained in this post, continuous maps from a topological space to are in bijection with open subsets , where is sent to (and to the indicator function ).

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

These correspond to 4 possible preorder relations , sitting in the following diagram (where vertical arrows indicate inclusion top to bottom):

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 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 is a Hausdorff space, then the specialisation preorder is just the equality relation , 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 .

Remark. On any topological space , we can define the naive constructible topology as the topology with a base given by locally closed sets for open and closed. In the Alexandroff topology, a base for this topology is given by the locally closed sets : indeed these sets are clearly naive constructible, and any set of the form for upward closed and downward closed has the property .

Thus, if 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 is .

# 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 , write for the poset . The full subcategory of on these is denoted , the simplex category. Concretely, it has objects for all , and morphisms

A simplicial set is a functor . This can be described rather concretely using the objects and the face and degeneracy maps between them; see e.g. Tag 0169. The category of simplicial sets is usually denoted , , or (in analogy with cosimplicial sets ).

The representable simplicial set is usually denoted or . Then the Yoneda lemma shows that the functor given by is represented by , i.e.

Definition. The geometric realisation functor is defined as follows: for , the geometric realisation is the standard -simplex

(If no confusion arises, it may also be denoted .) This is functorial in : for a map (equivalently, by the Yoneda lemma, a map ) we get a continuous map by

For an arbitrary simplicial set , write

where the transition map corresponding to a map over is defined via

This is functorial in , and when it coindices with the previous definition because the identity is terminal in the index category.

Remark. In a fancier language, is the left Kan extension of the functor along the Yoneda embedding . (Those of you familiar with presheaves on spaces will recognise the similarity with the definition of for 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 horn in as the union of the images of the maps coming from the face maps for . Since geometric realisation preserves colimits (alternatively, stare at the definitions), we see that the geometric realisation of is obtained in the same way from the maps , so it is the -simplex with its interior and face opposite the vertex removed.

The geometric realisation is a good first approximation for thinking about a simplicial set. However, when thinking about -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 -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 be a set endowed with the cofinite topology, and assume is path connected. Then is contractible.

The assumption is for example satisfied when , for then any injection is a path from to . 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 is finite, for then both are equivalent to . Thus we may assume that is infinite. Choose a path from some to some . This induces a continuous map . Choose a bijection

and extend to a map by and for all . Then is continuous: the preimage of is if , and if , both of which are closed. Thus is a homotopy from to the constant map , hence a contraction.

I would love to see an animation of this contraction as goes from to … I find especially the slightly more direct argument for given here elusive yet somehow strangely visual.

Remark. If is countable (still with the cofinite topology), then is path connected if and only if . In the finite case this is clear (because then 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 and , if such cardinalities exist. See this MO question for some results. In particular, it is consistent with ZFC that the smallest cardinality for which is path connected is strictly smaller than .

# 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 of sets, write for the small category with

and morphisms

for and (where ), with composition induced by composition of maps .

Note that by the Yoneda lemma, this category is isomorphic (not just equivalent!) to , where is the Yoneda embedding. Indeed, are in bijection with natural transformations , and morphisms correspond to a morphism rendering commutative the associated diagram

Example 1. If , then a diagram is a pair of sets with parallel arrows . Then looks like a ‘bipartite preorder’ where every source object has outgoing valence :

Example 2. Given a set , write for the discrete category on , i.e. and

If is itself a discrete category, then is just a collection of sets, and

Remark. Giving a functor is the same thing as giving functors and natural transformations

of functors for all in , such that

for all in (where denotes horizontal composition of natural transformations, as in Tag 003G).

Example 3.  Let be a small category, and consider the diagram given by the source and target maps . Then we have a functor

given on objects by

and on morphisms by

In terms of the remark above, it is given by the functors taking to and the natural inclusion , along with the natural transformations

We can now formulate the main result.

Lemma. Let be a small category. Then the functor of Example 3 is cofinal.

Recall that a functor is cofinal if for all , the comma category is nonemptry and connected. See also Tag 04E6 for a concrete translation of this definition.

Proof. Let . Since , the identity gives the object in , showing nonemptyness. For connectedness, it suffices to connect any (i.e. ) to the identity ) (i.e. ). If , then the commutative diagram

gives a zigzag

of morphisms in connecting to . If instead , we can skip the first step, and the diagram

gives a zigzag

connecting to .

Corollary 1. Let be a small diagram in a category with small products. Then there is a canonical isomorphism

provided that either side exists.

Proof. By the lemma, the functor

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

is an isomorphism if either side exists. But is a category as in Example 1, and it’s easy to see that the limit over a diagram is computed as the equaliser of a pair of arrows between the products.

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 is of the form for some . But it’s fun to move the argument almost entirely away from limits and into the index category.

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

# Application of Schur orthogonality

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

1.

2.

Proof. First consider the case . 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.

Here is a trivial consequence:

Corollary. Let be a positive integer, and let . Then

Proof 1. Without loss of generality, has exact order . Set , let , and note that

Part 1 of the lemma gives the result.

Proof 2. Set as before, let be the homomorphism , and the homomorphism . Then part 1 of the lemma does not give the result, but part 2 does.

In fact, the corollary also implies the lemma, because both are true ().

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

Lemma. Let be a graph. Then there exists an -colouring on such that for every graph and every -colouring on , there is a unique morphism such that .

Proof. By this post, we have the adjunction

(1)

In particular, the identity gives an -colouring under this adjunction. If is any other graph, (1) gives a bijection between morphisms and -colourings of , which by naturality of (1) is given by .

Corollary. To prove Hedetniemi’s conjecture, it suffices to treat the ‘universal’ case , for every and every loopless graph .

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

(2)

Then there exists an -colouring , so the lemma gives a map such that . This forces since an -colouring on induces an -colouring on by pullback. Thus, (2) implies

showing that is a counterexample as well.

Corollary. Hedetniemi’s conjecture is equivalent to the statement that for any loopless graph and any , either or admits an -colouring.

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

• If does not have a -colouring, then it has an edge. Then has no edges by construction, since has no edges. See also Example 2 of this post.
• If does not have a -colouring, then it has an odd cycle . We need to produce a -colouring on . Choose identifications and with adjacencies . Consider the map

To show this is a graph homomorphism, we must show that for adjacent we have . If two maps are adjacent, then for adjacent we have . Taking shows that , so

since is odd.

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

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 with colours is a graph homomorphism . The chromatic number of is the smallest positive integer such that admits a colouring with colours.

Note that if has a loop, then it cannot admit a colouring with any number of colours. In the loopless case, a trivial upper bound is , since is a subgraph of the complete graph on .

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

Conjecture (Hedetniemi). Let and be graphs. Then

Remark. Note that : if is a colouring, then the composition is a colouring of , and similarly for . Thus, it remains to rule out with and .

Example. The case where is easy to check:

• If and , then both and have an edge, hence so does . Then .
• If and , then both and contain an odd cycle. If has an -cycle and an -cycle with and odd, then these give morphisms and . Wrapping around (resp. ) times gives morphisms , , hence to the product: . Thus, does not admit a -colouring since doesn’t.

Thus, if , then .

# 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 and be graphs. Then the graph has vertices , and an edge from to if and only if implies (where we allow as usual).

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

In other words, is the internal Hom in the symmetric monoidal category .

Proof. There is a bijection

So it suffices to show that is a graph homomorphism if and only if is. The condition that is a graph homomorphism means that for any , the functions have the property that implies . This is equivalent to for all and all . By the construction of the product graph , this is exactly the condition that is a graph homomorphism.

Because the symmetric monoidal structure on is given by the categorical product, it is customary to refer to the internal as the exponential graph .

Example 1. Let be the discrete graph on a set . Then is the complete graph with loops on the set . Indeed, the condition for two functions to be adjacent is vacuous since has no edges.

In particular, any function is a graph homomorphism. Under the adjunction above, this corresponds to the fact that any function is a graph homomorphism, since is a discrete graph.

Example 2. Conversely, is discrete as soon as has an edge, and complete with loops otherwise. Indeed, the condition

can only be satisfied if , and in that case is true for all and .

In particular, a function is a graph homomorphism if and only if either or has no edges. Under the adjunction above, this corresponds to the fact that a function is a graph homomorphism to if and only if has no edges, which means either or has no edges.

Example 3. Let be the discrete graph on a set with loops at every point. Then is the -fold power of . Indeed, the condition that two functions are adjacent is that for all , which means exactly that for each of the projections .

In particular, graph homomorphisms correspond to giving graph homomorphisms . Under the adjunction above, this corresponds to the fact that a graph homomorphism is the same thing as graph homomorphisms , since is the -fold disjoint union of .

Example 4. Let be the terminal graph consisting of a single point with a loop (note that we used instead for in this earlier post). The observation above that also works the other way around: . Then the adjunction gives

This is actually true in any symmetric monoidal category with internal hom and identity object . We conclude that a function is a graph homomorphism if and only if has a loop at . This is also immediately seen from the definition: has a loop at if and only if implies .

Example 5. Let and be the complete graphs on and vertices respectively. Then has as vertices all -tuples , and an edge from to if and only if when . For example, for we get an edge between and if and only if and .

# Internal Hom

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

Definition. Let be a symmetric monoidal category, i.e. a category with a functor that is associative, unital, and commutative up to natural isomorphism. Then an internal Hom in is a functor

such that is a left adjoint to for any , i.e. there are functorial isomorphisms

Remark. In the easiest examples, we typically think of as ‘upgrading to an object of ‘:

Example. Let be a commutative ring, and let be the category of -modules, with the tensor product. Then with its natural -module structure is an internal Hom, by the usual tensor-Hom adjunction:

The same is true when is the category of -bimodules for a not necessarily commutative ring .

However, we cannot do this for left -modules over a noncommutative ring, because there is no natural -module structure on for left -modules and . In general, the tensor product takes an -bimodule and a -bimodule and produces an -bimodule . Taking gives a way to tensor a right -module with a left -module, but there is no standard way to tensor two left -modules, let alone equip it with the structure of a left -module.

Example. Let . Then is naturally a set, making it into an internal Hom for :

When is the categorical product , the internal (if it exists) is usually called an exponential object, in analogy with the case above.

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

Example. An example of a slightly different nature is chain complexes: let be a commutative ring, and let be the category of cochain complexes

of -modules (meaning each is an -module, and the are -linear maps satisfying ). Homomorphisms are commutative diagrams

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 with the structure of a chain complex’, but there is an internal Hom given by

with differentials given by

Then we get for example

since a morphism is given by an element such that , i.e. , meaning that is a morphism of cochain complexes.

Example. The final example for today is presheaves and sheaves. If is a topological space, then the category of abelian sheaves on has an internal Hom given by

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