TransWikia.com

Uncountability of $mathbb{R}$

Mathematics Asked by modo_mahu on January 5, 2021

I was trying to follow this proof of the uncountabilty of R and at first it seemed clear, but when I tried to explain it to myself I realized I didn’t really understand one of the steps.

The proof is by contradiction, using the nested intervals theorem:

Assume $mathbb{R}$ is countable. Then we can define a bijection from $mathbb{N}$ to $mathbb{R}$, in other words we can assign each number in $mathbb{R}$ a subscript in $mathbb{N}$ and get the infinite sequence $R = {x_1, x_2, x_3, … } $.

Let $I_1 subset mathbb{R}$ be a closed interval such that $x_1 notin I_1$. $I_1$ can also be written as $[a_1, b_1]$, with $x_1 < a_1 < b_1$.

So far so good. Now comes the step where I ran into difficulties.

Let $I_2 subset I_1$ be a closed interval such that $x_2 in I_1$ and $x_2 notin I_2$. $I_2$ has bounds $a_2, b_2$. This means we now have the following inequality $x_1 < a_1 leq x_2 < a_2 < b_2 < b_1$.

But it seems to me that for this to make sense $a_1$ must be equal to $x_2$, since we have assumed that $mathbb{R}$ is countable and we know that $mathbb{R}$ is increasing. Otherwise we’ve just produced a new number in $mathbb{R}$ between $x_1$ and $x_2$ that the count sort of skipped.

Now obviously the point of the proof is to show precisely that $mathbb{R}$ is uncountable and that assigning natural subscripts to the real numbers won’t get you anywhere, but it feels like at that moment in the proof we’d be asssuming the conclusion.

The proof then goes on to define $I_{n+1}$ as a closed interval $subset I_n$ such that $x_{n+1} notin I_{n+1}$.

Once we have these intervals constructed such that $I_1 supset I_2 supset I_3 supset$ … we can apply the nested intervals theorem, which tells us that the intersection of these nested sets is non-empty, and get:
$$exists x in mathbb{R};such;that; x in ( cap I_n forall n in mathbb{N} ) $$

Since we have assumed $mathbb{R}$ is countable, we know that $x = x_m, m in mathbb{N}$. So if the intersection of the nested sets is non-empty it must contain a number of the form $x_m$.

But we have constructed our sets such that for any number $x_m$ there is a nested set $I_m$ that doesn’t contain it. So the intersection of the nested sets cannot contain any number of the form $x_m$. Which is the contradiction we were after.

It seems to me like the rest of the proof holds even if we require that $a_1 = x_2$ (and by extension $a_n = x_{n+1}$). What am I missing? Does the proof still hold even if $a_1$ is allowed to be $leq x_2$? If so, why?

One Answer

I think the point you are missing is that the values $x_1,x_2,dots$ are not necessarily ordered. Indeed, the rationals $mathbb Q$ are countable, so there is an infinite sequence $q_1,q_2,dots$ covering all rationals, but there must be infinitely many rationals between $q_1$ and $q_2$ (which appear later in the sequence).

The proof still works just using $a_1leq x_2$; given a closed interval $[a,b]$ and a real number $x$ we can always find a smaller closed interval $[a',b']subseteq [a,b]$ which doesn't contain $x$. Thus we can find a nested sequence of closed intervals, each of which misses the first $n$ numbers in the list, then take the intersection of all these intervals, which is a nonempty closed interval missing all of them, contradicting the assumption that our list covered all the reals.

So what goes wrong if we use rationals rather than reals? We can find $a_n,b_ninmathbb Q$ such that $[a_n,b_n]$ misses out $q_1,dots,q_n$, and these intervals are nested as before. The problem comes when we take the intersection of all the intervals. Say the intersection is $[a,b]$ where $a=lim a_n, b=lim b_n$. Now since the limit of a sequence of rationals need not be rational, $a,b$ could be irrational. Also, they could be equal. So it could be that the final interval we get is, say, $[sqrt 2,sqrt 2]$. This interval is non-empty, but it doesn't contain any rationals, so doesn't give a contradiction.

Correct answer by Especially Lime on January 5, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP