Results 1 to 9 of 9

Thread: 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 $\displaystyle A_i$ be the set of all subsets of $\displaystyle \mathbb{N}$ consisting of $\displaystyle i$ elements, $\displaystyle A$ be the set of all finite subsets of $\displaystyle \mathbb{N}$. Then $\displaystyle A$ is a union of $\displaystyle 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 $\displaystyle \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
    22
    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 $\displaystyle A_i$ be the set of all subsets of $\displaystyle \mathbb{N}$ consisting of $\displaystyle i$ elements, $\displaystyle A$ be the set of all finite subsets of $\displaystyle \mathbb{N}$. Then $\displaystyle A$ is a union of $\displaystyle 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: $\displaystyle \mathbb{N}^m$ is countable for all $\displaystyle m\in\mathbb{N}$

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

    Now, let $\displaystyle \eta:\mathbb{N}^m\mapsto\mathbb{N}$ be given by $\displaystyle (n_1,\cdots,n_m)\mapsto p_1^{n_1}\cdots p_m^{n_m}$ where $\displaystyle p_k$ is the $\displaystyle k$th 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. $\displaystyle \blacksquare$

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

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

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    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 $\displaystyle \mathbb{N} = \mathbb{Z}^ + $
    Let $\displaystyle \mathbb{P}=\left\{ {p_1 ,p_2 ,p_3 , \cdots } \right\}$ be a listing of the primes. Let $\displaystyle \mathbb{A} = \left\{ {X \subseteq \mathbb{N}:\left| X \right| < \infty } \right\}$, the finite subsets.
    If $\displaystyle X\in \mathbb{A}$ define a mapping $\displaystyle \Theta :\mathbb{A} \mapsto \mathbb{N}$ as $\displaystyle \Theta (X) = \prod\limits_{k \in X} {p_k } $.
    Show that $\displaystyle \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 $\displaystyle \eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\displaystyle \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 $\displaystyle \eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\displaystyle \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
    22
    Quote Originally Posted by sfspitfire23 View Post
    Drexel, I assume that instead of $\displaystyle \eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\displaystyle \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 $\displaystyle \mathbb{N}^m$ be as normal and define on it the relation $\displaystyle \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 $\displaystyle \pi_m$ of $\displaystyle \mathbb{N}^m$. Define $\displaystyle \alpha:\pi_m\mapsto\mathbb{N}^m$ by $\displaystyle \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 $\displaystyle \gamma:A_m\mapsto\pi_m$ by $\displaystyle \{n_1,\cdots,n_m\}\mapsto\left[(n_1,\cdots,n_m)\right]$. This is readily verified to be a bijection. It follows that $\displaystyle \alpha\gamma:A_m\mapsto\mathbb{N}^m$ is an injection and so $\displaystyle A_m$ is countable by the lemma. And since $\displaystyle A=\bigcup_{j=1}^{\infty}A_j$ and the countable union of countable sets is countable it follows that $\displaystyle A$ is countable.
    Last edited by Drexel28; Feb 15th 2010 at 08: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: Jan 6th 2011, 03:18 AM
  2. Countability
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 23rd 2009, 12:09 AM
  3. Bijection - Countability
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: Oct 20th 2009, 08:42 AM
  4. Countability
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: Nov 28th 2008, 10:49 AM
  5. Countability
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 12th 2008, 06:26 AM

Search Tags


/mathhelpforum @mathhelpforum