cantor diagonalization method for proving infinity of real numbers

Question

Cantor Diagonalization method for proving that real numbers are strictly uncountable suggests to disprove that there is a one to one correspondence between a natural number and a real number.

However, The natural number and the real numbers both are infinite, So, I find there is ambiguity in finding the real number M that goes upto infinity which is different from all it's predecessors, r₁, r₂ r₃......, however infinity is not even definite, and we conclude that there is a miss. How's this possible.

Although, I don't know if it'd work, but, why would we not show that there is a one to one correspondence for all natural number for (0,1) that belongs to Real Numbers, and that the set of natural numbers would be exhausted for only (0,1), hence making the Real numbers uncountable. Either, way, what is the idea of cantor's method of concluding the miss?

EDIT: This is the best explanation I can give for the confusion in my head:

So, in cantor's proof, we build a series of r1, r2, r3, r4....... For, this series we choose a unique number M such that M = 0.d₁d₂d₃......., and we conclude that continuing this way we cannot find a number that has a match to the set of natural numbers i.e. the one-to-one correspondence cannot be found. But, The set of Natural numbers itself is infinite, and how can we extend M to infinity to deduce that there exists no one to one correspondence to the set of real Numbers from (0, 1).

So, what occurred to me(for the third paragraph), is that I thought(without any proof but the idea is intuitive), that the cardinality of real numbers from (0,1) is equal to the cardinality of the set of natural numbers. So, came with the idea that while finding the one-to-one correspondence to the set of real numbers, we exhaust the set of natural numbers that we have for the interval (0,1) itself, and other infinite number of intervals still remain in the set of Real numbers. Therefore, then proving that the set of Real Numbers is actually uncountable, because the definition of countability comes from the fact of a set's cardinality being equal to that to the set of natural numbers. Since, the cardinality of the real numbers would then be greater, it is not a countable set.

What I don't understand(very much for the first and second paragraphs) is that:
1) We make a list of real numbers. (OK)
2) We match the natural numbers with the list we have. (OK)
3) We form a Number M with a rule.(Such that say, d1 = 4 if d11 != 4 else 5) (OK)
4) And we continue this way(OK)
5) And we suddenly say, ok, since this is infinite, we conclude that there is no match from the set of natural number(Not OK)

As we move toward infinity for the set of real numbers, we also move towards infinity for the set of natural numbers, so we cannot possibly conclude that there's not match.

Either I don't understand cantor's theorem, or the theorem is taking some kind of a limiting value that is not stated in general proofs.

I hope you guys read all this.

Answer 1

You write

What I don't understand(very much for the first and second paragraphs) is that:

1. We make a list of real numbers. (OK)
2. We match the natural numbers with the list we have. (OK)
3. We form a Number M with a rule.(Such that say, d1 = 4 if d11 != 4 else 5) (OK)
4. And we continue this way(OK)
5. And we suddenly say, ok, since this is infinite, we conclude that there is no match from the set of natural number(Not OK)

Allow me to say what we actually do.

1. If $\mathbb{N}$ and $(0,1)$ have the same cardinality, they may be placed in bijection.
2. This means there exist a function $label$ from $\mathbb{N}$ to $(0,1)$ that is bijective, so each element of $(0,1)$ receives only one natural number via $label$ by injectivity and every element of $(0,1)$ receives at least one natural number via $label$ by surjectivity. That is, we have labelled every element of $(0,1)$ with a natural number. We may choose to imagine that we make the list $label(1), label(2), \dots$, but that is not essential. We have the bijection we need.
3. We construct $M$ such that it differs from $label(k)$ in the $k^{\text{th}}$ decimal digit. That is, in the $k^{\text{th}}$ position to the right of the decimal point. We use induction to complete this construction.
4. So in detail, we get a sequence of $M$s: $(M_1, M_2, \dots )$ where $M_1$ disagrees with $label(1)$ in the first decimal digit. Then $M_2$ is an extension of $M_1$ by one digit, so disagrees with $label(1)$ in the same way and disagrees with $label(2)$ in the second decimal digit. Then $M_3$ is an extension of $M_2$ by one digit, so disagrees with $label(1)$ and $label(2)$ and also disagrees with $label(3)$ in the third decimal digit. Since there is no obstruction to creating $M_{k+1}$ from $M_k$ -- because $label(k+1)$ certainly has a $k+1^\text{th}$ decimal digit and we can certainly choose the last digit of $M_{k+1}$ to be some other digit and this choice doesn't conflict with the prior or subsequent choices for the other elements of the sequence of $M$s, we may assume that the sequence continues arbitrarily far. In fact, because the reals are complete (meaning that all Cauchy sequences in the reals converge), the sequence $(M_n)$ converges to some $M \in (0,1)$. (If we're going to prove something about the real numbers, we're going to have to use some properties of the real numbers. For instance, the real numbers are a totally ordered, complete field. Now a sequence of reals in $(0,1)$ can converge to $0$ or $1$, so not to an element of the interval, but our prescription for selecting the mismatching digits in each decimal place are chosen to ensure we land in the interior of the interval.)
5. Now we go an entirely different way than the way you describe and I'm going to drop out of this list because I want to ramble on for a bit...

First a comment about the convergence of $(M_n)$. Our process of constructing $M_{k+1}$ from $M_k$ means that $M_{k+1}, M_{k+2}, \dots$ all lie in the interval $(M_k, M_k + 10^{-(k+1)})$. Since we don't change any of the leading digits, at every step, the interval containing all of the remaining elements of the sequence of $M$s becomes 10-times smaller. The limit infima and limit suprema of this sequence of intervals both converge and converge to the same real number, $M$.

Since $M$ is a real number in $(0,1)$ and $label$ is surjective, there is an $N$ in the natural numbers such that $label(N) = M$. But $M_N$ disagrees with $label(N)$ in the $N^\text{th}$ decimal digit and all subsequent $M_n$ for $n > N$ are restricted to lie in an interval which forces all of them to have the same disagreement with $label(N)$. Consequently, $label(N) \neq M$. In other words, $M$ is not the image of any natural number under the function $label$. This contradicts that $label$ is surjective and therefore contradicts that it is bijective.

The only assumption we are still conditional upon is "If $\mathbb{N}$ and $(0,1)$ have the same cardinality, they may be placed in bijection." We called that bijection "$label$". We've just proven "if $label$ is bijective then $label$ is not bijective", which is a logical impossibility. Therefore, there is no such function, $label$, placing $\mathbb{N}$ and $(0,1)$ in bijection. Therefore, $\mathbb{N}$ and $(0,1)$ do not have the same cardinality.

Now here's a different way to attack the last step.

Since $M$ is a real number in $(0,1)$ and $label$ is surjective, there is a subset of $\mathbb{N}$, $S$, such that for all $s \in S$, $label(s) = M$. By the well-ordering principle, $S$ has a least element, $N$. But $M_N$ (and all subsequent elements of the sequence, and therefore $M$) disagree with $label(N)$ in the $N^\text{th}$ digit, so $label(N) \neq M$, a contradiction.

Either way the proof is trying to capture this dichotomy:

• If $M$ is "on the list", meaning in the image of $label$, we contradict that $M$ disagrees with every item on the list in at least one digit. So $M$ is "not on the list".
• If $M$ is "not on the list", we contradict that $label$ is surjective. That is, the list cannot be complete; it cannot include every element of $(0,1)$.

We conclude -- no matter how you try to do it, you cannot make a bijection between $(0,1)$ and $\mathbb{N}$. If you assume that you have, you produce a contradiction. Therefore, such a bijection does not exist.

Answer 2

To understand the issue here you need to distinguish clearly between the naive notion of infinity and the mathematical notion of infinity as formalized by Cantor and his set-theoretic successors.

When you write that "however infinity is not even definite" you are referring either to naive/intuitive notion of infinity or making a philosophical point, but the mathematical claim concerning the uncountability of the set of real numbers is referring to a precise mathematical notion that may or may not correspond to your intuitions or philosophical conceptions of infinity.

Also keep in mind that the goal is not "to find a number M that goes beyond a countable collection" but rather to prove that the set of real numbers as a set is uncountable. A typical way of phrasing the argument involves a proof by contradiction which does proceed by exhibiting a number that's not on the list, but the part about exhibiting such a number is part of a never-never world of an argument whose result is a contradiction, rather than being a bona fide new number.