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