Feeds:
Posts

The connected components functor

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 $\text{Top}$ and $\text{Graph}$, and also has a sensible meaning in, for example, $G\text{-Set}$ for a group $G$. Lawvere and Schanuel suggest the following way to understand several of the examples that occur in practice:

Let $C$ be a concrete category with a forgetful functor $F : C \to \text{Set}$. If it exists, let $T : \text{Set} \to C$ be the left adjoint to $F$. Then $T$ describes the “discrete” (i.e. “totally disconnected”) objects of $C$, and, if it exists, the left adjoint to $T$ is a functor $\pi_0 : C \to \text{Set}$ describing the “connected components” of an object in $C$.

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 $\text{Graph}$ of – for the sake of simplicity – undirected simple graphs has objects specified by a vertex set $V$ and a symmetric reflexive relation $E$ 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 $v, w \in G$ 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 $\text{Graph}$. So how should we accomplish this? One answer is surprisingly simple.

Proposition: Let $\mathbf{2}$ be the graph consisting of two vertices and only self-loops. Then the number $c$ of connected components of a finite graph $G$ is the unique non-negative integer such that the number of morphisms $G \to \mathbf{2}$ is $2^c$.

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 $\pi_0 : \text{Graph} \to \text{Set}$ sending a graph to the set of its connected components satisfies a natural equivalence

$\text{Hom}_{\text{Set}}(\pi_0 A, \mathbf{2}) \simeq \text{Hom}_{\text{Graph}}(A, \mathbf{2})$

where $\mathbf{2}$ is a two-element set in $\text{Set}$. (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, $P$ should be left adjoint to the functor $T : \text{Set} \to \text{Graph}$ which sends a set to the graph with vertex set that set and with no nontrivial edges; this functor sends $\mathbf{2}$ to $\mathbf{2}$.

Here’s how we “come up” with this functor. The “obvious” choice of forgetful functor $F : \text{Graph} \to \text{Set}$ sends a graph to its vertex set, and its left adjoint is $T$! Remember that this means there is a natural identification

$\displaystyle \text{Hom}_{\text{Graph}}(TA, B) \simeq \text{Hom}_{\text{Set}}(A, FB)$

since any function from $TA$ to another graph automatically respects adjacency.

Topological spaces

The category $\text{Top}$ 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 $X$ is connected if $X$ is not the disjoint union of two open subsets of $X$. Again, there is an equivalence relation relating two points $p, q \in X$ if they lie in a connected subset of $X$, and the equivalence classes of this relation is the standard definition of connected component.

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

$\text{Hom}_{\text{Set}}(\pi_0 X, Y) \simeq \text{Hom}_{\text{Top}}(X, TY)$

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, $\mathbb{Q}$ 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 $\pi_0$ is a left adjoint to $T$ 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 $T$ in a category $C$ describes its subcategory of “discrete objects,” and then $\pi_0$ is universal for morphisms into discrete objects. Now, since $T$ is a right adjoint, it preserves products, in particular the empty product, so it sends the terminal object $\mathbf{1}$ of $\text{Set}$ to the terminal object $\mathbf{1}$ of $C$. Since $\text{Set}$ has the special property that all of its elements are coproducts of the terminal object with itself, and since $T$ is also a left adjoint, hence preserves coproducts, it follows that we can describe the subcategory of “discrete objects” without any explicit reference to $T$ or $F$: 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 $\text{Graph}$ it is the singleton with one self-loop, in $G\text{-Set}$ it is the singleton with a trivial action of $G$, and in $\text{Top}$ 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.”

23 Responses

1. I’m a bit confused by the G-Set example.

I don’t believe that the left adjoint to the forgetful functor is the “trivial action functor”. For example, let’s G be the two-element group, E be the regular G-set and X be a singleton. Then, GSet(TX, E) is empty, because a G-map sends fixed points to fixed points, and E has none, whereas Set(X,FE) has two elements.

What I think is true is that we have two chains of adjunctions L/F/E and pi0/T/Fix, where F, T and pi0 are the functors you defined, L is the functor sending a set X to |X| disjoint copies of the regular G-set, E is the functor sending a set X to the G-set X^G and Fix is the functor sending a G-set to its set of fixed points.

I don’t know how that effects the big-picture message you’re trying to convey.

• Yeah, the $G$-set example is just wrong; of course the left adjoint is the “free $G$-action functor,” which sends a set $X$ to $X \times G$ with the obvious $G$-action. Thanks for the correction!

2. I 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 $X$ to the coproduct in $Top$ 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.

• I’m not sure you should call this “locally connected” since it doesn’t seem to be a local property.

• Well, 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 $Top$ for which we have the sort of adjunction that your post is all about. Which should be good news.

• Right. That is good news!

• One 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 $Top$ — the coreflection retopologizes a space $X$ 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.)

• Aha. That’s good news too!

3. I 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 $Top$, 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 $LocConn$, we do indeed have the desired adjunction $\pi_0 \dashv T$. So, good things happen after all!

• Interesting. What’s the coreflection?

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

• Sorry; when I wrote “locally constant,” I meant “constant on each connected component.” I’ll fix that.

5. Also, 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…

• Sorry, ignore that and look at what I said after that, which is “symmetric reflexive relation.”

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

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.

• Tell us more!

• Oh, blah, I got confused. The thing in Lovasz is somewhat different, and starts off by (essentially) considering morphisms from a simple tree to 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…

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

• Darn. 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.

• Wikipedia 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.

• So 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.

• An 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.

• As I said before, this doesn’t necessarily mean that it doesn’t have infinite products. There could still be some locally connected space $X$ 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 $X$ 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 $X$ the product topology, so that the unique map $Y \to X$ is continuous. However, we now know that $Y$ must be locally connected, so we may be able to give $X$ 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.