Results 1 to 7 of 7

Math Help - Show that P={X \in P(Z+)|X finite} is countably infinite.

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    50

    Show that P={X \in P(Z+)|X finite} is countably infinite.

    I have no idea where to start.

    Let P= \{X \in \wp(Z^+)|X  finite \}. Prove that P is denumerable (countably infinite), where  \wp(Z^+) is the power set of Z^+

    I tried to find f:Z^+ \longrightarrow P that is one-to-one and onto. But that attemt was failed. I also tried to find something that might be equivalent to Z^+ and P and show that they are equivalent, but failed as well.

    Please guide me. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    There are countably infinite sets with cardinality i for i a natural number (as is aleph null times i). There are countably infinite choices for i. So, the set has cardinality equal to countably infinite times countably infinite, which is countably infinite. Basically.

    The same logic gives us that every finitely generated group is countably infinite.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    Thanks, but could you give more formal proof?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1
    We know that there is an injection \Phi :\mathbb{Z}^ +   \mapsto \{ 2,3,5, \cdots \} to the set of prime numbers.
    Define a function f:P \mapsto \mathbb{Z}^ +  ,\,f\left( X \right) = \prod\limits_{y \in X} {\Phi (y)} .
    Noting that each X \in P is finite, prove that f is an injection.
    That means that P is countable.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    The question asked show that P is countably infinite, not just countable. I wonder if showing injection is enough. Shouldn't it be to show that there is a bijection?

    Thanks a lot.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by armeros View Post
    The question asked show that P is countably infinite, not just countable. I wonder if showing injection is enough. Shouldn't it be to show that there is a bijection?

    Thanks a lot.

    If you show there is a injection both ways then that is sufficient. For the injection \phi: \mathbb{N} \rightarrow S meerly take i \mapsto \{i\}. Simples!

    (If there exists an injection from A to B then |A| \leq |B|.)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    Thanks a lot.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Theory: Show A is finite or countably infinite
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 14th 2011, 05:26 AM
  2. Finite, countably infinite, or uncountable
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 25th 2011, 08:40 AM
  3. Intersection of two countably infinite sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 22nd 2011, 06:30 PM
  4. countably infinite / uncountable sets
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 9th 2010, 12:18 PM
  5. Countably infinite proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2008, 11:35 AM

Search Tags


/mathhelpforum @mathhelpforum