Difference between revisions of "Uncountable"
(→Proof that \mathbb{R} is uncountable) |
|||
| Line 5: | Line 5: | ||
We give an [[indirect proof]] here. This is one of the most famous indirect proofs and was first given by [[Georg Cantor]]. | We give an [[indirect proof]] here. This is one of the most famous indirect proofs and was first given by [[Georg Cantor]]. | ||
| − | Suppose that the set <math>A=\{x\in\mathbb{R}:0<x< 1\}</math> is countable. Let <math>\{\omega_1, \omega_2, \omega_3, ...\}</math> be any enumeration of the elements of <math>A</math>. Consider the [[decimal expansion]] of each <math>\omega_i</math>, say <math>\omega_i=0.b_{i1}b_{i2}b_{i3} \ldots</math> for all <math>i</math>. Now construct a real number <math>\omega= 0.b_1b_2b_3 \ldots</math> by choosing the digit <math>b_i</math> so that it differs from <math>b_{ii}</math> by at least 3 and so that | + | Suppose that the set <math>A=\{x\in\mathbb{R}:0<x< 1\}</math> is countable. Let <math>\{\omega_1, \omega_2, \omega_3, ...\}</math> be any enumeration of the elements of <math>A</math> (in other words, take an injection <math>f: A \to \mathbb{N}</math>, and denote <math>\omega_i = f(i)</math>). |
| + | |||
| + | Consider the [[decimal expansion]] of each <math>\omega_i</math>, say <math>\omega_i=0.b_{i1}b_{i2}b_{i3} \ldots</math> for all <math>i</math>. Now construct a real number <math>\omega= 0.b_1b_2b_3 \ldots</math>, by choosing the digit <math>b_i</math> so that it differs from <math>b_{ii}</math> by at least 3 and so that <math>b_i</math> is never equal to 9 or 0. It follows that <math>\omega</math> differs from <math>\omega_i</math> by at least <math>\frac{2}{10^i}</math>, so <math>\omega \neq \omega_i</math> for every <math>i</math>. Thus, <math>\omega \not \in A</math>. However, <math>\omega</math> is clearly a real number between 0 and 1, a [[contradiction]]. Thus our assumption that <math>A</math> is countable must be false, and since <math>\mathbb{R} \supset A</math> we have that <math>\mathbb{R}</math> is uncountable. | ||
==See Also== | ==See Also== | ||
Revision as of 09:03, 13 August 2011
A set 
is said to be uncountable if there is no injection 
. Every set that is not uncountable is either finite or countably infinite. The most common example of an uncountable set is the set of real numbers 
.
Proof that 
is uncountable
We give an indirect proof here. This is one of the most famous indirect proofs and was first given by Georg Cantor.
Suppose that the set 
is countable. Let 
be any enumeration of the elements of 
(in other words, take an injection 
, and denote 
).
Consider the decimal expansion of each 
, say 
for all 
. Now construct a real number 
, by choosing the digit 
so that it differs from 
by at least 3 and so that is never equal to 9 or 0. It follows that 
differs from by at least 
, so 
for every . Thus, 
. However, is clearly a real number between 0 and 1, a contradiction. Thus our assumption that is countable must be false, and since 
we have that is uncountable.
See Also
This article is a stub. Help us out by expanding it.
