Math CentralQuandaries & Queries


Subject: countable and uncountable sets
Name: piyush
Who are you: Student

we se that union of countably infinite no of sets having countably infinite number of elements is a countable set
we can express p(n) (i.e power set of natural number) as a union of countable infinite number of sets i.e p(n)=s1Us2Us3.....
where s1=null
using the same statement can we prove that power set of natural number is a infinite countable set

Hi, we have two responses for you

The set you describe as p(n) = s1 U s2 U s3 U ... is indeed countable by the argument you have given. This set however is not the power set of the natural numbers. The power set of the natural numbers is the set of all subsets of the natural numbers. In your construction every element of sk is finite, every element of sn has k-1 elements, and hence every member of p(n) is finite. The power set of the natural numbers contains all subsets of the natural numbers, including the infinite subsets such as

{1, 2, 3, ...} and
{2, 4, 6, 8, ...} and
{2, 3, 5, 7, ...} all the prime numbers.


What you can prove in this way is that the set of FINITE subsets of natural numbers is countable. But to get the whole power set, you also need to count the infinite subsets, like {2, 4, 6, 8, ...} {1, 4, 9, 16, ...} and even strange ones like {1, 1093, 1094, 2222, ...}. Actually, there is an uncountable number of these.

P. S. I think that with your S3 you meant
S3 = {{1, 2}, {1,3}, {1,4}, ..., {2, 3}, {2, 4}, ..., {3, 4},... ... }


About Math Central


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS