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

Discussion in 'Recreational Math' started by ray, Aug 28, 2004.

  1. ray

    ray Guest

    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,…
     
    ray, Aug 28, 2004
    #1
    1. Advertisements

  2. 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
     
    William Elliot, Aug 28, 2004
    #2
    1. Advertisements

  3. ray

    ray Guest

    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.

    *****************************************************
     
    ray, Aug 28, 2004
    #3
  4. ray

    Odysseus Guest

    [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, Aug 28, 2004
    #4
  5. ray

    Mike Terry Guest

    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.
     
    Mike Terry, Aug 29, 2004
    #5
  6. 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

    ----
     
    William Elliot, Aug 29, 2004
    #6
  7. ray

    W. Dale Hall Guest

    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.
     
    W. Dale Hall, Aug 30, 2004
    #7
  8. ray

    ray Guest

    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.
     
    ray, Sep 11, 2004
    #8
  9. ray

    Chas Brown Guest

    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
     
    Chas Brown, Sep 13, 2004
    #9
  10. ray

    ray Guest

    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.
     
    ray, Sep 21, 2004
    #10
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.