Prove that the set which contains all FINITE subsets of N (natural numbers) is a countable set.

Printable View

- Sep 13th 2007, 03:53 PMseerTneerGevoLIProof (countable)
Prove that the set which contains all FINITE subsets of N (natural numbers) is a countable set.

- Sep 13th 2007, 04:45 PMPlato
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 $\displaystyle \Theta :Z^ + \mapsto P$ is that mapping. Now if $\displaystyle A=\left\{ {z_1 ,z_2 ,z_3 , \cdots ,z_j } \right\}$ is a finite subset of $\displaystyle Z^+$ then consider the function $\displaystyle \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 $\displaystyle \varphi $ is one-to-one. Thus the set of all finite subset of $\displaystyle Z^+$ maps injectively into $\displaystyle Z^ + $. Thus it is countable. - Sep 13th 2007, 07:35 PMseerTneerGevoLI