Is there a countable certificate for connectedness?

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

in , where

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