Sunday, October 14, 2012

The are uncountably many subsets of natural numbers

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

In the post Not enough names for numbers, we prove that there are more real numbers between 0 and 1 than natural numbers, technically we say that the set of real numbers is uncountable. We now apply the same argument to prove that there are uncountably many real numbers made up entirely by 1 and 2 in the unit interval.

Consider a list of real numbers made up entirely by 1 and 2 in the unit interval:

0.α11α12α13α14α15
0.α21α22α23α24α25
0.α31α32α33α34α35
0.α41α42α43α44α45
……………

construct a real number B=0.β1β2β3β4β5… such that βj=1 if αjj=2; 2 if αjj=1.

Again this number B is not in the list. Hence there is never a complete list of such real numbers.


Lets consider a somewhat different problem. The set of natural numbers is {1,2,3,…}. Each subset S of natural numbers is corresponding to a unique real number αS=0.α1α2α3α4α5… in a way that αj=1 if j∈S; 2 if j∉S, for example
α{1,2}=0.1122…
α{1,3,4}=0.121122…
α{2,4,6,8,…}=0.2121212…

Suppose there is a given list of subsets of natural numbers, then we convert it to a list of numbers in the unit interval made up entirely by 1 and 2, then we have a B which is not in the list, and finally we convert B to a subset SB={j βj=1} which is of course not in the given list of subsets of natural numbers.

Can we construct SB directly from the given list? Yes, we can!

SB={j : j∉ the j-th subset in the list}


In the first part of the previous section, we have a correspondence that each subset of natural numbers S maps to a real number αS in (0,1). Different subsets map to different real numbers in (0,1), and hence there is at least as many real numbers in (0,1) as the subsets of natural numbers.

Lets consider another correspondence. For each real number in (0,1), expressed in binary number system, for example 5/8=0.101000…. If α=0.α1α2α3α4α5…, then let Sα={j : αj=1}, for example S0.101000…={1,3}. Different real numbers in (0,1) maps to different subsets of natural numbers, and hence there is at least as many subsets of natural numbers as real numbers in (0,1).

Combining, we see that there are as many subsets of natural numbers as real numbers.