Results 1 to 14 of 14

Math Help - set of all finite subsets of a continuum has cardinality continuum

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    55

    set of all finite subsets of a continuum has cardinality continuum

    Hi. I'm learning about equivalent sets in a real analysis class and am struggling a bit with the abstractness of it. Would someone be able to explain in very basic language how to:

    Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

    I guess I'm not totally sure what a continuum is. Is it just any set with a bijection between it and the set of real numbers?

    From what I know a set has cardinality of continuum if it is equivalent to the set of all sequences whose elements are the digits 0 and 1 (which is equivalent to the set of real numbers).

    So I need a way to write each finite subset as a sequence of 1s and 0s to create a bijection between it and the set of all sequences whose elements are the digits 0 and 1?

    I'm definitely confused about where to start, and would really appreciate some help!

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by minivan15 View Post
    Hi. I'm learning about equivalent sets in a real analysis class and am struggling a bit with the abstractness of it. Would someone be able to explain in very basic language how to:

    Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

    I guess I'm not totally sure what a continuum is. Is it just any set with a bijection between it and the set of real numbers?

    From what I know a set has cardinality of continuum if it is equivalent to the set of all sequences whose elements are the digits 0 and 1 (which is equivalent to the set of real numbers).

    So I need a way to write each finite subset as a sequence of 1s and 0s to create a bijection between it and the set of all sequences whose elements are the digits 0 and 1?

    I'm definitely confused about where to start, and would really appreciate some help!

    Thanks!
    I could prove this whole thing for you...but I have a feeling that's not what you want.

    So, what exactly DO you want?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    Well ideally I would like to understand how to prove it myself. If you could show me your proof with explanations that might be very helpful! If you are unwilling to do that, I guess the next best thing would be a very good starting point to answering the question!

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by minivan15 View Post
    Well ideally I would like to understand how to prove it myself. If you could show me your proof with explanations that might be very helpful! If you are unwilling to do that, I guess the next best thing would be a very good starting point to answering the question!

    Thanks!
    Well, my point was that I could either give you a one-line proof, but that depends on how much you know. If you really want to understand the one-line proof I may have to prove quite a few laborious lemmas. What's your background in cardinal numbers?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    I'm afraid I don't know any of the cardinality symbols (e.g. aleph-naught), or how to operate on them (I've been researching my problem and have seen stuff about adding and subtracting cardinalities, but I haven't seen that stuff before).

    I know Cantor's proof that R is uncountable. I can prove the set of all sequences whose elements are 0 and 1 is uncountable (basically the same method that Cantor used). I can prove that R is equivalent to this set. I've seen the Cantor-Bernstein-Schroeder Theorem. ...unfortunately that's about the extent of my knowledge.

    If you are able to prove the result without using cardinality symbols, I'm sure I could follow. Maybe if you have a particular lemma that you want to avoid proving, you could mention the result and I can tell you if I understand it/ have seen it?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by minivan15 View Post
    I'm afraid I don't know any of the cardinality symbols (e.g. aleph-naught), or how to operate on them (I've been researching my problem and have seen stuff about adding and subtracting cardinalities, but I haven't seen that stuff before).

    I know Cantor's proof that R is uncountable. I can prove the set of all sequences whose elements are 0 and 1 is uncountable (basically the same method that Cantor used). I can prove that R is equivalent to this set. I've seen the Cantor-Bernstein-Schroeder Theorem. ...unfortunately that's about the extent of my knowledge.

    If you are able to prove the result without using cardinality symbols, I'm sure I could follow. Maybe if you have a particular lemma that you want to avoid proving, you could mention the result and I can tell you if I understand it/ have seen it?

    Thanks!
    How about that the set of all reals is equipotent to the power set of the natural numbers.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    Sorry, I haven't seen that.

    In my class we've been working through a bunch of problems, and that hasn't come up yet. Is there a way to prove the result without using it?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by minivan15 View Post
    Sorry, I haven't seen that.

    In my class we've been working through a bunch of problems, and that hasn't come up yet. Is there a way to prove the result without using it?
    I COMPLETELY misread your question. The set of all finite subsets of \mathbb{N} is countable (has the cardinality of \mathbb{N}). Ok? So do you still want me to prove it?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    Yeah, I would like to see a proof of the bold statement in my first post:

    Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

    Another problem I want to do is:

    prove that the set of all sequences of positive integers has cardinality continuum.

    I'm hoping to see an explanation of one of these problems, and use the example to figure out how to do the other one. You can do whichever you'd like.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by minivan15 View Post
    Yeah, I would like to see a proof of the bold statement in my first post:

    Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

    Another problem I want to do is:

    prove that the set of all sequences of positive integers has cardinality continuum.

    I'm hoping to see an explanation of one of these problems, and use the example to figure out how to do the other one. You can do whichever you'd like.
    How about an idea, and you try to prove the second one. It will be good for you. It can be shown pretty easily that the open unit interval has the same cardinality as the continuum, so think about numbers like .12453145632147... don't they sort of remind you of \{1,2,4,5,3,1,\cdots\}.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    yeah I actually did a problem where I had to come up with a bijection between R and (0,1). I came up with


    f(x) = ( arctan(x) + pi/2 ) / pi

    (hopefully that's right!) Anyways, finding a bijection between the two sets proves they are of the same cardinality.

    And I see what you're saying... each sequence is like a decimal, so all of the sequences is like the all of the numbers in the interval (0,1). Since this interval has the same cardinality as R, and since the set of all sequences of positive integers is like the interval (0,1) (I'll write it up more mathematically), it has the same cardinality as R, therefore cardinality of the continuum!

    Thanks for the great hint! hopefully that will give me an idea for the other one. Feel free to drop in another hint though
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by minivan15 View Post
    yeah I actually did a problem where I had to come up with a bijection between R and (0,1). I came up with


    f(x) = ( arctan(x) + pi/2 ) / pi

    (hopefully that's right!) Anyways, finding a bijection between the two sets proves they are of the same cardinality.
    I'll take your word that's a bijection. A nice geometrical proof goes as follows. Take the interval and bend it up to form a semi-circle C. Draw a vertical line through \frac{1}{2} and project from this line through C. You'll see that you hit one point on C and one point on \mathbb{R}. This is then an injection. And since clearly the inclusion mapping 0,1)\hookrightarrow\mathbb{R}" alt="f0,1)\hookrightarrow\mathbb{R}" /> given by x\mapsto x is an injection the other way the Schroder-Bernstein theorem finishes the argument

    And I see what you're saying... each sequence is like a decimal, so all of the sequences is like the all of the numbers in the interval (0,1). Since this interval has the same cardinality as R, and since the set of all sequences of positive integers is like the interval (0,1) (I'll write it up more mathematically), it has the same cardinality as R, therefore cardinality of the continuum!

    Thanks for the great hint! hopefully that will give me an idea for the other one. Feel free to drop in another hint though
    I'll try to think of a good hint, and get back to you!
    Follow Math Help Forum on Facebook and Google+

  13. #13
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    Quote Originally Posted by minivan15 View Post
    Hi. I'm learning about equivalent sets in a real analysis class and am struggling a bit with the abstractness of it. Would someone be able to explain in very basic language how to:

    Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

    I guess I'm not totally sure what a continuum is. Is it just any set with a bijection between it and the set of real numbers?

    From what I know a set has cardinality of continuum if it is equivalent to the set of all sequences whose elements are the digits 0 and 1 (which is equivalent to the set of real numbers).

    So I need a way to write each finite subset as a sequence of 1s and 0s to create a bijection between it and the set of all sequences whose elements are the digits 0 and 1?

    I'm definitely confused about where to start, and would really appreciate some help!

    Thanks!
    well....you can prove it like this..

    we can define the exponation of cardinals like that:
    if k_1,k_2are cardinals of two sets A,B, then k_1^{k_2}is the cardinal of the set of all functions mappings Bto A.
    Let the cardinal of the natural numbers to be \aleph_0, and the cardinal of real numbers to be \aleph.
    Then let S be set of the all finite subsets of a continuum.
    For every x\in S,since xis finite, there is a bijection f_x from n(meaning the set \{0,...,n-1\})to x, thus every y\in xcan be written as f_x(m). But we can also see f_x as mapping from \mathbb{N} to x, letting all other natural number map to a strange element adifferent from all real number. Thus now we have mapped all x\in S to some function from \mathbb{N} to \mathbb{R}\cup \{a\}(which have the same cardinality as \mathbb{R}).And clearly this mapping is one-to-one.
    Clearly we have S\succeq \aleph. From above we also have S\preceq\aleph^{\aleph_0}.
    But S\preceq\aleph^{\aleph_0}=(2^{\aleph_0})^{\aleph_0  }=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=\aleph
    So S\sim\aleph, it have the cardinality of a continuum.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by ynj View Post
    well....you can prove it like this..

    we can define the exponation of cardinals like that:
    if k_1,k_2are cardinals of two sets A,B, then k_1^{k_2}is the cardinal of the set of all functions mappings Bto A.
    Let the cardinal of the natural numbers to be \aleph_0, and the cardinal of real numbers to be \aleph.
    Then let S be set of the all finite subsets of a continuum.
    For every x\in S,since xis finite, there is a bijection f_x from n(meaning the set \{0,...,n-1\})to x, thus every y\in xcan be written as f_x(m). But we can also see f_x as mapping from \mathbb{N} to x, letting all other natural number map to a strange element adifferent from all real number. Thus now we have mapped all x\in S to some function from \mathbb{N} to \mathbb{R}\cup \{a\}(which have the same cardinality as \mathbb{R}).And clearly this mapping is one-to-one.
    Clearly we have S\succeq \aleph. From above we also have S\preceq\aleph^{\aleph_0}.
    But S\preceq\aleph^{\aleph_0}=(2^{\aleph_0})^{\aleph_0  }=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=\aleph
    So S\sim\aleph, it have the cardinality of a continuum.
    The poster said that he is not familiar with cardinal arithmetic, so this doesn't work. Also, even if he would accept it I always found cardinal arithmetic to be a little unconvincing.
    Last edited by Chris L T521; February 3rd 2010 at 10:20 PM. Reason: Removed part of post that is no longer relevant.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: February 7th 2011, 11:36 AM
  2. Replies: 0
    Last Post: February 6th 2011, 01:19 AM
  3. Cardinality of the continuum
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: September 22nd 2010, 12:10 AM
  4. A continuum of homomorphic images
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 4th 2010, 12:48 AM
  5. Continuum Hypothesis
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 15th 2010, 07:46 AM

Search Tags


/mathhelpforum @mathhelpforum