Uncountable Sets

This page is http://www.math.uic.edu/~lewis/las100/uncount.html

Main Questions:

  1. What is a countable set?
  2. What is an uncountable set?
  3. Are the real numbers a countable set?

Countable Sets

Recall from Equivalent Sets the definitions
The set A is countable if
A is equivalent to N ( A ~ N).
The set A is uncountable if
A is infinite and not countable.
Of course any infinite subsets of the natural numbers (such as the set of prime numbers) is a countable set. The set of all rational numbers is a countable set. This is somewhat harder to prove, but think about a way of "counting" all the ordered pairs, (m,n), where m and n are natural numbers.

All infinite sets are not necessarily equivalent. One of the best known examples of an uncountable set is the set of all real numbers. The demonstration that the real numberes are uncountable is another example of proof by contradiction. The following is a slight modification of a presentation by George Gamow in One, Two, Three, Infinity.

The statement to be proved is The set of real numbers x, 0 < x < 1, is uncountable.

Proof by contradiction: Suppose that the set is uncountable. Then we can claim to make an arrangement of all them, and that it looks something like this:

  1. 0.38602563708....
  2. 0.57350762050....
  3. 0.99356753207....
  4. 0.25763200456....
  5. 0.00005320562....
  6. 0.99035638567....
  7. 0.55522730567....
  8. ..........................
  9. ..........................
Now we claim to have listed every decimal between 0 and 1. But you can always give me a decimal which is not in my table! Do it like this:
  1. Take the first digit = 7 (not 3); Decimal = 0.7.....
  2. Take the second digit = 3 (not 7); Decimal = 0.73.....
  3. Take the third digit = 7 (not 3); Decimal = 0.737.....
  4. Take the fourth digit = 7 (not 6); Decimal = 0.7377.....
  5. Take the fifth digit = 3 (not 5); Decimal = 0.73773.....
  6. Take the sixth = 3 (not 6); Decimal = 0.737733.....
  7. ................ 0.737733?.....
  8. ................ 0.737733xx.....
  9. ................
The rule is to make sure that the kth digit of the new decimal is not equal to the kth digit of the kth number in my original list. As Gamow says,
In fact if the author of the table will tell you that this very fraction you have written here stands under No. 137 (or any other number) in [the] table, you can answer immediately: "No it isn't the same fraction because the one hundred and thirty seventh decimal in your fraction is different than the one hundred and thirty seventh decimal in the fraction I have in mind."

Thus our only choice is to conclude that the statement I have listed all the decimals is FALSE -- i.e., the statement I cannot list all the decimals is TRUE.

The conclusion is (Gamow):

Thus it is impossible to establish a one-to-one correspondence between the points on the line and the integer numbers, which means that the infinity of points on a line is larger, or stronger, than the infinity of points of all integer or fractional numbers.
Back to Prof. Lewis's LAS 100 home page