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 is that mapping. Now if is a finite subset of then consider the function . Now if we use the*unique factorization*theorem then the function is one-to-one. Thus the set of all finite subset of maps injectively into . Thus it is countable. - Sep 13th 2007, 07:35 PMseerTneerGevoLI