1
$\begingroup$

When reading the proof of Cantor's Theorem(the one that says no sequence can contain all reals), I feel unsure. The Cantor's Theorem are proved by contradicting the fact that there are some real number, call it x, in the nested intersection. However, the assumption that all reals are in the sequence leads us to the fact that no element can be in the nested intersection and thus a contradiction. I am wondering what if we let this number, x, put this x in the original sequence. Then what happens? I thought about we can apply the same method and just prove it again. So that some number y in real number is still not in the sequence. But we shouldn't have to prove this again. What part of my thoughts went wrong?

The proof I am talking about is to use the nested interval theorem to show it. Not the argument Cantor proposed. This proof show the connection with the completeness axiom.

Proof: The proof is by contradiction. Suppose that such a sequence A exists. Let $I_0$ be the interval $[0, 1]$. At least one of the thirds of I0 does not contain A(1). Let I1 be such a third. At least one of the thirds of I1 does not contain A(2). Let I2 be such a third. At least one of the thirds of I2 does not contain A(3). Let I3 be such a third. At least one of the thirds of I3 does not contain A(3). Let I4 be such a third. Etc. This way we have constructed a nested sequence I0 ⊃I1 ⊃I2 ⊃I3 ⊃I4... 4 of compact intervals. We see that the intersection of them is a singleton since the length of the interval is going to zero. tervals Theorem.

Since α∈I1 andA(1)∈/I1,it must be that α=A(1).

Since α∈I2 andA(2)∈/I2,it must be that α=A(2).

Since α∈I3 andA(3)∈/I3,it must be that α=A(3).

Since α∈I4 andA(4)∈/I4,it must be that α=A(4).

Etc.

This shows that this real number α is not a term in A. Yet we have as sumed that all real numbers appear as terms in A. A contradiction. The proof is complete!

$\endgroup$
  • $\begingroup$ The point is that your original sequence was supposed to contain all of them. There's no iteration needed; if it's possible to place all the reals in countable sequence then there is such a sequence. Given such a purported sequence, just run the 'diagonalization algorithm' to exhibit a number that wasn't in the original sequence and you've shown that the assumption - that such a sequence exists - is wrong. $\endgroup$ – Steven Stadnicki Oct 29 '14 at 19:52
  • $\begingroup$ Are you referring to his "diagonal argument" or a different proof? $\endgroup$ – Akiva Weinberger Oct 29 '14 at 19:57
  • $\begingroup$ I am talking about the proof where you use the nested interval theorem to obtain a contradiction. $\endgroup$ – Kun Oct 29 '14 at 20:02
  • $\begingroup$ @Kun: Then what do you mean by ‘the assumption that all reals are in the sequence’? $\endgroup$ – Brian M. Scott Oct 29 '14 at 20:15
  • $\begingroup$ @Brian M. Scott: I mean, "Suppose there is a real sequence A such that A contains all real numbers as terms. " $\endgroup$ – Kun Oct 29 '14 at 20:18
7
$\begingroup$

The proof isn’t really a proof by contradiction, even though it’s often presented in that language. It’s really a demonstration that there is an algorithm that takes as input any infinite sequence of real numbers in $[0,1]$ and constructs as output a specific real number that is not in that sequence. This shows that no sequence can list all of the real numbers in $[0,1]$. There is no need to assume that the sequence enumerates $[0,1]$.

In other words, the argument simply shows directly that every possible list is incomplete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry if I didn't point out earlier, I am talking about the argument where you need use the nested interval theorem to obtain a contradiction. Not the one proposed by Cantor $\endgroup$ – Kun Oct 29 '14 at 20:09
  • $\begingroup$ @Kun: That argument is due to Cantor, and everything that I said applies to it as well as to the diagonal construction. $\endgroup$ – Brian M. Scott Oct 29 '14 at 20:22
  • $\begingroup$ I think I am confused with the method of proof. I didn't really get what means by supposing an arbitrary sequence at first. So I think what happened is that if we've already proved it for any arbitrary sets, then the sequence A', where it contains all elements in A and $\alpha$, also contains a real that is not in this set, right? $\endgroup$ – Kun Oct 29 '14 at 20:26
  • $\begingroup$ @Kun: Both proofs show that if $\langle x_n:n\in\Bbb N\rangle$ is any sequence of real numbers whatsoever, there is a real number $y$ that is not in the set $\{x_n:n\in\Bbb N\}$. Thus, no sequence of real numbers can list all of $\Bbb R$: if you take any sequence at all, both proofs give you a recipe for finding a real number that isn’t in your sequence. $\endgroup$ – Brian M. Scott Oct 29 '14 at 20:30
  • $\begingroup$ Thank you! Now I understand . I was thinking that adding the number that it is missing will require another proof. But now I see that the fact "for all sequence A in R, you can always find a real number that is missing from A" already addressed this issue as no matter what you add in the sequence, it is still a sequence in R and thus there is no need to prove it again. Right? $\endgroup$ – Kun Oct 29 '14 at 20:33
1
$\begingroup$

Your thought is not wrong. Suppose we have an alleged "list of all real numbers" (indexed by natural numbers). Then we may apply diagonalization to obtain $x_0$, a real number not on the list. Suppose that we add $x_0$ back to the list (at position $0$, for example). Then we may apply diagonalization to the new list to obtain $x_1$. You will notice that, no matter how many (finite) times we repeat this process, we will always end up with an incomplete list of real numbers, for there is always a new real number not on the list that diagonalization can come up with.

Now this fact doesn't really mean that we need to apply the diagonal argument infinitely often. You may be under the impression that the new list we obtain after adding $x_0$ is somehow "larger" than the original list, and hence necessitates a new proof (in the manner of induction). But in fact the new list has exactly the same size as the original list! The "Hilbert's hotel" thought experiment demonstrates that, when you add one number to a countably infinite list, you still end up with a countably infinite list. So the original proof applies perfectly well to this situation as well, and you are not really proving anything other than that which you've already proven when you apply diagonalization to the new list and obtain another real number.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

You are not proving this by contradiction. Instead you show that whenever you are given a countable set of real numbers, there is a real number which is not in that set.

When you add such real number, you have a new countable set, and you can find a new one. And so on and so forth.

It's not that after repeating twice, three times, or even countably many times, you can suddenly claim that you have collected all the real numbers.

| cite | improve this answer | |
$\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.