Results 1 to 3 of 3

Math Help - Proof (countable)

  1. #1
    Junior Member
    Joined
    Sep 2007
    Posts
    46

    Proof (countable)

    Prove that the set which contains all FINITE subsets of N (natural numbers) is a countable set.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by seerTneerGevoLI View Post
    Prove that the set which contains all FINITE subsets of N (natural numbers) is a countable set.
    There are many different proofs of this theorem.
    Each depends upon what you have to work with.
    If you know that there is a one-to-one correspondence between the prime integers and the positive integers. Suppose that \Theta :Z^ +   \mapsto P is that mapping. Now if  A=\left\{ {z_1 ,z_2 ,z_3 , \cdots ,z_j } \right\} is a finite subset of Z^+ then consider the function \varphi \left( {\left\{ {z_1 ,z_2 ,z_3 , \cdots ,z_j } \right\}} \right) = \prod\limits_{k = 1}^j {\Theta \left( {z_k } \right)} . Now if we use the unique factorization theorem then the function \varphi is one-to-one. Thus the set of all finite subset of Z^+ maps injectively into Z^ + . Thus it is countable.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2007
    Posts
    46
    Quote Originally Posted by Plato View Post
    There are many different proofs of this theorem.
    Each depends upon what you have to work with.
    If you know that there is a one-to-one correspondence between the prime integers and the positive integers. Suppose that \Theta :Z^ + \mapsto P is that mapping. Now if  A=\left\{ {z_1 ,z_2 ,z_3 , \cdots ,z_j } \right\} is a finite subset of Z^+ then consider the function \varphi \left( {\left\{ {z_1 ,z_2 ,z_3 , \cdots ,z_j } \right\}} \right) = \prod\limits_{k = 1}^j {\Theta \left( {z_k } \right)} . Now if we use the unique factorization theorem then the function \varphi is one-to-one. Thus the set of all finite subset of Z^+ maps injectively into Z^ + . Thus it is countable.
    We haven't learned the unique factorization method. Is it possible to prove this using least upper bounds and greatest lower bounds (sup/inf) ? It's in the section of the Axiom of Completeness and we use the Archimedean Property a lot.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Countable Union proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 12th 2011, 06:02 PM
  2. Second countable, countable, proof...
    Posted in the Differential Geometry Forum
    Replies: 13
    Last Post: February 18th 2011, 08:08 AM
  3. Replies: 1
    Last Post: February 9th 2010, 02:51 PM
  4. Proof about countable sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 3rd 2010, 07:42 PM
  5. proof of countable
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2008, 12:30 PM

Search Tags


/mathhelpforum @mathhelpforum