There are many ways to prove that , the set of real numbers, is uncountable, i.e., it has no bijection with a subset (may be proper or improper) of , 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 to be uncountable, then it follows that is uncountable. We choose the closed interval . We start by assuming that this interval is countable, or in other words, it has a bijection with a subset of . Further see that being an infinite set (this is quite trivial, for, if belongs to , then and thus there are infinite elements in ), if such a bijection exists then such a bijection has to be with itself and not any proper subset of .
Thus can be used as an index set of , or in other words the elements of can be indexed as Thus we can write Now we shall construct a sequence of nested closed intervals, such that the -th interval excludes all the above elements till the -th element. How? Simply using the bisection method:
i) Bisect into the two closed intervals and .
ii) If belongs to , choose .
iii) If belongs to , then choose
iv) If then bisect into similar closed intervals and choose to be the left interval.
Continue this process ad infinitum. (It may happen that at the -th step, 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 , 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 . See that since each interval belongs to , so, their non-empty intersection belongs to . Also see that if is the length of the interval , then Thus by sandwich property of sequences,. Thus is a singleton set containing one point only, say . Now we shall argue that For this let us assume that for some . Then which is a contradiction since the element was eliminated at the -th step of our bisection.
Hence we see that such that but . Thus which is a contradiction. Thus our assumption is wrong and is uncountable.
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
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.