Re: Compact subsets of {0,1}^N
- From: William Elliot <marsh@xxxxxxxxxxxxxxxxxx>
- Date: Fri, 1 Jul 2005 00:55:50 -0700
From: David C. Ullrich <ullrich@xxxxxxxxxxxxxxxx>
Summary of proof and comments presented by D.C. Ullrich regards
closed without isolated points, nonnul K subset S = {0,1}^N
==> K homeomorphic S
> If a is a _finite_ sequence of 0's and 1's let S_a be the set of
> all elements of S that begin with a. Note that we're including
> the case where a is the empty sequence, ie a sequence of length 0:
> if a is the empty sequence then S_a = S.
> Let B be the tree of all finite sequences of 0's and 1's, and let
> T be the tree of all finite sequences a such that S_a intersect K
> is nonempty.
> Define a map F from B onto T by induction:
> If a is the empty sequence let F(a) = a.
> For each a in B, of length n, let a_0 and a_1 be the two extensions
> of a of length n + 1 (a_j consists of a followed by a j.)
> Now if a is in B and F(a) has already been defined, define
> F(a_0) and F(a_1) as follows: Let b = F(a).
Since K has no isolated points and S_b is open, K intersect S_b must
contain at least two points. So b has at least two extensions in T.
Hence there exists an extension b' of b, with length(b') = m, say,
such that
(i) b' is the only extension of b in T of length m and
(ii) b'_0 and b'_1 are both elements of T.
Define F(a_0) = b'_0 and F(a_1) = b'_1.
(Less formally: Since K intersect S_b contains more than one
point, the node b in T must _eventually_ split in two, at
some level below the level of b. Map a_0 and a_1 to the two
nodes in T at the first level where b splits.)
> It follows that if a' is an extension of a then F(a') is an
> extension of F(a), so F induces a map f:S -> S in a natural
> way (given a in S, f(a) is the unique element of S such that
> f(every finite initial segment of a) is an initial segment of f(a).
> It's easy to see that f is continuous (given a and n there exists
> m such that if a' agrees with a in the first m places then f(a')
> agrees with f(a) in the first n places).
f is 1-1: Say b, c are in S and b <> c. There is a first place
at which b and c differe, which says that there is a (possibly
zerp-length) finite string d such that d_0 is an initial segment
of b and d_1 is an initial segment of c, or vice versa. Now by
the construction of F, there exists e such that F(d_0) = e_0 and
F(d_1) = e_1, so F(d_0) <> F(d_1). But F(d_0) is an initial segment
of f(b) and F(d_1) is an initial segment of f(c), so f(b) <> f(c).
f maps S into K: Say a is in S. Let's say a[:n] is the finite
string consisting of the first n elements of a. Now by
construction for every n there exists b^n in T such that
F(a[:n]) = b^n, note that the length of b^n is at least n.
Since b^n is in T, for every n there exists k^n in K such
that b^n is an initial segment of K.
Now by construction f(a) agrees with b^n in the first
n places, and b^n also agrees with k^n in the first
n places, so f(a) agrees with k^n in the first n
places. This says that k^n converges to f(a), and
hence f(a) is in K since K is closed.
f maps S onto K: Let's say that a finite string t in T
is an n-sibling if t has length n and there exists t'
in T such that t' <> t, t' has length n, and t and t'
agree in the first n-1 places. Say that t in T is a
sibling if it is the empty string or an n-sibling for
some n. By construction the range of F is exactly the
set of all siblings.
Now suppose that k is in K. Since K has no isolated
points there exists a cofinal sequence of initial
segments of k, each of which is a sibling. Since
each sibling is in the range of F it follows that
k is in the range of f.
--
The fact that f maps S onto K is exactly the part that I originally
said I hoped was obvious, because a formal explanation might be a
little long. Ok, if it's obvious to me then I should be able to
write down a formal explanation - here we go (I'll give an
illustration of why every element of K starts with F(0) or
F(1) after the proof):
Borrowing notation from Python, if n <= length(t) let's say
that t[:n] is the initial segment of t of length n. Now say
t' is a child of t if n = length(t) = length(t') - 1 and
t'[:n] = n. This "child of" relation makes T into a tree
in which each node has one or two children.
Say t' is a descendant of t if t' is a child of t or a
child of a child of t or etc. Say t' starts with t if
n = length(t) <= length(t') and t'[:n] = t. So of course
t' starts with t if and only if t' is a descendant of t;
in the one case we're thinking about actual sequences
and in the other we're thinking about the tree structure.
Ok. The first fact is that every element of T has more
than one descendant. This is where the fact that K has
no isolated points is used: Say t is an element of T,
choose k in K so that k starts with t (the existence
of such a t is exactly the definition of T), and
consider a sequence of distinct points of K that
converge to k. By the definition of convergence,
all but finitely many of those points of K start
with t; in particular there exist at least two
elements of K that start with t, which says that
t has at least two descendants.
So every element of T has at least two descendants,
but of course an element of T can have only one
child. Say t is in T. Define split(t) = t', where
t' is the element of T of minimal length such that
t' is a descendant of t and t' has two children.
As before, let a_0 and a_1 be the two sequences
consiting of a followed by a 0 or 1, respectively.
The definition of F was this: F(empty sequence)
= empty sequence, and F(a_0) = split(F(a))_0,
F(a_1) = split(F(a))_1.
It follows that the range of F is exactly the
empty sequence plus all siblings in T: one
direction is immediate, and for the other
direction, given t in T which is a sibling,
trace the chain of ancestors up the tree until
you come to an ancestor of shorter length which
is also a sibling or the empty sequence. (If
t^ is a proper ancestor of t of maximal length
such that t^ is also a sibling then t^ is in the
range of F by induction on the length and then
the definition of F shows that t is in the range
of F. On the other hand, if no proper ancestor
of t is a sibling then t = split(empty sequence)
and it also follows that t is in the range of F.)
Now fix k in K. The second key fact is this:
infinitely many initial segments of k are siblings.
(We need to show that for every N there exists
n >= N such that k[:n] is a sibling. Fix n. Since
k is not an isolated point of K there exists k'
in K with k' <> k such that k'[:N} = k[:N}.
Since k' <> k there exists n > N such that
k'[n] <> k[n] (where s[n] denotes the n-th term
of s. Choose n minimal with this property; then
k[:n] is a sibling, because k[:n] and k'[:n]
are unequal but they are both children of
k[:n-1].)
So every element of K has infinitely many initial
segments which are siblings. Hence every k in K
has infinitely many initial segments which are in
the range of F, and hence k is in the range of f.
*******************
Why every element of K starts with F(0) or F(1):
It could happen, say, that every element of K
starts with 01101, but not every element of K
starts with 011010 and not every element of K
starts with 011011. If that happens then
every element of K starts with 011010 _or_
011011, and the definitions show that 01101
= split(empty sequence), hence F(0) = 011010
and F(1) = 011011.
Another way of looking at the whole thing - much less formal,
but it may make you realize suddenly why it's all obvious:
Draw a picture of the tree T: An infinite tree where every
node has one or two children and every node has more than
one descendant. Any time you see a chain of nodes each
with only one child, imagine collapsing that chain into
a single node in a new tree. Then that new tree is a
complete infinite binary tree - any two complete infinite
binary trees are obviously isomorphic, and the F above
(translated to our new tree) is just the obvious isomorphism.
----
.
- Prev by Date: Re: At what age did you get your idea published for the first time?
- Next by Date: Re: cranky challenge - beating a game
- Previous by thread: Re: Compact subsets of {0,1}^N
- Next by thread: Re: cranky challenge - beating a game
- Index(es):
Relevant Pages
|
