Results 1 to 9 of 9

Math Help - Countability

  1. #1
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273

    Countability

    Q- Prove that the collection of all finite subsets of N are countable

    What I have so far:

    Let A_i be the set of all subsets of \mathbb{N} consisting of i elements, A be the set of all finite subsets of \mathbb{N}. Then A is a union of A_i....

    Now I need to find a bijective function of this union to the real numbers? How should I proceed from where I am?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member mabruka's Avatar
    Joined
    Jan 2010
    From
    Mexico City
    Posts
    150
    Wait! You want to prove that A is countable so

    you need a bijective function from \mathbb{N} to A right?
    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 sfspitfire23 View Post
    Q- Prove that the collection of all finite subsets of N are countable

    What I have so far:

    Let A_i be the set of all subsets of \mathbb{N} consisting of i elements, A be the set of all finite subsets of \mathbb{N}. Then A is a union of A_i....

    Now I need to find a bijective function of this union to the real numbers? How should I proceed from where I am?

    Thanks
    Lemma: \mathbb{N}^m is countable for all m\in\mathbb{N}

    Proof: Let \tau:\mathbb{N}\mapsto\mathbb{N}^m be given by n\mapsto(n\underbrace{1,\cdots,1}_{m-1\text{ times}}). This is clearly an injection.

    Now, let \eta:\mathbb{N}^m\mapsto\mathbb{N} be given by (n_1,\cdots,n_m)\mapsto p_1^{n_1}\cdots p_m^{n_m} where p_k is the kth prime. It is clear that this is an injection since the representation of a number by a prime decomposition is unique (fundamental theorem of arithmetic)

    So, the conclusion follows by virtue of the Schroder-Bernstein theorem. \blacksquare

    Now, let A_m be set of all finite subsets of \mathbb{N} with cardinality m. Define \gamma:A_m\mapsto\mathbb{N}_m by \{n_1,\cdots,n_m\}\mapsto (n_1,\cdots,n_m) where n_1\leqslant\cdots\leqslant n_m (this is possible because of finiteness). This is clearly an injection, for to suppose that (n_1,\cdots,n_m)=(n'_1,\cdots,n'_m) would mean that n_1=n'_1,\cdots,n_m=n'_m and so \{n_1,\cdots,n_m\}=\{n'_1,\cdots,n'_m\}. It follows that each A_m is countable.

    And then since A=\bigcup_{j=1}^{\infty}A_j it follows that A is the countable union of countable sets, and thus countable.
    Last edited by Drexel28; February 15th 2010 at 07:26 PM. Reason: Typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,912
    Thanks
    1760
    Awards
    1
    Quote Originally Posted by sfspitfire23 View Post
    Prove that the collection of all finite subsets of N are countable.
    Here are my suggestions. Lets agree that \mathbb{N} = \mathbb{Z}^ +
    Let \mathbb{P}=\left\{ {p_1 ,p_2 ,p_3 , \cdots } \right\} be a listing of the primes. Let  \mathbb{A} = \left\{ {X \subseteq \mathbb{N}:\left| X \right| < \infty } \right\}, the finite subsets.
    If X\in \mathbb{A} define a mapping \Theta :\mathbb{A} \mapsto \mathbb{N} as \Theta (X) = \prod\limits_{k \in X} {p_k } .
    Show that \Theta is an injection.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273
    Drexel, I assume that instead of \eta:\mathbb{N}\mapsto\mathbb{N} you meant \eta:\mathbb{N}^m\mapsto\mathbb{N}? I think that is the only way the Bernstein-Schroeder theorem works?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273
    .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by sfspitfire23 View Post
    Drexel, I assume that instead of \eta:\mathbb{N}\mapsto\mathbb{N} you meant \eta:\mathbb{N}^m\mapsto\mathbb{N}? I think that is the only way the Bernstein-Schroeder theorem works?
    yes..typo.
    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 sfspitfire23 View Post
    Drexel, I assume that instead of \eta:\mathbb{N}\mapsto\mathbb{N} you meant \eta:\mathbb{N}^m\mapsto\mathbb{N}? I think that is the only way the Bernstein-Schroeder theorem works?
    Obviously. In retrospect, here is a better way to do this problem.

    Let \mathbb{N}^m be as normal and define on it the relation \left(n_1,\cdots,n_m\right)\overset{\pi_m}{\sim}\l  eft(n'_1,\cdots,n'_m\right)\Leftrightarrow \{n_1,\cdots,n_m\}=\{n'_1,\cdots,n'_m\} which (as can be readily proved) is an equivalence relation, and thus forms a partition \pi_m of \mathbb{N}^m. Define \alpha:\pi_m\mapsto\mathbb{N}^m by \left[(n_1,\cdots,n_m)\right]\mapsto(n_1,\cdots,n_m) (make the proper addendum so that mapping is well-defined). Clearly this is an injection. Now, form a mapping \gamma:A_m\mapsto\pi_m by \{n_1,\cdots,n_m\}\mapsto\left[(n_1,\cdots,n_m)\right]. This is readily verified to be a bijection. It follows that \alpha\gamma:A_m\mapsto\mathbb{N}^m is an injection and so A_m is countable by the lemma. And since A=\bigcup_{j=1}^{\infty}A_j and the countable union of countable sets is countable it follows that A is countable.
    Last edited by Drexel28; February 15th 2010 at 09:36 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273
    thanks a lot!
    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 Discrete Math Forum
    Replies: 2
    Last Post: December 23rd 2009, 01:09 AM
  3. Bijection - Countability
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 20th 2009, 09:42 AM
  4. Countability
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 28th 2008, 11:49 AM
  5. Countability
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2008, 07:26 AM

Search Tags


/mathhelpforum @mathhelpforum