Tag Archive

You are currently browsing the tag archive for the ‘path-connectedness’ tag.

Is there a countable certificate for connectedness?

13 April, 2010 in math.GN, math.LO, question | Tags: , , | by | 20 comments

In topology, a non-empty set {E} is said to be connected if cannot be decomposed into two nontrivial subsets that are both closed and open relative to {E}, and path connected if any two points {x,y} in {E} can be connected by a path (i.e. there exists a continuous map {\gamma: [0,1] \rightarrow E} with {\gamma(0)=x} and {\gamma(1)=y}).

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

\displaystyle E := \{ (0,y): -1 \leq y \leq 1 \} \cup \{ (x, \sin(1/x)): 0 < x \leq 1 \}, \ \ \ \ \ (1)

which is connected but not path-connected (there is no continuous path from {(0,1)} to {(1,\sin(1))}).

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 {x} and {y}) for a given type of input (in this case, a pair of points {x, y}). 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 {E} of Euclidean space, there is an answer as follows. If {\epsilon > 0}, let us call two points {x, y} in {E} {\epsilon}-connected if one can find a finite sequence {x_0 = x, x_1, \ldots, x_N = y} of points in {E}, such that {|x_{i+1}-x_i| < \epsilon} for all {0 \leq i < N}; informally, one can jump from {x} to {y} in {E} using jumps of length at most {\epsilon}. Let us call {x_0,\ldots,x_N} an {\epsilon}-discrete path.

Proposition 1 (Connectedness certificate for compact subsets of Euclidean space) Let {E \subset {\bf R}^d} be compact and non-empty. Then {E} is connected if and only if every pair of points in {E} is {\epsilon}-connected for every {\epsilon > 0}.

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

Conversely, suppose that there is a pair of points {x,y} in {E} and an {\epsilon > 0} such that {x,y} are not {\epsilon}-connected. Let {F} be the set of all points in {E} that are {\epsilon}-connected to {x}. It is easy to check that {F} is open, closed, and a proper subset of {E}; thus {E} is disconnected. \Box

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

It is also interesting to contrast the above proposition with path connectedness. Clearly, if two points {x, y} are connected by a path, then they are {\epsilon}-connected for every {\epsilon > 0} (because every continuous map {\gamma: [0,1] \rightarrow E} is uniformly continuous); but from the analysis of the example (1) we see that the converse is not true. Roughly speaking, the various {\epsilon}-discrete paths from {x} to {y} have to be “compatible” with each other in some sense in order to synthesise a continuous path from {x} to {y} 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 {E} of {{\bf R}^d}? One can construct lousy certificates, for instance one could look at all continuous paths in {{\bf R}^d} joining two particular points {x, y} in {E}, and verify that each one of them leaves {E} 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 {E} by describing a family of {\epsilon}-nets for a countable sequence of {\epsilon} 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 {E} 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 {{\bf R}^d}? Proposition 1 fails in this case; consider for instance the set

\displaystyle E := \{ (x,0): x \in {\bf R} \} \cup \{ (x,\frac{1}{x}): x > 0 \}. \ \ \ \ \ (2)

Any pair of points {x,y \in E} is {\epsilon}-connected for every {\epsilon > 0}, and yet this set is disconnected.

The problem here is that as {\epsilon} gets smaller, the {\epsilon}-discrete paths connecting a pair of points such as {(1,0)} and {(1,1)} 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 {x, y}, there exists an {R>0} such that there is an {\epsilon}-discrete path from {x} to {y} of diameter at most {R} for every {\epsilon > 0}. This does indeed force connectedness, but unfortunately not all connected sets have this property. Consider for instance the set

\displaystyle E := \{ (x,y,0): x \in {\bf R}, y \in \pm 1 \} \cup \bigcup_{n=1}^\infty (E_n \cup F_n) \ \ \ \ \ (3)

in {{\bf R}^3}, where

\displaystyle E_n := \{ (x,y,0): \frac{x^2}{n^2} + \frac{y^2}{(1-1/n)^2} = 1\}

is a rectangular ellipse centered at the origin with minor diameter endpoints {(0,1/n-1), (0,1-1/n)} and major diameter endpoints {(-n,0), (n,0)}, and

\displaystyle F_n := \{ (n,y,z): (y-1/2)^2+z^2=1/4 \}

is a circle that connects the {(n,0)} endpoint of {E_n} to the point {(n,1)} in {E}. One can check that {E} is a closed connected set, but the {\epsilon}-discrete paths connecting {(0,-1)} with {(0,+1)} have unbounded diameter as {\epsilon \rightarrow 0}.

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 {\delta}:

Proposition 2 (Second-order connectedness certificate) Let {E} be a closed non-empty subset of {{\bf R}^d}. Then the following are equivalent:

  • {E} is connected.
  • For every monotone decreasing, strictly positive function {\delta: {\bf R}^+ \rightarrow {\bf R}^+} and every {x,y \in E}, there exists a discrete path {x_0=x,x_1,\ldots,x_N=y} in {E} such that {|x_{i+1}-x_i| < \delta(|x_i|)}.

Proof: This is proven in almost the same way as Proposition 1. If {E} can be disconnected into two non-trivial sets {F, G}, then one can find a monotone decreasing gauge function {\delta: {\bf R}^+ \rightarrow {\bf R}^+} such that for each ball {B_R := \{ x \in {\bf R}^d: |x| \leq R \}}, {F \cap B_R} and {G} are separated by at least {\delta(R)}, and then there is no discrete path from {F} to {G} in {E} obeying the condition {|x_{i+1}-x_i| < \delta(|x_i|)}.

Conversely, if there exists a gauge function {\delta} and two points {x,y \in E} which cannot be connected by a discrete path in {E} that obeys the condition {|x_{i+1}-x_i| < \delta(|x_i|)}, then if one sets {F} to be all the points that can be reached from {x} in this manner, one easily verifies that {F} and {E \backslash F} disconnect {E}. \Box

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

Archives