Re: Compact subsets of {0,1}^N
- From: David C. Ullrich <ullrich@xxxxxxxxxxxxxxxx>
- Date: Thu, 30 Jun 2005 09:40:25 -0500
On Thu, 30 Jun 2005 03:14:28 -0700, William Elliot
<marsh@xxxxxxxxxxxxxxxxxx> wrote:
>On Tue, 28 Jun 2005, David C. Ullrich wrote:
>> William Elliot <marsh@xxxxxxxxxxxxxxxxxx> wrote:
>> >>
>> >> >A closed nonnul subset K without isolated points of S = {0,1}^N
>> >> >is homeomorphic to S.
>>
>> f maps S into K:
>
>This I did by defining f(s) to be the unique, as it turns out, element of
>the intersection of a descending sequence of nonnul closed subsets of K.
>
>> 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.
>>
>This I'm still puzzling. Assume s in K and lets take the first step,
>showing F(0) or F(1) is a prefix for s. Would you do a slow motion
>replay?
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.
>> 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.
>>
>> >> >[stuff I dunno nothing about snipped]
>> >Ah shucks. What don't you know about?
>>
>> Plenty. (Flattery may get you somewhere, but if you want
>> me to worry about things that I don't feel like worrying
>> about send money.)
>>
>Is this proof you came up with a proof of your own making?
Well, it's not something that I read, I guess I made it up,
but it's not original either - it's just the standard proof
as posted by someone else, translated to sequences, and
with everything written out in detail. (When I say "the
standard proof" that doesn't mean I read it either, but
when I figured it out some years ago it was clear it must
be the standard proof.)
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.
>How do you want payment, in bhats, dongs or pesos? ;-)
>
>let Sf = set of binary sequences in S that eventuate to 0.
>Sf is a countable dense subset of S = {0,1}^N.
>Let D be a countable dense subset of S. D has no isolated points.
>Let { d_j | j in N } be an enumeration of D
>
>Well posh and bother. You'd think there'd be a natural bijection between
>Sf and B = set of finite binary sequences. Nothing so simple like just
>tack on 000... to every b in B or just clip the training 0's from s in Sf.
>
>So less I worry you more than just your two cents worth, whoops better
>make that three cents worth due to inflation, where would Sf apply for
>naturalization onto the finite world of B?
Um, hard to say when you put it that way.
I gather that what you're really curious about is how to
show that any two countable dense subsets of K are
homeomorphic. Assuming this is true (seems right) I
don't think that there _is_ going to be a "natural"
homeomorphism.
************************
David C. Ullrich
.
- References:
- Compact subsets of {0,1}^N
- From: William Elliot
- Re: Compact subsets of {0,1}^N
- From: David C . Ullrich
- Re: Compact subsets of {0,1}^N
- From: William Elliot
- Re: Compact subsets of {0,1}^N
- From: David C . Ullrich
- Re: Compact subsets of {0,1}^N
- From: William Elliot
- Re: Compact subsets of {0,1}^N
- From: David C . Ullrich
- Re: Compact subsets of {0,1}^N
- From: William Elliot
- Re: Compact subsets of {0,1}^N
- From: David C . Ullrich
- Compact subsets of {0,1}^N
- From: William Elliot
- Compact subsets of {0,1}^N
- Prev by Date: Re: Cantor and the binary tree
- Next by Date: Re: Question about generalized union
- Previous by thread: Compact subsets of {0,1}^N
- Next by thread: Help me master mathematics!
- Index(es):
Relevant Pages
|
