Results 1 to 6 of 6

Math Help - Which of the following sets is uncountable?

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    93

    Which of the following sets is uncountable?

    P(N) (N is the natural number set.)
    Q
    Z
    [0, 1] n Q
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by treetheta View Post
    P(N) (N is the natural number set.)
    Q
    Z
    [0, 1] n Q
    Its P(N) but it's important you understand why the others are countable. (I take it P means power set).

    First of. If a set is countable then a subset of it is also countable.

    So... Is \mathbb{Q} countable?

    If it is then [0, 1] \cap \mathbb{Q} will be countable.

    Surely you can tell that \mathbb{Z} is countable?

    Do you know anything about cardinality yet?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Deadstar View Post
    Its P(N) but it's important you understand why the others are countable. (I take it P means power set).

    First of. If a set is countable then a subset of it is also countable.

    So... Is \mathbb{Q} countable?

    If it is then [0, 1] \cap \mathbb{Q} will be countable.

    Surely you can tell that \mathbb{Z} is countable?

    Do you know anything about cardinality yet?
    Well I think the justification of why \mathcal{P}(\mathbb{N}) isn't countable is non-trivial.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Drexel28 View Post
    Well I think the justification of why \mathcal{P}(\mathbb{N}) isn't countable is non-trivial.
    Ya no way could I be fully proving that of the top of my head. Could prove the rest are countable though...

    To be honest I kinda misinterpreted the question as 'which one is uncountable' so I figured try to show OP how to eliminate the countable ones. Never the less... If OP is learning about cardinality that could be used via Cantors card(x) < card(P(x)) theorem.
    Last edited by Deadstar; April 17th 2010 at 06:12 PM. Reason: added stuff
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Deadstar View Post
    Ya no way could I be fully proving that of the top of my head. Could prove the rest are countable though...

    To be honest I kinda misinterpreted the question as 'which one is uncountable' so I figured try to show OP how to eliminate the countable ones. Never the less... If OP is learning about cardinality that could be used via Cantors card(x) < card(P(x)) theorem.
    It's easier to prove that \mathbb{R}\simeq(0,1)\simeq\mathcal{P}(\mathbb{N}) from where the conclusion follows immediately, but yes I was thinking of Cantor's theorem too.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2008
    Posts
    93
    I think i can see why P(N) is countable cus usually when you take all the subsets of N right? and thats not countable cus there's alot of sets i really suck at proving stuff I looked at cantors therom

    Proof: It suffices to show that [0, 1] is uncountable (see Exercise 7). If
    not, then we have a bijection from N to [0, 1]. This is a sequence (x) that
    lists all numbers in [0, 1], in some order. By considering the canonical
    decimal expansions, we will construct a number not on the list.
    Xl = CI,I CI,2 C I.3
    X2 = C2, I C2,2 C 2.3
    X3 = C3,IC3,2C3.3
    Suppose that the expansions appear in order as indicated above. We
    build a canonical decimal expansion that disagrees with every expansion
    in our list. Let an = 1 if Cn,n = 0, and an = 0 if Cn,n > o. Now (a) disagrees
    in position n with the expansion of Xn. Furthermore, since (a) has no 9, (a)
    cannot be the alternative expansion of any number in our list. Therefore,
    the expansion (a) does not represent a number in our list. By Theorem
    13.25, (a) is the canonical expansion of some real number. Thus our list
    does not contain expansions for all real numbers in [0, 1]. .

    but i dont really get how to use it
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. countable & uncountable sets
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 7th 2010, 08:43 PM
  2. Countable and Uncountable sets
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: October 21st 2010, 12:58 PM
  3. countable and uncountable sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2009, 01:40 PM
  4. Countables and Uncountable sets.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 8th 2008, 11:40 PM
  5. Uncountable sets
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 14th 2006, 11:10 AM

Search Tags


/mathhelpforum @mathhelpforum