1
$\begingroup$

This question already has an answer here:

In Stephen Abbott's "Understanding Analysis" book, he proves that the set of Real numbers is an uncountable set in theorem 1.4.11. My issue with the proof is that it seems too strong, as in it seems like you can prove that the set of Integers or Rationals are uncountable with the exact same proof, just replace Reals with Integers or Rationals. Where does he invoke properties of the Reals that the Integers and Rationals don't have? I know I have to be missing something...

Here's the theorem and proof, copied straight out of Abbott:

Theorem 1.4.11. The set R of Real Numbers is uncountable.

Proof. Assume that there does exist a 1–1, onto function f : N → R. Again, what this suggests is that it is possible to enumerate the elements of R. If we let x1 = f(1), x2 = f(2), and so on, then our assumption that f is onto means that we can write

(1) R ={$x_1$, $x_2$, $x_2$, $x_2$,...}

and be confident that every real number appears somewhere on the list. We will now use the Nested Interval Property (Theorem 1.4.1) to produce a real number that is not there.

Let $I_1$ be a closed interval that does not contain $x_1$. Next, let $I_2$ be a closed interval, contained in $I_1$, which does not contain $x_2$. The existence of such an $I_2$ is easy to verify. Certainly $I_1$ contains two smaller disjoint closed intervals, and $x_2$ can only be in one of these. In general, given an interval $I_n$, construct $I_{n+1}$ to satisfy

(i) $I_{n+1}$ ⊆ $I_n$ and

(ii) $x_{n+}$ $\mathrel{{\epsilon}\llap{/}}$ $I_{n+1}$.

We now consider the intersection $\cap_{n=1}^{\infty}I_n$. If $x_{n_0}$ is some real number from the list in (1), then we have $x_{n_0} \mathrel{{\epsilon}\llap{/}} I_{n_0}$, and it follows that $x_{n_0} \mathrel{{\epsilon}\llap{/}} \cap_{n=1}^{\infty}I_n$. Now, we are assuming that the list in (1) contains every real number, and this leads to the conclusion that $\cap_{n=1}^{\infty}I_n =∅$. However, the Nested Interval Property (NIP) asserts that $\cap_{n=1}^{\infty}I_n \mathrel{{=}\llap{/}}∅$. By NIP, there is at least one $x ~\epsilon \cap_{n=1}^{\infty}I_n$ that, consequently, cannot be on the list in (1). This contradiction means that such an enumeration of R is impossible, and we conclude that R is an uncountable set.

$\endgroup$

marked as duplicate by Noah Schweber, Lord Shark the Unknown, Leucippus, Daniel W. Farlow, José Carlos Santos Jul 28 '17 at 4:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ You should summarize the proof given. I don't have a copy of the book at hand. $\endgroup$ – Ross Millikan Jul 27 '17 at 17:56
  • 5
    $\begingroup$ Short version: the issue is that there is no reason to believe that the "antidiagonal" sequence corresponds to a rational (it won't be eventually periodic) or an integer (it will have infinitely many digits). Cantor's argument has two pieces: build an object not on the list, and then show that it should have been on the list. This second part is what fails if you try to use the argument on the rationals or on the integers. $\endgroup$ – Noah Schweber Jul 27 '17 at 17:59
  • $\begingroup$ You might want to look up Cantor's original proof for a distinct viewpoint on the proof, that may make the result clearer for the real numbers. $\endgroup$ – Chappers Jul 27 '17 at 18:03
  • $\begingroup$ " as in it seems like you can prove that the set of Integers or Rationals are uncountable with the exact same proof, just replace Reals with Integers or Rationals." It may seem like you can but you obviously can't. Rereading and find out why it wouldn't work. $\endgroup$ – fleablood Jul 27 '17 at 18:07
  • $\begingroup$ If he is using Cantors diagonal argument, then if you list the rationals or the integers and create a new thing by changing a decimal different from all the others, what you create is NOT an integer (it has infinite decimals) and is NOT rational. (It has infinite decimals that are not periodic--- proving they can not be periodic is... probably a bear, but ... it doesn't prove they are and if you can't show they are you can't assume they are.) $\endgroup$ – fleablood Jul 27 '17 at 18:11
3
$\begingroup$

Abbot uses the nested interval property that the countable intersection of nested intervals is non empty.

BUT the intersection need not have any integers or rational numbers. It merely needs at least one (and it could be just one) real number.

Rough outline:

Let $\{x_1,x_2...\}$ be a countable list of all real numbers. Construct $I_n$ being closed intervals so that $x_i \not \in I_i$ and $I_{i+1} \subset I_i$.

By the 1.4.1 The Nested Interval property $\cap_{i=1}^{\infty} I_i \in \emptyset$ So there exists a $w \in \cap_{i=1}^{\infty}I_n$. But $w \in \mathbb R$ so $w \in \{x_1, x_2 ....\}$. So $w = x_k$ for some $k$. And $w=x_k \in \cap_{i=1}^{\infty}I_n \subset I_k$. But $x_k \in I_k$ which is a contradiction.

End of rough outline.

So if $\{x_1, x_2....\}\ne \mathbb R$ (or more precisely if $\mathbb R \not \subset \{x_1,x_2....\}$), we can only conclude that $w \in \mathbb R$ and we can not conclude $w \in \{x_1, x_2....\}$.

And thus we have no contradiction.

=====

Addendum: This post is assuming that or space is still the reals and that it is only the list that is all the rationals or integers.

If we were to do "Rational Analysis" the proof fails because the rationals do not have the Nested Interval Property. If you have nested series of $[a_n, b_n] = \{q \in \mathbb Q|a_n \le q \le b_n\}$ and $I_{n+1} \subset I_n$ then it is not true that $\cap I_n \ne \emptyset$.

The rationals do not have the Axiom of Completeness and thus the set $\{x_i\}$ so that $a_i < x_i < a_{i+1}$ although increasing and bounded above need not have a least upper bound and $\cap I_n$ may be empty.

Example: Let $\{[a_i, b_i]\}$ so that $a_i^2 < 2- \frac 1n < a_{i+1}^2 < 2 < b_{i+1}^2 < 2 + \frac 1n < b_{i}^2$ and $a_, b_i$ are positive. Then $\cap [a_i,b_i] = \emptyset$.

The integers do have the Nested Interval Propety but If you have a sequence of $I_{i+1} \subset I_{i}$ and $I_i \ne \emptyset$ then the is an $N$ so that $I_i = I_N$ for all $i > N$. As such the sequence of nested intervals as described in the proof of 1.4.11 can not be created. Ultimately you will not be able to create $I_{i+1} \subset I_i$ with $x_{i+1} \not \in I_{i+1}$.

The "The existence of such an I2 is easy to verify" is not possible in the ingeters. In the reals (or the rationals)one can verify that in $(a_i, b_i)$ there are $a_{i+1}, b_{i+1}$ so that $a_i < a_{i+1}< b_{i+1}$ and if $x_{i+1} \in I_i$ we can avoid it by selecting proper $a_{i+1} , b_{i+1}$.

In the integers that is simply not the case. Give $a_{i} < b_i$ there only finitely many (possible none) $a_{i+1}, b_{i+1}$ so that $a_{i} < a_{i+1} < b_{i+1} < b_i$ so this can not be extended. Eventually there will have to be an $x_n \in I_n$.

$\endgroup$
  • $\begingroup$ The integers do have the least upper bound property (and when interpreted appropriately, the nested interval property). But bounded intervals in $\mathbb{Z}$ are finite, and hence the construction doesn't work there. $\endgroup$ – Daniel Fischer Jul 27 '17 at 18:59
  • $\begingroup$ Good point..... $\endgroup$ – fleablood Jul 27 '17 at 19:11
  • $\begingroup$ Actually the construction does work for integers but it aould be utterly irrelevent. The infinite intersection will be either an interval containing no integers or a single non integer point. $\endgroup$ – fleablood Jul 27 '17 at 19:41
  • $\begingroup$ No. Since a bounded interval in $\mathbb{Z}$ has only finitely many elements, the interval $I_1$ can be exhausted after finitely many steps (and will be if $f$ is a surjection), and the construction cannot be continued. In $\mathbb{R}$, we need a nondegenerate compact interval at each step to guarantee that we can continue the construction. I hope that Abbott's definitions are such that "a closed interval" is a nondegenerate compact interval, or the OP has incompletely quoted, otherwise his proof is faulty. $\endgroup$ – Daniel Fischer Jul 27 '17 at 19:50
  • $\begingroup$ You misunderstood the point of my comment. The construction works for making real intervals but eventually you will have a real interval with no integers. If you restrict to integer intervals then you can't create these inervals. If x1 = 1 and I_1 = [2,3] and x2=2 then we can not creat I_2 so that I_2 subset I_1. I_2 not empty. And 2 not in I_2. $\endgroup$ – fleablood Jul 27 '17 at 20:08

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