# Math Help - Proof (countable)

1. ## Proof (countable)

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

2. Originally Posted by seerTneerGevoLI
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.

3. Originally Posted by Plato
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!