In topology, a non-empty set is said to be *connected* if cannot be decomposed into two nontrivial subsets that are both closed and open relative to , and *path connected* if any two points in can be connected by a path (i.e. there exists a continuous map with and ).

Path-connected sets are always connected, but the converse is not true, even in the model case of compact subsets of a Euclidean space. The classic counterexample is the set

which is connected but not path-connected (there is no continuous path from to ).

Looking at the definitions of the two concepts, one notices a difference: the notion of path-connectedness is somehow a “positive” one, in the sense that a path-connected set can produce the existence of something (a path connecting two points and ) for a given type of input (in this case, a pair of points ). On the other hand, the notion of connectedness is a “negative” one, in that it asserts the *non-existence* of something (a non-trivial partition into clopen sets). To put it another way, it is relative easy to convince someone that a set is path-connected (by providing a connecting path for every pair of points) or is disconnected (by providing a non-trivial partition into clopen sets) but if a set is not path-connected, or is connected, how can one easily convince someone of this fact? To put it yet another way: is there a reasonable *certificate* for connectedness (or for path-disconnectedness)?

In the case of connectedness for compact subsets of Euclidean space, there is an answer as follows. If , let us call two points in *-connected* if one can find a finite sequence of points in , such that for all ; informally, one can jump from to in using jumps of length at most . Let us call an *-discrete path*.

Proposition 1 (Connectedness certificate for compact subsets of Euclidean space)Let be compact and non-empty. Then is connected if and only if every pair of points in is -connected for every .

*Proof:* Suppose first that is disconnected, then can be partitioned into two non-empty closed subsets . Since is compact, are compact also, and so they are separated by some non-zero distance . But then it is clear that points in cannot be -connected to points in , and the claim follows.

Conversely, suppose that there is a pair of points in and an such that are not -connected. Let be the set of all points in that are -connected to . It is easy to check that is open, closed, and a proper subset of ; thus is disconnected.

We remark that the above proposition in fact works for any compact metric space. It is instructive to see how the points and are -connected in the set (1); the -discrete path follows the graph of backwards until one gets sufficiently close to the -axis, at which point one “jumps” across to the -axis to eventually reach .

It is also interesting to contrast the above proposition with path connectedness. Clearly, if two points are connected by a path, then they are -connected for every (because every continuous map is uniformly continuous); but from the analysis of the example (1) we see that the converse is not true. Roughly speaking, the various -discrete paths from to have to be “compatible” with each other in some sense in order to synthesise a continuous path from to in the limit (we will not make this precise here).

But this leaves two (somewhat imprecise) questions, which I do not know how to satisfactorily answer:

**Question 1:** Is there a good certificate for path disconnectedness, say for compact subsets of ? One can construct lousy certificates, for instance one could look at all continuous paths in joining two particular points in , and verify that each one of them leaves at some point. But this is an “uncountable” certificate – it requires one to check an uncountable number of paths. In contrast, the certificate in Proposition 1 is basically a countable one (if one describes a compact set by describing a family of -nets for a countable sequence of tending to zero). (Very roughly speaking, I would like a certificate that can somehow be “verified in countable time” in a suitable oracle model, as discussed in my previous post, though I have not tried to make this vague specification more rigorous.)

It is tempting to look at the equivalence classes of given by the relation of being connected by a path, but these classes need not be closed (as one can see with the example (1)) and it is not obvious to me how to certify that two such classes are not path-connected to each other.

**Question 2:** Is there a good certificate for connectedness for closed but *unbounded* closed subsets of ? Proposition 1 fails in this case; consider for instance the set

Any pair of points is -connected for every , and yet this set is disconnected.

The problem here is that as gets smaller, the -discrete paths connecting a pair of points such as and have diameter going to infinity. One natural guess is then to require a uniform bound on the diameter, i.e. that for any pair of points , there exists an such that there is an -discrete path from to of diameter at most for every . This does indeed force connectedness, but unfortunately not all connected sets have this property. Consider for instance the set

is a rectangular ellipse centered at the origin with minor diameter endpoints and major diameter endpoints , and

is a circle that connects the endpoint of to the point in . One can check that is a closed connected set, but the -discrete paths connecting with have unbounded diameter as .

Currently, I do not have any real progress on Question 1. For Question 2, I can only obtain the following strange “second-order” criterion for connectedness, that involves an unspecified gauge function :

Proposition 2 (Second-order connectedness certificate)Let be a closed non-empty subset of . Then the following are equivalent:

- is connected.
- For every monotone decreasing, strictly positive function and every , there exists a discrete path in such that .

*Proof:* This is proven in almost the same way as Proposition 1. If can be disconnected into two non-trivial sets , then one can find a monotone decreasing gauge function such that for each ball , and are separated by at least , and then there is no discrete path from to in obeying the condition .

Conversely, if there exists a gauge function and two points which cannot be connected by a discrete path in that obeys the condition , then if one sets to be all the points that can be reached from in this manner, one easily verifies that and disconnect .

It may be that this is somehow the “best” one can do, but I am not sure how to quantify this formally.

Anyway, I was curious if any of the readers here (particularly those with expertise in point-set topology or descriptive set theory) might be able to shed more light on these questions. (I also considered crossposting this to Math Overflow, but I think the question may be a bit too long (and vague) for that.)

(The original motivation for this question, by the way, stems from an attempt to use methods of topological group theory to attack questions in additive combinatorics, in the spirit of the paper of Hrushovski studied previously on this blog. The connection is rather indirect, though; I may discuss this more in a future post.)

## 19 comments

Comments feed for this article

13 April, 2010 at 10:56 pm

mirceaI think you mean (0, 1/n-1) instead of (1-1/n,0) in the description of E_n, right?

[Corrected, thanks - T.]14 April, 2010 at 3:49 am

noamnisanIn Q1 are you really looking for a certificate for non-path-connectedness (as stated) or for path-connectedness (in analogy to the certificate for connectedness)?

14 April, 2010 at 7:53 am

Terence TaoWell, I had thought that the definition of path-connectedness already supplied a countable certificate, but on closer reflection I realise that this is not the case (given a path oracle, one can verify in countable time that it will demonstrate path connectedness between two given points, but I don’t know how to search the path space, and also one has to deal with an uncountable number of pairs of points x,y. Todor’s answer suggests in fact that no such certificate exists either for path connectedness or path disconnectedness, which would be a satisfactory answer to Q1.

14 April, 2010 at 4:40 am

Pedro Lauridsen RibeiroDear Prof. Tao,

I don’t quite understand the first sentence of Question 2, for a subset of is compact if and only if it’s closed and bounded (Heine-Borel theorem).

14 April, 2010 at 7:50 am

Terence TaoOops! I meant to say “unbounded closed” rather than “unbounded compact”, of course.

14 April, 2010 at 5:15 am

Todor TsankovOne possible way to formalize your questions is to ask for the descriptive complexity of the set of connected (resp. path-connected) compact subsets of in the space of all compact subsets (with the Vietoris topology). Then the existence of a certificate of the kind you are asking for would correspond to that set being analytic (a projection of a Borel set).

It is easy to see that the condition of being connected is closed (so it is very simple in descriptive set theoretic terms), while it is a theorem of Ajtai and Becker that being path-connected is -complete (see Kechris, Classical descriptive set theory, 37.11) at least if (so it is very complicated). I believe something similar has been proved in dimension 2 but it is more difficult to trace in the literature. This means that the simplest (in terms of number of changing quantifiers) possible way to say that a set is path-connected is the obvious one: for every pair of points there exists a path between them. In particular, there isn’t a certificate neither for path-connectedness nor for path-disconnectedness, at least if you require that the certificate can be represented as a point in a Polish space and checking it be Borel.

As for the equivalence relation of being in the same path-component, there is an interesting jump in complexity from dimension 2 to 3. See the paper MR1678350 (MathSciNet) by Becker for details.

14 April, 2010 at 7:57 am

Terence TaoThanks! I think this settles Q1 pretty conclusively. The assertion that connectedness is a closed condition for compact sets seems quite consistent with Proposition 1. For Q2, I mistakenly wrote “compact” when I should have written “closed”. I think the topology of all closed sets is much worse than that of all compact sets (in particular, it will not be separable in most reasonable topologies), so the descriptive set theory classification might not be enough.

I had a vague idea of trying to describe connectedness for unbounded sets in terms of some sort of generalised path connectedness involving something like the long line rather than the unit interval, but it looks messy (I guess ordinals are not sufficient to describe all the possible one-dimensional connected sets out there).

14 April, 2010 at 10:03 am

Todor TsankovTo put the second question in the same framework, one can consider the sphere instead of . Then the question becomes: is the set of compact subsets of such that is connected Borel? (Here is the point at infinity.) Since the set is obviously co-analytic (for all pairs of non-intersecting open subsets of the sphere… etc.; this can also be seen from your Proposition 2), being Borel is equivalent to being analytic (that is, the existence of certification system). I have no idea what the answer is but at least it is a concrete question..

14 April, 2010 at 5:32 am

portonI did some research (however it has white spots that is open problems) of connectedness for funcoids, a generalization of proximites, pretopologies, and preclosures, and reloids, a generalization of uniformities.

http://www.mathematics21.org/binaries/funcoids-reloids.pdf

http://www.mathematics21.org/algebraic-general-topology.html

If you are serious about researching connectedness, you should read my drafts. (However I in no way touch the issue of path-connectedness.)

16 August, 2010 at 5:58 am

portonSee http://www.mathematics21.org/binaries/connectedness.pdf for my preprint of an article about generalized connectedness of sets. This generalizes topological connectedness, digraph connectedness, proximal connectedness (aka equiconnectedness), uniform connectedness, etc.

I will also dive deeper in my research into connectedness of filters.

16 April, 2010 at 3:18 am

nicolaennioIn the discrete setting you can count the number of a graph connected components as the number of eigenvalues of the graph laplacian operator that are equal to zero. Thus to test if a subset of the graph is disconnected you can build the related eigenvector and plug it into the laplacian definition. I do not know if this can be of help for Q2

16 April, 2010 at 11:56 am

Joshua ZelinskyRegarding connected sets with a uniform bound on the diameter of their epsilon-connectedness, your example that you can have a connected set without such a bound requires 3 dimensions. Is there any way to do this with a subset of R^2? (Obviously this can’t be done in R^1(.

21 April, 2010 at 10:44 am

777I think for that we can just consider the set . To connect the points and , the -chain has to have unbounded diameter as .

If this is true (and so far * I * don’t see what fails) Does this give a simpler example for a connected set with unbounded diameter for -chains connecting two points (and is in )?

21 April, 2010 at 11:03 am

Joshua ZelinskyThat looks like it works to me.

21 April, 2010 at 2:57 pm

777For question 2, we can invert the closed set about any ball in the complement and get a bounded set . (I think Todor Tsankov has already mentioned this above)

Let be the center of the ball (i.e. image of infinity). being unbounded means infinity is in the closure of and compact.

If is not connected (by the -chain test then is also not connected and we are done.

In continuum theory, is called a

cut pointof a compact connected set if is not connected. So the problem is same as giving a countable certificate for determining a given point in a continuum is a non-cut point.23 April, 2010 at 3:35 am

Joseph MuscatThe emphasis above has been on boundedness not completeness. But the latter is crucial for Prop. 1 to work. For example, the Cantor teepee, which is not complete, satisfies the epsilon-connectedness criterion, whether it contains its dispersion point or not.

24 April, 2010 at 10:58 am

Bob BrownThere seems to be a problem with the proof of Proposition 1. Let E be the 1/n sequence union 0, let x = 0 and y = 1, then F = {0} which is not open in E.

24 April, 2010 at 9:29 pm

Terence TaoDear Bob,

Hmm, I’m afraid I don’t see the problem (I assume you are referring to the second part of the proof). If , then the set of points in E that can be -connected to 0 is just the intersection of E with , which is both open and closed.

25 April, 2010 at 3:36 pm

Bob BrownDear Terry,

Whoops – sorry about that. Well, now that I *do* understand your nice proposition, I’ll show it to my Introduction to Topology class when we get to the section on connectedness. Many thanks for a nice topic.