Waste less time on Facebook — follow Brilliant.
×

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
8 months, 3 weeks ago

No vote yet
1 vote

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...