Results 1 to 6 of 6

Math Help - [SOLVED] Cardinality

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    [SOLVED] Cardinality

    Which of the following sets has the greatest cardinality?

    (A) \mathbb{R}

    A: Card(\mathbb{R})=c

    (B) The set of all functions from \mathbb{Z}\to\mathbb{Z}

    B: I think this is countable infinite (\mathbb{Z}\to\mathbb{Z})\sim\mathbb{N}

    (C) The set of all functions from \mathbb{R}\to{ 0,1}

    C: This is the answers but why?

    (D) The set of all finite subsets of \mathbb{R}

    D: Not sure how to determine cardinality here

    (E) The set of all polynomials with coefficients in \mathbb{R}

    E: I think this countable infinite too.
    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
    I'll write something equivalent

    Quote Originally Posted by dwsmith View Post
    Which of the following sets has the greatest cardinality?

    (A) \mathbb{R}

    A: Card(\mathbb{R})=c
    Right.

    (B) The set of all functions from \mathbb{Z}\to\mathbb{Z}

    B: I think this is countable infinite (\mathbb{Z}\to\mathbb{Z})\sim\mathbb{N}
    This is surely not countable. Not even \{0,1\}^\omega is countable. In fact, \mathbb{Z}^\mathbb{Z}\simeq\mathbb{R}

    (C) The set of all functions from \mathbb{R}\to{ 0,1}

    C: This is the answers but why?
    In general \{0,1\}^A\simeq\mathcal{P}(A)

    (D) The set of all finite subsets of \mathbb{R}

    D: Not sure how to determine cardinality here
    This is equipotent to the reals. To see this let \mathcal{R}_n=\left\{E\subseteq\mathbb{R}:\text{ca  rd }E=n\right\} then clearly \text{card }\mathbb{R}\leqslant \text{card }\mathcal{R}_n\leqslant\text{card }\mathbb{R}^n=\mathbb{R} so that \mathcal{R}_n\simeq\mathbb{R}. So, then your set, call it W, can be written as \bigcup_{n\in\mathbb{N}}\mathcal{R}_n and there's a theorem which says that if the indexing set is countable and all of the sets being united have the same cardinality which is greater than \aleph_0 then the union has the same cardinality as each set in the union.

    (E) The set of all polynomials with coefficients in \mathbb{R}

    E: I think this countable infinite too.
    Surely not isn't f(x)=a,\text{ }a\in\mathbb{R} a subset of this and isn't that clearly equipotent to \mathbb{R}? In fact, since a polynomial is completely determined by it's coefficients this set is equipotent to that described in D)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,708
    Thanks
    1638
    Awards
    1
    The set \mathbb{Q} is the set of rationals and the set \mathcal{P}(\mathbb{Q}) is the power set.
    Define f:\mathbb{R}\to \mathcal{P}(\mathbb{Q}) as a\mapsto \{x\in \mathbb{Q}:x<a,~a\in\mathbb{R}\}.
    Can you show that f is an injection?
    If so then card(\mathcal{P}(\mathbb{N}) )= card(\mathcal{P}(\mathbb{Q}))<card(\mathbb{R})
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dwsmith View Post
    Which of the following sets has the greatest cardinality?


    All but (c) have the same cardinality 2^{\aleph_0}=c


    (A) \mathbb{R}

    A: Card(\mathbb{R})=c

    (B) The set of all functions from \mathbb{Z}\to\mathbb{Z}

    B: I think this is countable infinite (\mathbb{Z}\to\mathbb{Z})\sim\mathbb{N}


    Its cardinality is, by definition, |\mathbb{Z}|^{|\mathbb{Z}|}=\aleph_0^{\aleph_0}=c


    (C) The set of all functions from \mathbb{R}\to{ 0,1}

    C: This is the answers but why?


    Its cardinality is |(0,1)|^{|\mathbb{R}|}=c^c>c


    (D) The set of all finite subsets of \mathbb{R}

    D: Not sure how to determine cardinality here


    For every n\in\mathbb{N}\,\,\exists\,c=2^{\aleph_0} subsets of \mathbb{R} with n elements, so the set we're dealing with has cardinality c\cdot \aleph_0=c


    (E) The set of all polynomials with coefficients in \mathbb{R}

    E: I think this countable infinite too.

    This last one is very similar to the previous set so I'll let it to you

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Drexel28 View Post
    In general \{0,1\}^A\simeq\mathcal{P}(A)

    Is the A here referring to (A) which is the reals?
    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 dwsmith View Post
    Is the A here referring to (A) which is the reals?
    No. For any set A we have that \{0,1\}^A=\left\{f:A\to\{0,1\}\right\} is equipotent to \mathcal{P}(A)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 4th 2010, 12:21 PM
  2. cardinality, ZFC
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 24th 2010, 04:22 PM
  3. [SOLVED] Cardinality (easy)
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: April 19th 2010, 03:04 PM
  4. Cardinality of R x R
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2009, 04:34 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: April 28th 2009, 11:30 AM

Search Tags


/mathhelpforum @mathhelpforum