Cantors diagonal problem revisited

Question

This topic seems to have been discussed in this forum about 6 years ago. I have reviewed most of the answers. The proof I have is labelled Cantor's Second Proof and takes up about half a page (Introduction to Real Analysis - Robert G. Bartle and Donald R. Sherbert page 50). I apologise if I missed something important but all the answers seem to just make the subject more obscure. The proof by Bartle and Sherbert is relatively straight forward but on reflexion I have found 3 objections:

1. No infinite list is constructed. They are just produced - like those cookery TV shows - here is a cake I made earlier. I think with something so fundamental it should be exaplained how the cake was made.
2. The proof demonstrates that there are missing numbers from the list but does not state or prove how many.
3. If you include the construction of the infinite numbers you arrive at a paradox.

My argument (I doubt if it could be understood by a 5 year old but a smart 12 year old should be able to follow it):

Let us start with a finite list. To keep the numbers small let's use binary. Assume an n*n structure with n=3. The structure looks like this:

1. 000
2. 001
3. 010

Now one can easily find a three digit number missing from the list, e.g. 100. A combination of 3 digit binary numbers gives 8 values (if 0 is included). (A 3 digit base 10 number has 1,000 possibilities of course). So n messages each with n digits will always have missing values. There is no mystery here. It is just basic school mathematics. In fact we can calculate the exact number of missing numbers.

For n digits in base b there are exactly $b^n$ possible numbers that can be created. So we create a finite list with n digits and $b^n$ numbers. We have constructed this so there are no missing numbers. If we apply the diagonal argument to this list we cannot create any more numbers unless we add digits.

Now comes the possibly interesting part: What happens if we take a limit as $n \to \infty$?

Well there are two ways to do this and this is where the paradox comes in:

(1) It would seem reasonable to assume that $b^n$ expands faster then n. So let's swap this around and call $b^n = K$. Then the number of digits is $\log K$. So we allow $K \to \infty$. But then $\log K \to \infty$. But note from this construction: There are no missing numbers.

(2) Let's take the opposite view and assume an $n \times n$ structure. We have shown above this has exactly $b^n-n$ missing possible number combinations. We let $n \to \infty$. So in this case: there are $b^\infty-\infty$ missing numbers. This construction supports Cantor's argument.

I think the Paradox resolves around defining a number as an infinite list. In which case you can apply argument (2). But you cannot derive this by construction. This seems to imply the impossibility of constructing the irrational numbers. We need first an infinite set as a static data structure. But there is no such thing. An infinite set is the result of a process which as a limit to oo can never be completed. oo itself is not a number.

So how is this Paradox resolved?

Answer 1

In some sense, your problem here is assuming that all of the quantities involved here are "continuous"; that

$$ q \left( \lim_n x_n \right) = \lim_n q(x_n) $$

but there is no reason to think so. Many functions aren't continuous. In a precise sense, most functions aren't continuous! We just like to study continuous ones, which is why you see them a lot.

There are further issues here that it's not even clear we're in a situation where the idea of taking a limit makes sense.

---

Incidentally, a fact related to the argument idea you seem to have is the following.

Let $\mathcal{P}_f(X)$ denote the collection of all finite subsets of a set $X$.

Then, if $X$ is a countably infinite set, $\mathcal{P}_f(X)$ is also countably infinite.

The full power set $\mathcal{P}(X)$, however, is well-known to be uncountable.

I imagine that your line of thought, if you were to actually make it precise and work through the problems, will turn out to be something akin to you actually thinking about $\mathcal{P}_f(X)$ rather than $\mathcal{P}(X)$.

Answer 2

1. No infinite list is constructed. They are just produced - like those cookery TV shows - here is a cake I made earlier. I think with something so fundamental it should be exaplained how the cake was made.
2. The proof demonstrates that there are missing numbers from the list but does not state or prove how many.
3. If you include the construction of the infinite numbers you arrive at a paradox.

1. The goal of Cantor's argument is to show that the cardinality of the real numbers is strictly greater than the cardinality of the natural numbers. To show this, it is sufficient to show that there is no surjective function $\varphi : \mathbb{N} \to \mathbb{R}$. The argument then proceeds by contradiction: we suppose that there is such a surjection, then show that it leads to a contradiction. This is done by constructing a real number which is not $\varphi(n)$ for any natural number $n$.

   Note that I have not used the word "infinite list" here anywhere. This is an imprecise statement of the argument that gives a nice heuristic, but is not entirely rigorous. If you wanted, you could regard $\varphi$ as providing that infinite list ($\varphi(1)$ is the first item on the list, $\varphi(2)$ is the second item on the list, and son on), but it is better to use a more precise language.

   Again, the takeaway is that the existence of this "infinite list" is an assumption that we make in order to arrive at a contradiction.

2. Why would you need to know how many "missing numbers" there are from the list? Again, the statement of the theorem is that the cardinality of $\mathbb{R}$ is strictly greater than the cardinality of $\mathbb{N}$. The theorem is not "There are three more real numbers than there are natural numbers." The only thing that the argument attempts to prove is that there is no surjection from $\mathbb{N}$ to $\mathbb{R}$. Now, if you are interested, there are interesting things which can be said vis-à-vis comparing infinite cardinals. Long story short: if you remove any countable collection from $\mathbb{R}$, the remaining set has the same cardinality as $\mathbb{R}$.

3. Not at all. As soon as you tell me what the $n$-th digit of the $n$-th number is (where by "the $n$-th number", we really mean the image of a natural number $n$ under the surjection $\varphi$), I can give you the $n$-th digit of a number that is not on your "list".

The rest of your question is spent attempting to construct a counter-example to Cantor's argument (which you almost certainly aren't going to be able to do without being able to identify where Cantor's argument goes wrong (which you won't be able to do, because Cantor is provably correct)). So the question is: where do your argument go wrong?

Your fundamental problem seems to be the assumption that all infinities are the same and that we can pass limits around willy-nilly (i.e. all limits are continuous). While I've been typing, it appears that Hurkyl addressed this pretty well, so I'm going to finish by once again suggesting that you have a look at infinite cardinals.