Results 1 to 8 of 8

Thread: 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
    19,771
    Thanks
    3028
    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 $\displaystyle \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 $\displaystyle \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

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

    and $\displaystyle P_2$ is a countable set. And you can see that $\displaystyle P_2$ could be injected in $\displaystyle \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

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

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

    So I should show that $\displaystyle 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
    21,776
    Thanks
    2823
    Awards
    1
    It should be clear to you that we can take the set $\displaystyle A$ as $\displaystyle \mathbb{Z}^ +$.
    Now list the prime numbers: $\displaystyle P= \left\{ {p_1 ,p_2 ,p_3 , \cdots ,p_n , \cdots } \right\}$. For example: $\displaystyle p_1 = 2\;,\,p_2 = 3\;\& \,p_6 = 13$.

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

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

    Let us look at some examples: $\displaystyle 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 $\displaystyle f$ is an injection from $\displaystyle \mathbb{F}$ to $\displaystyle \mathbb{Z}^+$.
    Thereby proving that $\displaystyle \mathbb{F}$ is countable.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Jan 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: Oct 8th 2010, 01:59 PM
  3. Replies: 1
    Last Post: Feb 9th 2010, 01:51 PM
  4. Countable Sets
    Posted in the Calculus Forum
    Replies: 0
    Last Post: Dec 8th 2008, 05:17 PM
  5. Replies: 11
    Last Post: Oct 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum