Results 1 to 8 of 8

Math Help - Countable sets?

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Countable sets?

    How can I show that if A is a countable set, then A has countably many finite subsets?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,697
    Thanks
    1469
    Quote Originally Posted by posix_memalign View Post
    How can I show that if A is a countable set, then A has countably many finite subsets?
    First show that for every integer n, the collection of subsets with exactly n members is countable. Then show that the union of all those sets (a countable collection of countable sets) is countable.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by HallsofIvy View Post
    First show that for every integer n, the collection of subsets with exactly n members is countable. Then show that the union of all those sets (a countable collection of countable sets) is countable.
    To show that the collection of subsets with exactly n members are countable (for every integer n), can that be done by first showing that n = 1 is countable, then showing n+1 is countable under the assumption that n is countable -- i.e. induction?

    If that is a correct way to proceed, how exactly does one show something as trivial that a set with one element is countable? I really having some trouble with this as I don't understand the operations that should be used.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    By definition, a set A is countable if there is a injection from A to \mathbb{N}, so trivially any finite set (including the empty set) is countable. But you need to show that the collection of subsets having n elements is countable as Hallsoflvy said
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by tah View Post
    By definition, a set A is countable if there is a injection from A to \mathbb{N}, so trivially any finite set (including the empty set) is countable. But you need to show that the collection of subsets having n elements is countable as Hallsoflvy said
    A collection of subsets with exactly n elements, where n is of the natural numbers -- doesn't that mean every set in the collection is merely a finite set and is thus countable?
    Or does "collection of subsets" mean something else than merely all the sets that can be constructed with n elements where n is of the natural numbers?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    Not sure I understand you. We mean the collection itself is countable (the set of subsets)
    in fact HallsofIvy said

    First show that for every integer n, the collection of subsets with exactly n members IS countable.

    For instance the collection of subsets with cardinality 2 is

    P_2 = \{\{0,1\},\{0,2\},\cdots,\{1,2\},\{1,3\},\cdots\}

    and P_2 is a countable set. And you can see that P_2 could be injected in \mathbb{N}^2
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by tah View Post
    Not sure I understand you. We mean the collection itself is countable (the set of subsets)
    in fact HallsofIvy said

    First show that for every integer n, the collection of subsets with exactly n members IS countable.

    For instance the collection of subsets with cardinality 2 is

    P_2 = \{\{0,1\},\{0,2\},\cdots,\{1,2\},\{1,3\},\cdots\}

    and P_2 is a countable set. And you can see that P_2 could be injected in \mathbb{N}^2
    Sorry that I don't understand this, I'm trying really hard.

    So I should show that P_n is countable? Can I do this with induction?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,658
    Thanks
    1615
    Awards
    1
    It should be clear to you that we can take the set A as \mathbb{Z}^ +.
    Now list the prime numbers:  P= \left\{ {p_1 ,p_2 ,p_3 , \cdots ,p_n , \cdots } \right\}. For example: p_1  = 2\;,\,p_2  = 3\;\& \,p_6  = 13.

    Use the set of finite subsets of \mathbb{Z}^ +: \mathbb{F} = \left\{ {X:X \subseteq \mathbb{Z}^ +  \;\& \;X \text{ in finite}} \right\}.

    Define a function f:\mathbb{F} \mapsto \mathbb{Z}^ +  \;,\;f(X) = \prod\limits_{n \in X} {p_n } .

    Let us look at some examples: f\left( {\left\{ 6 \right\}} \right) = 13,\;f\left( {\left\{ {2,4} \right\}} \right) = 3 \cdot 7\;\& \;f\left( {\left\{ {3,4,6} \right\}} \right) = 5 \cdot 7 \cdot 13.

    Now using the prime factorization theorem, it easy to prove that f is an injection from \mathbb{F} to \mathbb{Z}^+.
    Thereby proving that \mathbb{F} is countable.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  3. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  4. Countable Sets
    Posted in the Calculus Forum
    Replies: 0
    Last Post: December 8th 2008, 05:17 PM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum