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}


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





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)

Be Sociable, Share!



Infinite Sets

[…] The next question from Yahoo Answers is related to a different kind of infinity – the kind that deals with sets. The works of Georg Cantor between 1874 and 1884 are the origin of set theory in which he established the importance of one-to-one correspondence between sets, defined infinite and well-ordered sets, and proved that the real numbers are “more infinite” than the natural numbers. The diagonalization argument he used demonstrates a powerful and general technique that has since been used in a wide range of proofs such as this one. […]

Leave your comment:
XHTML:You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> . * required