Results 1 to 2 of 2

Math Help - countable sets

  1. #1
    Newbie
    Joined
    May 2012
    From
    here
    Posts
    8

    countable sets

    I need some help with this proof:

    Let C be a countable set. Prove C^n is countable for all n.

    I was thinking to show that the Cartesian product of any countable sets is countable by writing them out in a table and going through the elements diagonally to count them, similar to a proof I have seen to show that the rational numbers are countable.

    this proves C^2 is countable since C is countable.
    then using induction I can say that C^n+1 is countable because it = C^n (which is countable from the induction premise) x C and is therefore the cartesian product of two countable sets.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1

    Re: countable sets

    Quote Originally Posted by stuffthings View Post
    Let C be a countable . Prove C^n is countable for all n.
    Suppose that \mathbb{N} is the set of natural numbers.
    Map \mathbb{N}\times\mathbb{N}\to\mathbb{N} by (j,k)\mapsto 2^j\cdot 3^k.
    Show that is an injection.
    Thus C\times C is countable. Now use induction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 05:26 PM
  2. Open sets and sets of interior points
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: August 9th 2011, 03:10 AM
  3. Metric spaces, open sets, and closed sets
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 16th 2011, 05:17 PM
  4. Replies: 9
    Last Post: November 6th 2010, 12:47 PM
  5. Approximation of borel sets from the top with closed sets.
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 18th 2010, 08:51 AM

Search Tags


/mathhelpforum @mathhelpforum