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 S(E) a slightly different way:

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

    Another proof of this: If E is finite, then S(E) = \mathcal{P}(E) \setminus \{\emptyset\}. Hence, \text{card}(S(E)) = 2^{\text{card}(E)}-1 where \mathcal{P}(E) is the power set of E, so S(E) is finite and therefore countable. Suppose E is infinite and let E = \{e_0,e_1,\ldots\} be an enumeration of the elements of E. Then, define h: S(E) \to \mathbb{N} by h(A) = \sum_{e_k \in A}2^k. Show that 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