×

# The Uncountability of R

There are many ways to prove that $$R$$, the set of real numbers, is uncountable, i.e., it has no bijection with a subset (may be proper or improper) of $$N$$, the set of naturals. Here I will provide a simple proof. The proof is basically done by assuming [0,1] to be countable (its elements can be listed) and then devising a method to exclude all the elements of [0,1] one by one and show that still at least one real remains which is not in the list

First we shall state the result that a superset of an uncountable set is uncountable. So, if we can prove a subset of $$R$$ to be uncountable, then it follows that $$R$$ is uncountable. We choose the closed interval $$[0,1]$$. We start by assuming that this interval is countable, or in other words, it has a bijection with a subset of $$N$$. Further see that $$[0,1]$$ being an infinite set (this is quite trivial, for, if $$x$$ belongs to $$[0,1]$$, then $$\frac { x }{ n } \in [0,1]\forall n\in N$$ and thus there are infinite elements in $$[0,1]$$ ), if such a bijection exists then such a bijection has to be with $$N$$ itself and not any proper subset of $$N$$.

Thus $$N$$ can be used as an index set of $$[0,1]$$, or in other words the elements of $$[0,1]$$ can be indexed as $${ x }_{ 1 },{ x }_{ 2 },{ x }_{ 3 },...$$ Thus we can write $[0,1]=\left\{ { { x }_{ n } }|{ n\in N } \right\}$ Now we shall construct a sequence of nested closed intervals, such that the $$i$$-th interval excludes all the above elements till the $$i$$-th element. How? Simply using the bisection method:

i) Bisect $$[0,1]$$ into the two closed intervals $$[0,\frac { 1 }{ 2 } ]$$ and $$[\frac { 1 }{ 2 } ,1]$$.

ii) If $${ x }_{ 1 }$$ belongs to $$[\frac { 1 }{ 2 } ,1]$$, choose $${ I }_{ 1 }=[0,\frac { 1 }{ 2 } ]$$.

iii) If $${ x }_{ 1 }$$ belongs to $$[0,\frac { 1 }{ 2 } ]$$, then choose $${ I }_{ 1 }=[\frac { 1 }{ 2 } ,1]$$

iv) If $${ x }_{ 1 }=\frac { 1 }{ 2 }$$ then bisect $$[0,\frac { 1 }{ 2 } ]$$ into similar closed intervals and choose $${ I }_{ 1 }$$ to be the left interval.

Continue this process ad infinitum. (It may happen that at the $$i$$-th step, $${ x }_{ i }$$ does not belong to any of the two closed sub-intervals of the bisected interval. Then we can choose any one of the two sub-intervals as $${ I }_{ i }$$, though, for making a definiteness in our choice I prefer the left one always.)

By this process we get a sequence of closed nested intervals which have a non-empty intersection by the Nested Interval Property of $$R$$. See that since each interval belongs to $$[0,1]$$, so, their non-empty intersection belongs to $$[0,1]$$. Also see that if $${ l }_{ i }$$ is the length of the interval $${ I }_{ i }$$, then $0<{ l }_{ i }\le \frac { 1 }{ { 2 }^{ i } } \forall i\in N$Thus by sandwich property of sequences,$\lim _{ }{ \left( { l }_{ i } \right) } =0$. Thus $$\bigcap _{ i=1 }^{ \infty }{ { I }_{ i } }$$ is a singleton set containing one point only, say $$x$$. Now we shall argue that $x\neq { x }_{ i }\forall i\in N$For this let us assume that $$x={ x }_{ i }$$ for some $$i\in N$$. Then ${ x }_{ i }\in \bigcap _{ i=1 }^{ \infty }{ { I }_{ i } }$which is a contradiction since the element $${ x }_{ i }$$ was eliminated at the $$i$$-th step of our bisection.

Hence we see that $$\exists x$$ such that $$x\in [0,1]$$ but $$x\notin \left\{ { { x }_{ n } }|{ n\in N } \right\}$$. Thus $[0,1]\neq \left\{ { { x }_{ n } }|{ n\in N } \right\}$ which is a contradiction. Thus our assumption is wrong and $$R$$ is uncountable. $$[Q.E.D.]$$

Note by Kuldeep Guha Mazumder
1 year ago