Proposition 2.2.1: An Uncountable Set
Proof:
Any number x in the interval (0, 1) can be expressed as a unique, never-ending decimal. Actually, this is not quite true: 0.1499999... is the same number as 0.15000.... But when we simply discard those numbers with a non-ending tail of 9's we still get the open interval (0, 1), and now every number has a unique decimal representation. If these numbers were countable, we could list them in a two-way infinite table:- 1. number: x_{1}^{1}, x_{2}^{1}, x_{3}^{1}, x_{4}^{1}, ...
- 2. number: x_{1}^{2}, x_{2}^{2}, x_{3}^{2}, x_{4}^{2}, ...
- 3. number: x_{1}^{3}, x_{2}^{3}, x_{3}^{3}, x_{4}^{3}, ...
- 4. number: x_{1}^{4}, x_{2}^{4}, x_{3}^{4}, x_{4}^{4}, ...
- ...
In this list, what would be the number associated to the following element:
- Let x be the number represented by
(x_{1}, x_{2}, x_{3}, x_{4}, ...),
where we let:
- x_{1} = 0 if x_{1}^{1} = 1 and x_{1} = 1 if x_{1}^{1} = 0
- x_{2} = 0 if x_{2}^{2} = 1 and x_{2} = 1 if x_{2}^{2} = 0
- x_{3} = 0 if x_{3}^{3} = 1 and x_{3} = 1 if x_{3}^{3} = 0
- ...