Even “More” Infinite Sets

May 20, 2009 17:41 by scibuff

In my previous post (you should read it first before continuing here), I wrote about a little bit about infinite sets and how we can get a sense of size for some of them. This time, I will give a solution to a problem which will, together with the previous result, demonstrate that sets with infinitely many elements have a “measure” of size, and that not all infinite sets are “equally” infinite.

Problem: Show set of real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, i.e. S=\left \{0.1, 0.9, 0.11, 0.99\cdots \right \} is uncountable.

Solution: To solve this problem we will use a proof by contradiction just as we did before.

Suppose, that similarly as in the last problem, we can put our S into a one-to-one correspondence with the set of natural numbers \mathbb{N}=\left \{0, 1, 2, 3,\cdots \right \}. In other words, we can create a list of ALL elements in our set (just as we did before) like so:

0\rightarrow s_{0}

1\rightarrow s_{1}

2\rightarrow s_{2}

\vdots

Now, consider any such arbitrary listing of the elements of S, for example, this one:

s_{0}=0.111111\cdots

s_{1}=0.999999\cdots

s_{2}=0.191919\cdots

s_{3}=0.919191\cdots

For the following argument the order of the elements on the list is irrelevant. The important thing is we have listed them ALL. Now, suppose with create a number s in the following way:

  • Make the first (decimal) digit of s be different from the first (decimal) digit of s_{0}, i.e. 9
  • Then make the second (decimal) digit of s be different from the second (decimal) digit of s_{1}, 1
  • The third (decimal) digit of s to be different from the third (decimal) digit of s_{2}, i.e. 9
  • The fourth(decimal) digit of s to be different from the fourth (decimal) digit of s_{3}, i.e. 1
  • etc …

 

It is relatively easy to show that a number created in such a way as s CANNOT be on our list. If s were on the list then s = s_{n} for some n\in \mathbb{N}. So, in particular, the n-th (decimal) digit of s must be equal to the n-th (decimal) digit of s_{n}. But that is not possible by the very definition of s.

On the other hand, set S is the set of all real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, in particular, s\in S.

The assumption that S is countable led us to conclude that s\notin S and at the same time s\in S, which is impossible. Therefore S must be uncountable.

On a side note: S can actually be put into one-to-one correspondence with the entire set of real numbers (which also true of any open interval of non-zero length)