# Proof (countable)

Printable View

• Sep 13th 2007, 03:53 PM
seerTneerGevoLI
Proof (countable)
Prove that the set which contains all FINITE subsets of N (natural numbers) is a countable set.
• Sep 13th 2007, 04:45 PM
Plato
Quote:

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.
• Sep 13th 2007, 07:35 PM
seerTneerGevoLI
Quote:

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!