5
$\begingroup$

There is this proof in Abbott's book (Understanding Analysis) on page 25, that I am failing to understand.

Theorem is that $\mathbb{R}$ is uncountable. And here is how the author proceeds to prove it (I know there is an easier proof by Cantor):

To show that a set is uncountable, we need to show that there is no 1-1,onto function of the form: $f:\mathbb{N} \rightarrow \mathbb{R}$. The author uses proof by contradiction, therefore assume there is a 1-1, onto function. This implies that no two "input" values from $\mathbb{N}$ will map us to the same value in $\mathbb{R}$ (1-1) and also that every element maps onto a unique value in $\mathbb{R}$, i.e. $x_1=f(1)$,$x_2=f(2)$ and so on, so we can write:

$$\mathbb{R} = \{x_1,x_2,x_3, ... \}$$

Would be the set of all the reals. Now the author proceeds to use the Nested Interval Property (Theorem 1.4.1 in the book) to produce a real that is not in the list.

Let $I_1$ be a closed interval that does not contain $x_1$ and $I_2$ be a closed interval that is contained in $I_1$ and which does not contain $x_2$. (1) My first understanding hurdle: "Certainly $I_1$ contains two smaller disjoint closed intervals", I cannot see which two disjoint intervals he has in mind. So I am starting to struggle at this point.

He then proceeds to say that $x_{n_0}$ is some real number from the list, then $x_{n_0} \notin I_{n_0}$ (fair enough, this is due to the way we constructed the intervals) and he then proceeds saying that:

$$x_{n_0} \notin \bigcap_{n=1}^{\infty}I_n$$

I do not see where the $I_{n_0}$ is in the above... The above has an intersection of the following intervals: $I_1,I_2,I_3,..$ and there is no $I_{n_0}$.

(2) Finally, by construction there is a real that is not in the interval, $x_n \notin I_n$ is not in there at all. So by definition, we are omitting a real number from the interval, even though we are meant to prove it (I realize that this is an interval in the first place; My thinking was that if we prove it on the interval then we can extend the conclusions from that interval to the whole of the real line; But if we are omitting a real from the number line, then how can we make any conclusions at all).

$\endgroup$
  • $\begingroup$ At the end of the third paragraph you have a typo, "every element maps onto a unique element of $\Bbb R$" $\endgroup$ – Ross Millikan Sep 18 '16 at 15:22
  • 1
    $\begingroup$ $I_{n_0}$ is just some interval in the list. And due the intersection then, cause $x_{n_0}\notin I_{n_0}\implies x_{n_0}\notin \bigcap I_n$. In other words $I_{n_0}\in\{I_n:n\in\Bbb N\}$, i.e. $n_0\in \Bbb N$ $\endgroup$ – Masacroso Sep 18 '16 at 15:24
  • $\begingroup$ The point is that the Nested Interval Property says that the intersection of closed intervals is not empty. Then $\bigcap I_n\neq \emptyset$, so exist some real that belongs to this intersection, then the function $f:\Bbb N\to\Bbb R$ with map $I_n\mapsto x_n$ is not surjective, so it cannot be bijective. $\endgroup$ – Masacroso Sep 18 '16 at 15:42
6
$\begingroup$

I'll try.

For your first hurdle, suppose that $x_1=2$ and choose $I_1$ to be $[0,1]$. Look at any pair of disjoint closed subintervals - say $[0,1/3]$ and $[2/3,1]$. Since they are disjoint, $x_2$ can't be in both of them (it may well be in neither) so let $I_2$ be one it's not in.

For the second hurdle, forget $I_{n_0}$. What the proof is saying is that the intersection of all the intervals you chose can't contain any of the numbers in the list: since $x_n$ isn't in $I_n$ it isn't in the intersection. You seem to understand that.

But that intersection does contain something, so there's a number not on the list.

$\endgroup$
3
$\begingroup$

To your first question, $I_1$ contains many possible choices for $I_2$. Hell, it might be that $x_2$ is not even in $I_1$ to begin with. But we do t not have to describe explicitly which interval is chosen, just that we can make such a choice.

However, if an explicit choice is wanted, you can enumerate the closed intervals with rational endpoints, there are only countably many of them, and take the least suitable interval in the enumeration.

As for your second question, $n_0$ is a natural number. If we intersect all the intervals, which are indexed by all the natural numbers, we also included $I_{n_0}$.

$\endgroup$
3
$\begingroup$

It is not important that every member of $\Bbb N$ be mapped to a unique real. Somebody has given us a function that is claimed to be onto the reals, that is that every real is the image of at least one natural. We are proving them wrong by finding a real they didn't cover. If they cover some reals more than once, that is not a problem.

For your first question, as an example, maybe $x_i=\pi$. We now want to find a closed interval not including $\pi$ to call $I_1$. It could be $[4,300]$, for example. Now we are asked to find two closed intervals included within it. We could take $[4,100]$ and $[101,300]$. The particular intervals do not matter as long as they are disjoint. Then at least one of them (maybe both) does not include $x_2$, so that one will become our $I_2$. If $x_2=1$, it is in neither one and we can take either one as $I_2$. If $x_2=10$ we are forced to take the second. The point is just that we can find one. Then we continue step by step.

The claim about $x_{n_0}$really says that no real on the list is in $\bigcap_{n=1}^{\infty}I_n$. $x_1$ isn't because it is not in $I_1$. $x_{100}$ isn't because it isn't in $x_{100}$ and so on.

In finally, we are not omitting a real from an interval, we are finding intervals that each do not cover a given real. Then we say the intersection contains a real, but we know it is not on the list.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.