The Uncountability of R

There are many ways to prove that RR, the set of real numbers, is uncountable, i.e., it has no bijection with a subset (may be proper or improper) of NN, 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 RR to be uncountable, then it follows that RR is uncountable. We choose the closed interval [0,1][0,1]. We start by assuming that this interval is countable, or in other words, it has a bijection with a subset of NN. Further see that [0,1][0,1] being an infinite set (this is quite trivial, for, if xx belongs to [0,1][0,1], then xn[0,1]nN\frac { x }{ n } \in [0,1]\forall n\in N and thus there are infinite elements in [0,1][0,1] ), if such a bijection exists then such a bijection has to be with NN itself and not any proper subset of NN.

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

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

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

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

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

Continue this process ad infinitum. (It may happen that at the ii-th step, xi{ 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 Ii{ 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 RR. See that since each interval belongs to [0,1][0,1], so, their non-empty intersection belongs to [0,1][0,1]. Also see that if li{ l }_{ i } is the length of the interval Ii{ I }_{ i }, then 0<li12iiN0<{ l }_{ i }\le \frac { 1 }{ { 2 }^{ i } } \forall i\in NThus by sandwich property of sequences,lim(li)=0\lim _{ }{ \left( { l }_{ i } \right) } =0. Thus i=1Ii\bigcap _{ i=1 }^{ \infty }{ { I }_{ i } } is a singleton set containing one point only, say xx. Now we shall argue that xxiiNx\neq { x }_{ i }\forall i\in NFor this let us assume that x=xix={ x }_{ i } for some iNi\in N. Then xii=1Ii{ x }_{ i }\in \bigcap _{ i=1 }^{ \infty }{ { I }_{ i } } which is a contradiction since the element xi{ x }_{ i } was eliminated at the ii-th step of our bisection.

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

Note by Kuldeep Guha Mazumder
3 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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.

Max Jerry - 1 year, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...