Theorem concerning the internal structure of uncountable subsets of P(N).
ray
no x in C do there exist y1,y2,y3,… in C such that x is a subset of
the union of y1,y2,y3,…, then C is countable.
Proof.
We build an enumeration of C as follows. If the union of sets in C is
not equal to N then we extend C to a set C* by putting W = N – C and
C* = C union {W}. Since W is disjoint from all the other sets in C,
this extension does not affect our hypothesis.
Now let F map C* onto a subset of N as follows.
Select any y1 from C* and let F(y1) = the least number in y1. Now
select any y2 from C* and let F(y) = the least number in y2 –y1. Now
select any y3 from C* and let F(y3) = the least number in y3 – (y2
union y1). Generally, at the nth stage we select any yn in C* and let
F(yn) = the least number in yn – (union of y1,y2,…yn-1). By the
hypothesis, at no stage will yn – (union of y1,y2,…yn-1) be undefined,
since yn is never the subset of the union of y1,y2,…yn-1.
We need to show that F is one to one. Suppose that for some z1 and z2
in C* we have F(z1) = F(z2) = w, say, with z1 appearing earlier in
the construction than z2. Now, w obviously belongs to z1, or else
it could not have been chosen to represent z1, hence w does not belong
to z2 – (union of y1,y2,y3,…z1,…), so w cannot be selected from z2 to
represent F(z2). Hence F(z2) cannot be equal to F(z1).
Thus F is always defined and is one to one. So C* is mapped onto a
subset of N and hence is countable.
It follows that if a collection C of subsets of N is uncountable, then
for some x in C there must exist y1,y2,y3,… in C such that x is a
subset of the union of y1,y2,y3,…
William Elliot
I'll take a look at this but first explain what the special characters
are as they don't show up as you expect.
As it is, Cantor showed a countable number of countable sets is countable,
which is a generalization of your problem. He listed them as
a1, a2, a3, ...
b1, b2, b3, ...
c1, c2, c3, ...
...
He counted them by the upper left corner first a1
then the diagonal b1, a2, ie the upper left corner with a1 shaved off
then the diagonal c1, b2, a3, etc
There is a simple polynomial relating the position (n,m) in the infinite
matrix and the position in the sequence. Let's see, something like
(n + m - 1)(n + m - 2)/2 + m
Which, when it's the right formula, is straight forward to show is
bijection.
> For any collection C of subsets of N (positive whole numbers), if for
> no x in C do there exist y1,y2,y3,… in C such that x is a subset of
What's the character after y3, ? in C Is it ... ?
> the union of y1,y2,y3,…, then C is countable.
>
> Proof.
>
> We build an enumeration of C as follows. If the union of sets in C is
> not equal to N then we extend C to a set C* by putting W = N – C and
What's the character after = N ? Is it union, ie \/ or perhaps U ?
> C* = C union {W}. Since W is disjoint from all the other sets in C,
> this extension does not affect our hypothesis.
>
> Now let F map C* onto a subset of N as follows.
> Select any y1 from C* and let F(y1) = the least number in y1. Now
> select any y2 from C* and let F(y) = the least number in y2 –y1. Now
> select any y3 from C* and let F(y3) = the least number in y3 – (y2
> union y1). Generally, at the nth stage we select any yn in C* and let
> F(yn) = the least number in yn – (union of y1,y2,…yn-1). By the
What do you mean by yn-1 ? y_n - 1 or y_(n-1) ? x_n for x sub n
ray
> matrix and the position in the sequence. Let's see, something like
> (n + m - 1)(n + m - 2)/2 + m
>
> Which, when it's the right formula, is straight forward to show is
> bijection.
>
> > For any collection C of subsets of N (positive whole numbers), if for
>
> What's the character after y3, ? in C Is it ... ?
********
Yes
********
>
> > the union of y1,y2,y3,?, then C is countable.
> >
> > Proof.
> >
> > We build an enumeration of C as follows. If the union of sets in C is
> > not equal to N then we extend C to a set C* by putting W = N ? C and
>
> What's the character after = N ? Is it union, ie \/ or perhaps U ?
**********************************
It is a minus sign, meaning the intersection of N and C complement. I
just felt it would be less messy if the union of all the sets to be
counted was equal to N.
************************************
>
> > C* = C union {W}. Since W is disjoint from all the other sets in C,
> > this extension does not affect our hypothesis.
> >
> > Now let F map C* onto a subset of N as follows.
> > Select any y1 from C* and let F(y1) = the least number in y1. Now
> > select any y2 from C* and let F(y) = the least number in y2 ?y1. Now
> > select any y3 from C* and let F(y3) = the least number in y3 ? (y2
> > union y1). Generally, at the nth stage we select any yn in C* and let
> > F(yn) = the least number in yn ? (union of y1,y2,?yn-1). By the
*****************************************************
yn-1 means y subscript n-1 I note the ? for ... again. The reason for
this is that I prepared the message in Word.
*****************************************************
> What do you mean by yn-1 ? y_n - 1 or y_(n-1) ? x_n for x sub n
>
> > hypothesis, at no stage will yn ? (union of y1,y2,?yn-1) be undefined,
> > since yn is never the subset of the union of y1,y2,?yn-1.
> > We need to show that F is one to one. Suppose that for some z1 and z2
> > in C* we have F(z1) = F(z2) = w, say, with z1 appearing earlier in
> > the construction than z2. Now, w obviously belongs to z1, or else
> > it could not have been chosen to represent z1, hence w does not belong
> > to z2 ? (union of y1,y2,y3,?z1,?), so w cannot be selected from z2 to
> > represent F(z2). Hence F(z2) cannot be equal to F(z1).
> >
> > Thus F is always defined and is one to one. So C* is mapped onto a
> > subset of N and hence is countable.
> >
> > It follows that if a collection C of subsets of N is uncountable, then
> > for some x in C there must exist y1,y2,y3,? in C such that x is a
> > subset of the union of y1,y2,y3,?
> >
Odysseus
>
[snip]
> >
> > > For any collection C of subsets of N (positive whole numbers), if for
> > > no x in C do there exist y1,y2,y3,? in C such that x is a subset of
[quoting William Elliot]
FWIW both the ellipsis (…, in ASCII written "...") and the en-dash
(or minus sign, –) from the original message showed up correctly
here; I'm using Netscape under Mac OS 9. But when posting to Usenet
in general it's best to stick to ASCII representations for symbols
that don't appear on the key-caps of a standard keyboard.
--
Odysseus
Mike Terry
news:e2951aa7.04082...@posting.google.com...
> For any collection C of subsets of N (positive whole numbers), if for
> the union of y1,y2,y3,., then C is countable.
Hi ray,
I've just arrived back from the pub, so sorry if what follows is
alcohol-induced rubish...! :)
If x in C, and C is non-empty, then taking y1,y2,y3,. all equal to x, then x
will always be a subset of the union of y1,y2,y3,., so the premise of your
conclusion can only be true if C is empty (in which case of course C is
countable...)
Regards,
Mike.
William Elliot
Newsgroups: sci.math, alt.math.recreational
Subject: Re: Theorem concerning the internal structure of uncountable
subsets of P(N).
"ray" <ray_...@yahoo.co.uk> wrote in message
>> For any collection C of subsets of N (positive whole numbers), if
>> for no x in C do there exist y1,y2,y3,. in C such that x is a
>> subset of the union of y1,y2,y3,., then C is countable.
>I've just arrived back from the pub, so sorry if
>what follows is alcohol-induced rubish...! :)
>If x in C, and C is non-empty, then taking y1,y2,y3,. all equal to x,
>then x will always be a subset of the union of y1,y2,y3,., so the
>premise of your conclusion can only be true if C is empty (in which
>case of course C is countable...)
I found the same phantom after, non-alcoholic ponderance upon Ray's
question and careful clarification of his non-ascii Word post as:
Not some X, Y1, Y2,.. in C with X subset Union_j Yj
==> C countable
For all X, Y1, Y2,.. in C, not X subset Union_j Yj
==> C countable
----
W. Dale Hall
> For any collection C of subsets of N (positive whole numbers), if for
> no x in C do there exist y1,y2,y3,… in C such that x is a subset of
> the union of y1,y2,y3,…, then C is countable.
>
>
> Proof.
>
> We build an enumeration of C as follows. If the union of sets in C is
> not equal to N then we extend C to a set C* by putting W = N – C and
> C* = C union {W}. Since W is disjoint from all the other sets in C,
> this extension does not affect our hypothesis.
>
> Now let F map C* onto a subset of N as follows.
> Select any y1 from C* and let F(y1) = the least number in y1. Now
> select any y3 from C* and let F(y3) = the least number in y3 – (y2
> union y1). Generally, at the nth stage we select any yn in C* and let
> F(yn) = the least number in yn – (union of y1,y2,…yn-1). By the
> hypothesis, at no stage will yn – (union of y1,y2,…yn-1) be undefined,
> since yn is never the subset of the union of y1,y2,…yn-1.
> We need to show that F is one to one. Suppose that for some z1 and z2
> in C* we have F(z1) = F(z2) = w, say, with z1 appearing earlier in
> the construction than z2. Now, w obviously belongs to z1, or else
> it could not have been chosen to represent z1, hence w does not belong
> to z2 – (union of y1,y2,y3,…z1,…), so w cannot be selected from z2 to
> represent F(z2). Hence F(z2) cannot be equal to F(z1).
>
> Thus F is always defined and is one to one. So C* is mapped onto a
> subset of N and hence is countable.
>
>
Doesn't the construction here assume countability of C*?
Here's the construction as I understand it:
Select a y1 and let F(y1) = min(y1)
Given the definition for {y1, y2, ..., yn}
define F(y(n+1)) = min(y(n+1) \ union(y1,y2,...,yn)).
where I have used \ for the set-theoretic difference.
If C* were uncountable (which I imagine might be an assumption one might
wish to test), how can F be said to be defined on all of C*, if it's
only defined for the sets that can be reached via enumeration by
integral subscripts? What, for instance, could be the value of
F(y_\Omega), where \Omega represents the first uncountable ordinal?
The following may be a fix. Assuming the Axiom of Choice, choose a
well-ordering (I'll call it .<.) of C*. Then one defines F by allowing
F(y) to be
F(y) = min(y \ union(z | z .<. y)).
The hypothesis ensures that y \ union(z | z != y) is nonempty, so
certainly, y \ union(z | z .<. y) will be nonempty.
I don't know how to prove this without some ordering of the set C*,
however.
>
> It follows that if a collection C of subsets of N is uncountable, then
> for some x in C there must exist y1,y2,y3,… in C such that x is a
> subset of the union of y1,y2,y3,…
Dale.
ray
C, there exists a y in A such that y does not belong to any other B in
C. In other words, every set belonging to C has at least one member
that is unique to it. Then C is countable.
Proof.
We define a function F from C into N as follows, F(A) = the least x in
A such that x belongs to A and x does not belong to any other B in C.
The hypothesis of the theorem assures us that such an x can be found
for each A in C, thus F is defined for every A in C. Since F is a one
to one mapping from C onto a subset of N, then C is countable.
Theorem. If a collection of subsets of N is uncountable, then there
must exist an A in C such that there exist B_1, B_2, B_3? in C such
that A is a subset of the union of B_1, B_2, B_3?
From the Lemma, if a collection of subsets of N is uncountable then,
for some A in C, for any x_i in A there must exist a B_i in C such
that x_i is in B_i, (in other words, not every member of C can have an
element that is unique to it). Then A will be a subset of the union of
those B_i?s.
Chas Brown
Next would be...
Theorem. If a collection C of subsets of N is uncountable, then there
are an uncountable number of elements A in C such that there exist
B_1, B_2, B_3, ... in C such that A is a subset of the union of B_1,
B_2, B_3, ...
Cheers - Chas
ray
> > From the Lemma, if a collection of subsets of N is uncountable then,
> > for some A in C, for any x_i in A there must exist a B_i in C such
> > that x_i is in B_i, (in other words, not every member of C can have an
> > element that is unique to it). Then A will be a subset of the union of
> > those B_i?s.
>
> Next would be...
>
> Theorem. If a collection C of subsets of N is uncountable, then there
> are an uncountable number of elements A in C such that there exist
> B_1, B_2, B_3, ... in C such that A is a subset of the union of B_1,
> B_2, B_3, ...
>
> Cheers - Chas
I see what you mean. If I remove the offending A from my uncountable
collection of subsets of N then what I have left must still be
uncountable, because aleph(x) minus 1 is still aleph(x), ( roughly,
infinity minus 1 is infinity ). And since we still have uncountably
many subsets of N in our collection we can use a backward induction
argument by removing another A. No matter how we remove a countable
number of A's from our collection there will still be more A's left
behind because our (depleted) collection will still be uncountable. So
there are uncountbly many A's.