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.)
20 comments
Comments feed for this article
13 April, 2010 at 10:56 pm
mircea
I 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
noamnisan
In 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 Tao
Well, 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 Ribeiro
Dear 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 Tao
Oops! I meant to say “unbounded closed” rather than “unbounded compact”, of course.
14 April, 2010 at 5:15 am
Todor Tsankov
One 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 Tao
Thanks! 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 Tsankov
To 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
porton
I 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/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
porton
See 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
nicolaennio
In 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 Zelinsky
Regarding 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
777
I 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 Zelinsky
That looks like it works to me.
21 April, 2010 at 2:57 pm
777
For 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 point of 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 Muscat
The 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 Brown
There 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 Tao
Dear 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 Brown
Dear 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.
25 June, 2016 at 7:34 am
Jhon Manugal
These notions of topology assume you have infinite resources to verify. If we thicken a space-filling curve, the interior is connected. But how long does it take to draw locate a path from one point to another. If you are a dog and the mailman is the maze somewhere, how long does it take before you can bite his leg?
Even more severely, let the space-filling curve itself be the boundary (which is not even closed) and I am sure the dog will find the mailman.