Difference between revisions of "Uncountable"
(categories) |
m |
||
| Line 3: | Line 3: | ||
== Proof that <math>\mathbb{R}</math> is uncountable == | == Proof that <math>\mathbb{R}</math> is uncountable == | ||
| − | We give an indirect proof here. This is one of the most famous indirect proofs and was given by | + | 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 binary expansion of each <math>\omega_i</math>. For dyadic rationals, take only the expansion terminating in an infinite chain of zeros, so that we have a unique binary expansion for each element of <math>A</math>. Say <math>\omega_i=(.b_{i1}b_{i2}b_{i3}...)_2</math> for all <math>i</math>. Now construct <math>\omega=(.b_1b_2b_3...)_2</math> such that <math>b_i=1-b_{ii}</math> for all <math>i</math>. So <math>\omega</math> is different from <math>\omega_i</math> for all <math>i</math>. So <math>\omega\not\in A</math>. But <math>\omega\in\mathbb{R},0<\omega<1</math>, a'' contradiction''. So <math>\mathbb{R}</math> is uncountable. | 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 binary expansion of each <math>\omega_i</math>. For dyadic rationals, take only the expansion terminating in an infinite chain of zeros, so that we have a unique binary expansion for each element of <math>A</math>. Say <math>\omega_i=(.b_{i1}b_{i2}b_{i3}...)_2</math> for all <math>i</math>. Now construct <math>\omega=(.b_1b_2b_3...)_2</math> such that <math>b_i=1-b_{ii}</math> for all <math>i</math>. So <math>\omega</math> is different from <math>\omega_i</math> for all <math>i</math>. So <math>\omega\not\in A</math>. But <math>\omega\in\mathbb{R},0<\omega<1</math>, a'' contradiction''. So <math>\mathbb{R}</math> is uncountable. | ||
Revision as of 09:38, 29 June 2008
A set 
is said to be uncountable if there is no injection 
. A well-known 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 
. Consider the binary expansion of each 
. For dyadic rationals, take only the expansion terminating in an infinite chain of zeros, so that we have a unique binary expansion for each element of . Say 
for all 
. Now construct 
such that 
for all . So 
is different from for all . So 
. But 
, a contradiction. So is uncountable.
See Also
This article is a stub. Help us out by expanding it.
