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
1 year, 10 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...