I skimmed through books 1, 4, and 5 of my new batch and am currently skimming through 3; it seems I don’t have the mathematical prerequisites to get much out of 2. It will take me a long time to digest all of the interesting things I’ve learned, but I thought I’d discuss an interesting idea coming from Lawvere and Schanuel.

An important idea in mathematics is to reduce an object into its “connected components.” This has various meanings depending on context; it is perhaps clearest in the categories and , and also has a sensible meaning in, for example, for a group . Lawvere and Schanuel suggest the following way to understand several of the examples that occur in practice:

Let be a concrete category with a forgetful functor . If it exists, let be the left adjoint to . Then describes the “discrete” (i.e. “totally disconnected”) objects of , and, if it exists, the left adjoint to is a functor describing the “connected components” of an object in .

I think this is a nice illustration of a construction that is illuminated by the abstract approach, so I’ll briefly describe how this works for a few of my favorite categories.

**Graphs**

The category of – for the sake of simplicity – undirected simple graphs has objects specified by a vertex set and a symmetric reflexive relation called adjacency. Morphisms are functions between vertex sets preserving the edge relation. Now, the intuitive definition of the connected components of a graph is as follows: two vertices of a graph are connected if there is a path between them, i.e. a sequence of edges and vertices satisfying the appropriate incidence relations. Connectedness is an equivalence relation, and the connected components are the equivalence classes of this relation.

From a categorical perspective, though, we want to do everything in terms of the morphisms in . So how should we accomplish this? One answer is surprisingly simple.

**Proposition:** Let be the graph consisting of two vertices and only self-loops. Then the number of connected components of a **finite** graph is the unique non-negative integer such that the number of morphisms is .

The conceptual content of the proof is that any such morphism must be locally constant, since otherwise it could not preserve adjacency, and every locally constant function is a morphism since there is no adjacency relation between distinct components. This construction, however, has the drawback that it only works for graphs with a finite number of components. A better statement that works for all graphs is that the functor sending a graph to the set of its connected components satisfies a natural equivalence

where is a two-element set in . (I know it’s not a great idea to use the same notation for objects in two categories, but I hope it is clear what this means.) In other words, should be left adjoint to the functor which sends a set to the graph with vertex set that set and with no nontrivial edges; this functor sends to .

Here’s how we “come up” with this functor. The “obvious” choice of forgetful functor sends a graph to its vertex set, and its left adjoint is ! Remember that this means there is a natural identification

since any function from to another graph automatically respects adjacency.

**Group actions**

Fix a group . The category has objects consisting of sets equipped with a group action of , i.e. a homomorphism , and its morphisms are the functions between the underlying sets respecting the action of . Again, there is a naive definition of connectedness: two elements are connected if there exists satisfying . The equivalence classes of this relation are just the orbits of the action. Indeed, this relation is symmetric and reflexive and hence embeds into , so we should expect that the above definitions that worked for also work for . Indeed, the forgetful functor sending a group action to its underlying set has a left adjoint sending a set to a group action on which acts trivially, and this functor in turn has a left adjoint sending a group action to its set of orbits.

**Topological spaces**

The category has objects the topological spaces and morphisms continuous functions between them. The definition of connectedness in this category is slightly less transparent than in the above two examples; the standard definition is that a topological space is connected if is not the disjoint union of two open subsets of . Again, there is an equivalence relation relating two points if they lie in a connected subset of , and the equivalence classes of this relation is the standard definition of connected component.

Now let’s talk about morphisms. The forgetful functor sends a topological space to its underlying set of points, and it has a left adjoint sending a set to itself in the discrete topology. Let be the discrete space on two points, i.e. the image of on the two-point set. The preimage of both points must be open and disjoint, and any (ordered) separation of into disjoint open sets gives rise to a continuous function . Again, the point here is that any continuous function into a discrete space must be locally constant. More generally, if has connected components, then the number of continuous functions is . ~~Even more generally, there is a natural identification~~

exactly as in the other cases.

Unfortunately, things get messy in spaces with infinitely many connected components (thanks to DT below for the correction). The issue is that connected components are always closed, but not always open (although they are open if there are finitely many connected components), and the ~~locally constant functions~~ functions constant on each connected component are all continuous if and only if each connected component is clopen. For example, is totally disconnected, but its points aren’t open. According to Wikipedia, connected components are clopen if we pass ~~either to the subcategory of topological spaces which are compact Hausdorff or~~ to the subcategory of topological spaces which are also locally connected, and in these subcategories is a left adjoint to as expected. This is slightly unsatisfying, but the full category of topological spaces is messy like that.

**Generalities**

One way to think about the above adjunction is that the image of in a category describes its subcategory of “discrete objects,” and then is universal for morphisms into discrete objects. Now, since is a right adjoint, it preserves products, in particular the empty product, so it sends the terminal object of to the terminal object of . Since has the special property that all of its elements are coproducts of the terminal object with itself, and since is also a left adjoint, hence preserves coproducts, it follows that we can describe the subcategory of “discrete objects” without any explicit reference to or : it is just the subcategory of all coproducts of the terminal object (assuming they exist).

This works nicely for all of our above examples. The coproduct in all of the categories above is the disjoint union and the terminal object is the singleton. More precisely, in it is the singleton with one self-loop, in it is the singleton with a trivial action of , and in it is the singleton with the only possible topology.

It would be nice if the connected components functor bore a relationship to the decomposition of, say, representations of a group into irreducible representations, but as stated this can’t work. In any category with a zero object, the coproduct of copies of the zero object is just the zero object again, so the zero object is the only discrete object; in other words, every object is “connected.”

on December 27, 2009 at 12:13 am |DTThe topological story has to be more complicated: an infinite product of discrete spaces is not discrete, so the functor T does not preserve infinite products and doesn’t have a left adjoint.

I wonder if there’s anything interesting to say about totally disconnected spaces, besides that they’re a source of a lot of counterexamples.

on December 27, 2009 at 12:37 am |Qiaochu YuanDarn. I think the problem is that there are spaces which are totally disconnected but which don’t have the discrete topology. I’ll see if I can repair the claim I’m making.

on December 27, 2009 at 11:55 am |DTWikipedia is wrong about connected components of compact Hausdorff spaces being open. For instance the Cantor set and the one-point compactification of the integers are compact, Hausdorff, totally disconnected, but not discrete.

on December 31, 2009 at 12:28 pm |PhilSo if we’re looking at the subcategory of locally connected spaces, then I don’t think an infinite product of discrete spaces exists in this category (or probably does exist, but is different from the infinite product in the category of all topological spaces).

We would need to resolve this before we can even talk about whether T preserves infinite products.

on December 31, 2009 at 1:24 pm |Qiaochu YuanAn infinite product of locally connected spaces is locally connected if and only if all but finitely many of the factors are connected; in other words, the subcategory of locally connected spaces doesn’t have infinite products. So I guess bad things happen no matter what.

on January 1, 2010 at 9:22 pm |philtynanAs I said before, this doesn’t necessarily mean that it doesn’t have infinite products. There could still be some locally connected space that satisfies the universal property for the infinite product of discrete spaces in the category of locally compact spaces.

Naiively, I suspect that if this is true, then as a set is probably the set-wise infinite product, but is topologized in a different way.

In the full category of topological spaces, we of course need to give the product topology, so that the unique map is continuous. However, we now know that must be locally connected, so we may be able to give a finer topology. Upon inspection, it still turns out that the box topology fails, as does the uniform topology, so this is not looking too hopeful.

on December 27, 2009 at 6:43 am |HarrisonThe conceptual content of the proof is that any such morphism must be locally constant, since otherwise it could not preserve adjacency, and every locally constant function is a morphism since there is no adjacency relation between distinct components.There’s a sequence in Lovasz where this concept is taken to its extreme, including replacing the equivalence relation by a metric. (At which point the above statement becomes completely wrong, but you should still have a solid intuition.) I think the sequence builds to a proof that the greedy algorithm for minimum spanning tree is optimal.

on December 27, 2009 at 11:59 am |DTTell us more!

on December 27, 2009 at 4:44 pm |HarrisonOh, blah, I got confused. The thing in Lovasz is somewhat different, and starts off by (essentially) considering morphisms from a simple

treeto the graph obtained by putting a loop at each vertex. Still, it seems related to the connected components functor, although in a way I can’t totally articulate…on December 28, 2009 at 11:36 pm |HarrisonAlso, a nitpick: If you restrict your graphs to be simple, you can’t define a morphism to the graph with two vertices and two loops. :) Probably best to stick to the category of just undirected graphs (and noting that multiple edges don’t make a difference), although there’s a strong case that the “right” thing to do is to assign weights to the vertices and edges…

on December 28, 2009 at 11:51 pm |Qiaochu YuanSorry, ignore that and look at what I said after that, which is “symmetric reflexive relation.”

on December 30, 2009 at 2:41 am |Attila SmithYour sentence

“The issue is that … ,and the locally constant functions on a space are all continuous if and only if each connected component is clopen”

is incorrect as stated, since locally constant functions are always continuous from any topological space to any topological space.

on December 30, 2009 at 12:22 pm |Qiaochu YuanSorry; when I wrote “locally constant,” I meant “constant on each connected component.” I’ll fix that.

on October 7, 2012 at 7:51 am |Todd TrimbleI had been doing some work in the nLab and googling around when I bumped into this discussion. It might help to observe that the category of locally connected spaces is coreflective in , and therefore is complete and cocomplete (in particular, has infinite products), although it involves retopologizing the products in $Top$ by applying the coreflection. For this category , we do indeed have the desired adjunction . So, good things happen after all!

on October 7, 2012 at 2:35 pm |Qiaochu YuanInteresting. What’s the coreflection?

on October 7, 2012 at 6:28 pm |Todd TrimbleI should be a little careful here; when I said “locally connected”, I meant a space that is a topological coproduct of its connected components. This definition seems to be at variance with how “locally connected” is defined by for example Munkres (who defines it to mean: having a basis of connected open neighborhoods; under his definition, a space can be connected and yet not be locally connected).

Sticking with my definition, the coreflection just sends a space to the coproduct in of its connected components. Same underlying set, but retopologized with a finer topology. You get the same space back if and only if the original space is locally connected.

on October 7, 2012 at 6:33 pm |Qiaochu YuanI’m not sure you should call this “locally connected” since it doesn’t seem to be a local property.

on October 7, 2012 at 6:53 pm |Todd TrimbleWell, I’m open to suggestions.

I do have a reason for calling it that, but let’s put nomenclature aside for the moment. The reason I wrote you is that restriction to the full category of whatshallicallit spaces gives a reasonable (complete and cocomplete) full subcategory of for which we have the sort of adjunction that your post is all about. Which should be good news.

on October 7, 2012 at 7:02 pm |Qiaochu YuanRight. That is good news!

on October 8, 2012 at 6:08 am |Todd TrimbleOne more comment before taking leave — I agree that “locally connected” is a poor choice of terminology here. But if we use the standard definition of “locally connected”, then it is still true that locally connected spaces are coreflective in — the coreflection retopologizes a space by considering the topology generated by the collection of connected components of open sets. In particular, the category of locally connected spaces is complete and cocomplete. (This addresses a point in the exchange between you and philtynan, circa December 31, 2009.)

on October 8, 2012 at 10:14 am |Qiaochu YuanAha. That’s good news too!