Theorem concerning the internal structure of uncountable subsets of P(N).

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 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,…

 

On Fri, 27 Aug 2004, ray wrote:

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.

What's the character after y3, ? in C Is it ... ?

What's the character after = N ? Is it union, ie \/ or perhaps U ?

What do you mean by yn-1 ? y_n - 1 or y_(n-1) ? x_n for x sub n

 

There is a simple polynomial relating the position (n,m) in the infinite

**********************************

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

*****************************************************

yn-1 means y subscript n-1 I note the ? for ... again. The reason for
this is that I prepared the message in Word.

*****************************************************

 

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

 

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.

 

From: Mike Terry <>
Newsgroups: sci.math, alt.math.recreational
Subject: Re: Theorem concerning the internal structure of uncountable
subsets of P(N).

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

----

 

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.

Dale.

 

Lemma. Let C be a collection of subsets of N such that for all A in
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.

 

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.