I feel I must be wrong, but how? Regarding a contradiction with Cantor Diagonalization Proof

Question

I'm very new to formally describing maths, so please accept my apologies in advance for anything that's not as clear as it could be.

Background

I do not doubt that there are different cardinalities of infinite sets, but I'm still a little worried about diagonalisation. I was initially repelled without understanding that diagonalisation works within a set of axioms (ZF/ZFC). Now I better understand the axioms, I think one might be incompletely defined... (big claim, I know - hence wondering where I've gone wrong)

The "Inconsistency"

The current definition of the axiom of infinity makes the construction of infinite decimal expansions, one by one, possible. What if that's not true? (or at least leads to an inconsistency?). What if infinite decimal expansions are allowable only for defined numbers? (although I also believe all Reals can be constructed... but that's a side issue)

e.g.

0.00000000...
0.50000000...
0.55000000...
0.55500000...
0.55550000...

If we use diagonalisation to replace selected 0's with 5's we should be able to see that 0.5555... cannot be contained in the list - which seems reasonable at first.

BUT

What about the number that is being created by the addition of the infinite sequence 0 + 0.5 +0.05 + 0.005...

(which looks like this)

0.00000000...
0.50000000...
0.55000000...
0.55500000...
0.55550000...

If diagonalisation proves that 0.5555... isn't on the list (which is what is suggested by substituting the diagonal 0's with 5's) then how do we explain the inability to "create" 0.5555... using the same infinite list? (you could argue that 0.5555... is the limit of the sequence - but that doesn't explain why one infinite decimal can be created by diagonalisation, whilst another can't be created by also adding one digit at a time).

To me, this suggests that diagonalisation never creates an infinite length decimal expansion (and hence never "settles" to a Real number). I believe that there must be a better way to describe Real numbers (and actually believe that infinite decimals are very handy but do not properly describe the properties of Real numbers).

I'd really appreciate thoughts on where am I going wrong.

Thanks

Answer 1

You write:

---

"If diagonalisation proves that 0.5555... isn't on the list (which is what is suggested by substituting the diagonal 0's with 5's) then how do we explain the inability to "create" 0.5555... using the same infinite list? (you could argue that 0.5555... is the limit of the sequence - but that doesn't explain why one infinite decimal can be created by diagonalisation, whilst another can't be created by also adding one digit at a time)."

---

This is not a compelling argument simply because it is impossible to understand your meaning or point. I added the boldface to highlight particularly unclear parts. It seems like you have hidden meanings and assumptions for words like "create" and "adding one digit at a time." I also do not know what you are referring to in your statement "why one infinite decimal...whilst another..."

While I do not know what your point of concern is, it sounds like you might be arguing that a single number cannot be created/described/communicated in two different ways. However, consider:

"The largest integer less than 20"

"The smallest integer greater than 18"

These are two different ways of describing "19." There is no inconsistency.

---

In order to understand Cantor, I advise removing all loaded definitions. Forget about real numbers, and so certainly forget about concepts such as sums or limits. Suppose you have an infinite matrix: $$(a_{ij}), \quad a_{ij} \in \{0, 1, ..., 9\} \quad \forall i, j \in \{1, 2, 3, ...\}$$ So each "row" of this matrix can be viewed as an infinite sequence of digits, each digit in the set $\{0, ..., 9\}$. I do not care how this matrix is defined or constructed. Perhaps there is a formula or algorithm to compute $a_{ij}$ for each $i,j$ pair. For example: $$ a_{ij} = (i+j^2) \mod 10 $$ Or perhaps this matrix is formed in some other way. It does not matter. The Cantor argument shows how to construct a sequence of digits in $\{0, ..., 9\}$ that is not the same as any row of the matrix $(a_{ij})$.

Hopefully you can at least agree to that. If you want to wax philosophical about "what infinite matrices are we allowed to construct/consider/imagine?" you can do that all you want. Assuming there is some class of such matrices that you allow yourself to construct/consider/imagine, then Cantor applies to every matrix in that class. So, even restricting to whatever class of matrices you want, it is impossible to construct/consider/imagine a matrix where every possible infinite sequence of digits in $\{0,...,9\}$ appears as some row. Another way of saying this is that it is not possible to "list" all infinite sequences of digits in $\{0, ..., 9\}$.

Answer 2

Would you say that the number $3$ is an element of $\{1,2\}$? No. It's not.

Just because you have a sequence of real numbers, and their sum is equal to their diagonal does not mean that the diagonal is one of these numbers.

Similarly, the set $\Bbb N$ is certainly not an element of $\{\{0,\ldots,n-1\}\mid n\in\Bbb N\}\}$, since this is a collection of finite sets and $\Bbb N$ is not a finite set.

And similarly, $0\notin\bigcup\limits_{n=1}^\infty[\frac1n,1)$, since $0$ is not in any of these intervals.

Do you see where I'm going with this? The point is that a limit is not the same as the sequence, and the diagonal argument shows that there is a real which is not on the list you've suggested, even if that diagonal happens to coincides with the limit of that list.

Answer 3

One version of the Axiom of Infinity says that there is a set, that I will call the counting numbers C, that (1) contains the number 1, and (2) if it contains the number c, it also contains the number c+1. The point of the Axiom is not just to define C. It is to establish that if you can define any object in an infinite collection of objects, then you have defined the entire collection of objects as a set. Part (2) of this Axiom can define any counting number by constructing it from its predecessor. So it defines every counting number, without having to actually state each member.

That's all that the process of diagonalization does. Assuming you have an infinite list of strings with infinite digits, it says that there is another string, not in that list, where (1) the first character is not the first character of the first string and (2) the character after the cth character is not the (c+1)th character of the (c+1)th string. I know that this looks like an awkward way to define the process, but by making it parallel the Axiom of Infinity, I think it is easier to see that it defines the entire string. So the issue you thought was there, is not.

Note 1: Cantor did not apply the process to real numbers, by explicit choice. He applied it to strings. This avoids confusion with some properties of real numbers.

Note 2: It is not a proof by contradiction. To be one, the contradiction you find must follow from the entire statement you assume. The supposed contradiction in Cantor's proof does not follow from assuming you have an infinite list of ALL strings with infinite digits, just that you have an infinite list of SOME. It still proves the proposition since it proves that any such list can't have all such strings.