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.α₁₁α₁₂α₁₃α₁₄α₁₅…
0.α₂₁α₂₂α₂₃α₂₄α₂₅…
0.α₃₁α₃₂α₃₃α₃₄α₃₅…
0.α₄₁α₄₂α₄₃α₄₄α₄₅…
……………

construct a real number B=0.β₁β₂β₃β₄β₅… 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.α₁α₂α₃α₄α₅… 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 S_B={j β_j=1} which is of course not in the given list of subsets of natural numbers.

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

S_B={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.α₁α₂α₃α₄α₅…, then let S_α={j : α_j=1}, for example S_0.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.