Results 1 to 4 of 4

Math Help - Countability

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    22

    Countability

    Q ) For a fixed positive integer k, let P_k(N) be the set of all subsets of N with exactly k elements. Prove that P_k(N) is countable.

    I think that I should find a 1-1 map from P_k(N) into N^k=N*N*...*N (k times). But unfortunately I couldn't prove it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by selinunan View Post
    Q ) For a fixed positive integer k, let P_k(N) be the set of all subsets of N with exactly k elements. Prove that P_k(N) is countable.

    I think that I should find a 1-1 map from P_k(N) into N^k=N*N*...*N (k times). But unfortunately I couldn't prove it.
    If S\in P_k(\mathbb{N}) then S can be well-ordered. Thus, basically write \{a_0,a_1,...,a_{k-1}\} in increasing order. Then consider the mapping \{a_0,...,a_{k-1} \}\mapsto (a_0,a_1,...,a_{k-1}). It depends how formal you want to be that is why I used 'basically' - just to say the idea. I think you might need to use an induction and recursion argument here to write out all the details formally if that is what you are looking for.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    22
    Thank you for your answer.

    And how can I prove it by using induction?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by selinunan View Post
    Thank you for your answer.

    And how can I prove it by using induction?
    If it is true for k i.e. there is injection g: P_k(\mathbb{N}) \to \mathbb{N}^k. Then define f: P_{k+1}(\mathbb{N})\to \mathbb{N}^{k+1} by f(S) = (a,g(S-\{ a \})) where a is least element of S.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. countability of a set
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 6th 2011, 04:18 AM
  2. Countability
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: February 15th 2010, 09:36 PM
  3. Countability
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 23rd 2009, 01:09 AM
  4. Bijection - Countability
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 20th 2009, 09:42 AM
  5. Countability
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 28th 2008, 11:49 AM

Search Tags


/mathhelpforum @mathhelpforum