You are currently browsing the tag archive for the ‘path-connectedness’ tag.
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.)
Recent Comments