SEARCH HOME
 Math Central Quandaries & 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 s2={1,2,3,4,5..........} s3={{1,1},{1,2},{1,3},..............{2,1},{2,2}........} 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.

Penny

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

Claude

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.