Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: proving a set is countable

  1. #1
    Super Member
    Sep 2008

    proving a set is countable


    Can anyone please help me with this question, I am finding it very hard. I am not sure where to begin
    Attached Thumbnails Attached Thumbnails proving a set is countable-screen-shot-2013-11-05-15.19.09.png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Nov 2010

    Re: proving a set is countable

    Let's write $\displaystyle S(E)$ a slightly different way:

    $\displaystyle S(E) = \left\{A \subseteq E \mid \text{card}(A) = n, n\in \mathbb{N}\right\}$

    Note that this is similar to the power set, but the power set includes subsets with infinite cardinality and the empty set.

    Let $\displaystyle P$ be the set of primes (as suggested in the hint). Define $\displaystyle f:E \to P$ to be any injection. Such an injection exists since both $\displaystyle E$ and $\displaystyle P$ are countable. Then, define $\displaystyle g:S(E) \to \mathbb{N}$ by $\displaystyle g(A) = \prod_{e \in A}f(e)$. Prove that $\displaystyle g$ is an injection.

    Another proof of this: If $\displaystyle E$ is finite, then $\displaystyle S(E) = \mathcal{P}(E) \setminus \{\emptyset\}$. Hence, $\displaystyle \text{card}(S(E)) = 2^{\text{card}(E)}-1$ where $\displaystyle \mathcal{P}(E)$ is the power set of $\displaystyle E$, so $\displaystyle S(E)$ is finite and therefore countable. Suppose $\displaystyle E$ is infinite and let $\displaystyle E = \{e_0,e_1,\ldots\}$ be an enumeration of the elements of $\displaystyle E$. Then, define $\displaystyle h: S(E) \to \mathbb{N}$ by $\displaystyle h(A) = \sum_{e_k \in A}2^k$. Show that $\displaystyle h$ is a bijection.
    Last edited by SlipEternal; Nov 5th 2013 at 07:00 AM.
    Thanks from Tweety
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Jun 3rd 2013, 04:48 PM
  2. Replies: 5
    Last Post: Jan 9th 2013, 06:14 AM
  3. proving the set of finite decimals is countable
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Sep 29th 2010, 01:07 PM
  4. Proving countable set
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 14th 2010, 01:29 PM
  5. Replies: 11
    Last Post: Oct 11th 2008, 06:49 PM

Search Tags

/mathhelpforum @mathhelpforum