# 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
5 years, 3 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

In the second paragraph you write " if such a bijection exists then such a bijection has to be with N itself and not any proper subset of N ." I did not understand this part. Why can't the bijection be assumed to be with a proper subset of N.

- 2 years, 10 months ago