Thread: Proof (countable)

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

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 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.

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 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.

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!