Understanding Cantor's Diagonalization Proof: A Brief Explanation

[Jarvis323]

I wrote a long response hoping to get to the root of AlienRender's confusion, but the thread closed before I posted it. So I'm putting it here.

You know very well what digits and rows. The diagonal uses it for goodness' sake. Please stop this nonsense.

When you ASSUME that there are as many real numbers as there are digits in a single real number, this isn't true for N either. It's a given that it isn't true. If it's not true for N, what does it matter that it's not true for R?

It seams you're argument is something like this:

let $f(n) = 2n$, this is a one-one and onto mapping of the natural numbers onto the even natural numbers.

Let $L$ be the enumeration/list $2, 4, 6, 8, ...$ . And let's call $L$ a thing, a complete object.

Now suppose you want to take $L$ and concatenate some more numbers, say $3k$, for all $k$ in $N$, to make an extended list, $L'$ . (For now let's ignore the problems with the idea of concatenating to an infinite list. )

Well, wait a minute, isn't there a problem? Because if we add these new numbers, we need new rows/natural numbers to correspond them to, but we've used them all up. It seams there is a contradiction since $L'$ is a subset of $N$, yet we can't seam to construct $L'$ from $L$ in a way that preserves a bijection.

It would seam that $g(n)=L'_n$ is not a bijection with $\{L'_i \mid i \in N\}$ and $N$, so does this imply that $|\{L'_i \mid i \in N\}| > |N|$, a contradiction since it's a subset of $N$? What in the world is $g(n) = L'_n$ if not $f(n)$ which it cannot always be? Conclusion? Well, you can't concatenate to the end of an infinite list can you?

Actually, IMO, infinite enumerations should be considered as a processes. What does it mean to concatenate processes? Not the same thing as what one imagines when they think of concatenating two lists. In this view, diagionlization would perhaps be considered a coupled and synchronized process in which for each step of process 1, there is a step of process 2, yet there is no final step.

Lastly, on a tangent, we can't do diagonalization on an enumeration of $N$ in unary, because we have only one symbol. If we use binary, we have the problem that the number of digits grows slower than the number of rows. We could however do something similar, just one by one, add the numbers on the "rows" construct the new one, call it $x$, through the application of $g(n)=\sum_{i=1}^nn$ at step $n$. $L_n=g(n)$ is fine, but the problem is that $x$ is infinite and thus not a natural number, so it was never supposed to be on the list in the first place. This is why the proof would not work, meaning that diagonalization in this way doesn't prove $|N|<|N|$.

In the case of diagonalization of an assumed list of all of the reals, we don't have the limitation, since we are working in the fractional parts of the numbers, thus the constructed number is still finite in size, and reals are allowed to require an infinite length representation.

 

[AlienRenders]

I'm happy to continue this in private if possible. I want to respect the mods decision.

 

[stevendaryl]

I wrote a long response hoping to get to the root of AlienRender's confusion, but the thread closed before I posted it. So I'm putting it here.It seams you're argument is something like this:

let $f(n) = 2n$, this is a one-one and onto mapping of the natural numbers onto the even natural numbers.

Let $L$ be the enumeration/list $2, 4, 6, 8, ...$ . And let's call $L$ a thing, a complete object.

Now suppose you want to take $L$ and concatenate some more numbers, say $3k$, for all $k$ in $N$, to make an extended list, $L'$ . (For now let's ignore the problems with the idea of concatenating to an infinite list. )

Well, wait a minute, isn't there a problem? Because if we add these new numbers, we need new rows/natural numbers to correspond them to, but we've used them all up. It seams there is a contradiction since $L'$ is a subset of $N$, yet we can't seam to construct $L'$ from $L$ in a way that preserves a bijection.

You can't just concatenate to the end of an infinite list, but what you can do is merge two lists. You have an original list:

$L_A = [2, 4, 6, 8, ...]$

You have a second list: $L_B = [3, 6, 9, ...]$.

Then you merge them to get a new list:

$L' = [2, 3, 4, 6, 6, 9, 8, 12, ...]$

Your first list is $f(n)$, your second list is $g(n)$, then the merged list is:

$h(n) = f(n/2)$ if $n$ is even.
$h(n) = g((n-1)/2)$ if $n$ is odd.

 

[fresh_42]

I'm happy to continue this in private if possible. I want to respect the mods decision.

We made an exception here in this specific case:

• @Jarvis323 put a lot of effort in his answer and the parallel closure of the previous thread was more bad luck, so this is not really a re-opening.
• @AlienRenders, you are the only "client" on this topic, as everyone else has no problems with Cantor's argument.
• The post above should be seen as an attempt to set the discussion back on track, without a heated debate drifting into accusations from whomever.

We would appreciate a public debate instead of a hidden one. As long as everybody concentrates on mathematics, this shouldn't be a problem.

 

[stevendaryl]

I think, rather than talking about real numbers, we can first discuss binary sequences.

A binary sequence is defined to be a function $f$ that takes a natural number $n$ and returns either 0 or 1.

An infinite list of objects of type T is defined to be a function $L$ that takes a natural number $n$ and returns an object of type $T$.

Cantor's proof shows that if $L$ is an infinite list of binary sequences, then there is a binary sequence that is not on the list. That is:

For all $L$, if $L$ is an infinite list of binary sequences, then there is a binary sequence $f$ such that for all natural numbers $j$, $L(j) \neq f$.​

So this business of whether index sets are one-to-one is just blather. By definition, the domain of a binary sequence is the natural numbers. By definition, an infinite list is a function whose domain is the natural numbers. So by definition, the domain of $L$ and the domain of $f$ are the same. The index sets are the same. So the expression $L(i)(j)$ makes sense for any two natural numbers $i$ and $j$. It means:

Let $f$ be the binary sequence $L(i)$, and return $f(j)$.
​

Since $L(i)(j)$ makes sense for any $i$ and $j$, as long as they are both natural numbers, then the function:

$d(n) = 1 - L(n)(n)$

is well-defined. And clearly, it is a binary sequence; it gives 0 or 1 for every $n$. And clearly it is not on the list $L$.

That's Cantor's diagonal argument.

 

[Jarvis323]

You can't just concatenate to the end of an infinite list, but what you can do is merge two lists. You have an original list:

$L_A = [2, 4, 6, 8, ...]$

You have a second list: $L_B = [3, 6, 9, ...]$.

Then you merge them to get a new list:

$L' = [2, 3, 4, 6, 6, 9, 8, 12, ...]$

Your first list is $f(n)$, your second list is $g(n)$, then the merged list is:

$h(n) = f(n/2)$ if $n$ is even.
$h(n) = g((n-1)/2)$ if $n$ is odd.

Yes, but in this case, $L$ is really not part of the list anymore. The mapping of the elements of $L$ to $N$ is no longer onto. So AlienRenders problem that $N$ has been used up no longer holds. Then you are left with the normal conceptual task of understanding how an infinite subset of $N$ can have the same cardinality, but no issue with diagonalization itself.

 

[stevendaryl]

Yes, but in this case, $L$ is really not part of the list anymore. The mapping of the elements of $L$ to $N$ is no longer onto. So AlienRenders problem that $N$ has been used up no longer holds. Then you are left with the normal conceptual task of understanding how an infinite subset of $N$ can have the same cardinality, but no issue with diagonalization itself.

The merging idea is the reason that the rational numbers can have the same cardinality as the naturals, even though the naturals are a subset of the rationals.

 

[stevendaryl]

I think, rather than talking about real numbers, we can first discuss binary sequences.

A binary sequence is defined to be a function $f$ that takes a natural number $n$ and returns either 0 or 1.

An infinite list of objects of type T is defined to be a function $L$ that takes a natural number $n$ and returns an object of type $T$.

So one can first establish Cantor's theorem for binary sequences and infinite lists: There is no infinite list of binary sequences that contains every possible binary sequence. That's pretty much a one-line proof. There is no issue of whether matrices are square, or whatever.

Then you can go on to show a few other things:

• There is a one-to-one map between binary sequences and reals in the range 0 to 1. That's pretty easy.

This implies that there is no infinite list of reals that contains every real, either.

In contrast, there is an infinite list of fractions that contains every fraction. Cantor showed that.

 

[Jarvis323]

You can't just concatenate to the end of an infinite list, but what you can do is merge two lists. You have an original list:

$L_A = [2, 4, 6, 8, ...]$

You have a second list: $L_B = [3, 6, 9, ...]$.

Then you merge them to get a new list:

$L' = [2, 3, 4, 6, 6, 9, 8, 12, ...]$

Your first list is $f(n)$, your second list is $g(n)$, then the merged list is:

$h(n) = f(n/2)$ if $n$ is even.
$h(n) = g((n-1)/2)$ if $n$ is odd.

The merging idea is the reason that the rational numbers can have the same cardinality as the naturals, even though the naturals are a subset of the rationals.

Yeah, the whole issue is what it means to merge, or add numbers to the list. They have to be put somewhere so to speak. Conceptually, to put one at the end (of an infinite list) means to map the largest natural number to something. The problem is that there is no largest natural number. So, we have to insert them somewhere before the end, at some index. Fortunately with infinite sequences, we can make room, shift things around, and reassign.

 

[AlienRenders]

Remapping and catenation is all fine outside of Cantor's diagonal. Enumerating Q for example is an interesting technique. But is the infinite identity matrix not a proper subset of my list if I write N binary strings and compare by digits? Is there not a 1 in each possible position n in this subset? My question, if misguided, is where do the "other" digit positions comes from for constructing the diagonal? That's it. That's what I don't understand.

I know a subset of N can be remapped to N outside of Cantor's diagonal. I have no problem there. But Cantor's diagonal doesn't allow it. It is specifically using digit positions to map N rows. But this will only map a proper subset of any list regardless if it has N or R elements. So that there are "new" numbers for R doesn't impress me. You can do the same with N. The conclusion of Cantor's diagonal argument should have been that he's proven that the digits will always be a proper subset of the rows unless you use the infinite identity matrix (unary enumeration).

Lastly, on a tangent, we can't do diagonalization on an enumeration of NNN in unary, because we have only one symbol. If we use binary, we have the problem that the number of digits grows slower than the number of rows. We could however do something similar, just one by one, add the numbers on the "rows" construct the new one, call it xxx, through the application of g(n)=∑ni=1ng(n)=∑i=1nng(n)=\sum_{i=1}^nn at step nnn. Ln=g(n)Ln=g(n)L_n=g(n) is fine, but the problem is that xxx is infinite and thus not a natural number, so it was never supposed to be on the list in the first place. This is why the proof would not work, meaning that diagonalization in this way doesn't prove |N|<|N||N|<|N||N|

You can do diagonalization on an enumeration in unary. You can't flip the digits though if that's what you mean. But the diagonal and the infinite identity matrix are one and the same. There's no need to add at the "end" to "finish" my list. The infinite identity matrix is for visualization in this particular case. It let's us see what subset will be used. You can swap rows with their actual locations. Doesn't change anything. So my enumeration works fine all the way through. But Cantor's diagonal cannot go through my whole list because it is restricted to the subset of digits.

When you're going through my list one row at a time and you reach a row that matches a row from the infinite identity matrix, does the digit that is a 1 not have to match a unique position x? Does it not have to be a unique position not used by any other row from that subset?

This means that there is a bijection between the rows of I and the columns D (digits), I ⊂ L (my list), and there is an assumed bijection between D and L. These can't all be true at the same time unless I and L are the same set (the identity matrix), but L is not the identity matrix.

 

[stevendaryl]

Remapping and catenation is all fine outside of Cantor's diagonal. Enumerating Q for example is an interesting technique. But is the infinite identity matrix not a proper subset of my list if I write N binary strings and compare by digits?

Try to make the discussion self-contained. Pretend that we have no idea what you mean by "the infinite identity matrix" and "proper subset" and "my list" and "compare by digits".

What I wrote was Cantor's theorem. If you have a problem with it, then refer to that theorem, not to something that you made up.

 

[AlienRenders]

So this business of whether index sets are one-to-one is just blather. By definition, the domain of a binary sequence is the natural numbers. By definition, an infinite list is a function whose domain is the natural numbers. So by definition, the domain of LLL and the domain of fff are the same. The index sets are the same. So the expression L(i)(j)L(i)(j)L(i)(j) makes sense for any two natural numbers iii and jjj. It means:

Let fff be the binary sequence L(i)L(i)L(i), and return f(j)f(j)f(j).
Since L(i)(j)L(i)(j)L(i)(j) makes sense for any iii and jjj, as long as they are both natural numbers, then the function:

d(n)=1−L(n)(n)d(n)=1−L(n)(n)d(n) = 1 - L(n)(n)

Does there not exist a set S ⊂ L where each element s of S is defined as a string of 0's except for d(n) = 1. The range is a subset of L, yet the domain n is the same. That's a big problem, no?

 

[stevendaryl]

Yeah, the whole issue is what it means to merge, or add numbers to the list. They have to be put somewhere so to speak. Conceptually, to put one at the end (of an infinite list) means to map the largest natural number to something. The problem is that there is no largest natural number. So, we have to insert them somewhere before the end, at some index. Fortunately with infinite sequences, we can make room, shift things around, and reassign.

We can actually make sense of putting something on the end of an infinite list, but then we're not indexing the list with naturals, we're indexing the list with ordinals.

Roughly speaking, an ordinal is a way of well-ordering a set. To say that we have a well-order of a set $S$ means that we have a binary relation $x \prec y$ such that for every subset of $S$, $S' \subseteq S$, there is a smallest element, according to $\prec$.

For the natural numbers, the simplest ordering is called $\omega$. That's the usual one: $0, 1, 2, ...$. We say that $x \prec y$ if there is a positive natural $z$ such that $x+y = z$.

If we want to stick something at the end, we can do that with a different $\prec$.

Define $x \prec y$ if either $y = 0$ or $x > 0$ and $x < y$. That's the ordering $\omega + 1$ which can be represented as:

$1, 2, 3, ..., 0$

We can similarly come up with the ordering $2 \omega$:

Define $x \prec y$ if either $y$ is even and $x$ is odd, or if they are both odd or both even and $x < y$. That ordering can be represented as:

$1, 3, 5, ... 2, 4, 6, ...$

You're putting the evens after all the odds.

If you want to consider a "list" where you put things at the end of infinitely many, then you can consider such a list to be a function from an ordinal $\alpha$ into the set.

 

[stevendaryl]

Does there not exist a set S ⊂ L where each element s of S is defined as a string of 0's except for d(n) = 1. The range is a subset of L, yet the domain n is the same. That's a big problem, no?

Please use the notation that I introduced. Don't make up your own.

By definition, a binary sequence $f$ is a function from naturals to $\{0, 1\}$.
By definition, a list of binary sequences is a function $L$ from naturals to binary sequences.
Given any list of binary sequences $L$, there is a corresponding binary sequence that we can construct that is not an element of $L$:

$d(n) = 1 - L(n)(n)$

Please refer to these when you make a comment.

What do you mean "a set $S \subset L$"? $L$ is a list, which is a function. What do you mean by saying that $S$ is a subset of $L$? What do you mean by saying that the range is a subset of $L$? What do you mean by the domain? What $L$ are you talking about? What $S$ are you talking about?

 

[AlienRenders]

Try to make the discussion self-contained. Pretend that we have no idea what you mean by "the infinite identity matrix" and "proper subset" and "my list" and "compare by digits".

What I wrote was Cantor's theorem. If you have a problem with it, then refer to that theorem, not to something that you made up.

The infinite identity matrix is basically the diagonal in Cantor's proof. You can represent it as a grid of 0's with 1's along the diagonal.

Let f(n) be a row/element. d(n) of f(n) is 1. Everything else is 0.I'm not aware of any other definition for "proper subset". It's where all elements of set A is "contained" in set B. I normally use it that they are different sets, but that's not required by the actual definition. I try to mention the distinction when it doesn't clutter up the discussion even more.

"My list" is the list of N given to Cantor's proof in the form of an enumeration of binary strings. Yes, it's supposed to be R. But I'm trying to demonstrate that Cantor's proof has the same result on N.

"Compare by digits" simply means matching digits. The position must be the same and the row must be the same. At that position, you compare the glyph (or whatever you want to call it) in each set.

 

[stevendaryl]

The infinite identity matrix is basically the diagonal in Cantor's proof. You can represent it as a grid of 0's with 1's along the diagonal.

Let f(n) be a row/element. d(n) of f(n) is 1. Everything else is 0.

Please don't use the word "row". Cantor's proof is about functions. People talk about in terms of matrices and rows to help give some intuition about his proof, but that is inessential.

Cantor's proof is that for every function $L$ from naturals to binary sequences, there is a binary sequence $f$ that is not in the range of $L$.

 

[Jarvis323]

This means that there is a bijection between the rows of I and the columns D (digits), I ⊂ L (my list), and there is an assumed bijection between D and L. These can't all be true at the same time unless I and L are the same set (the identity matrix), but L is not the identity matrix.

There exists a bijection between the rows of $I$ and the columns $D$. But there also exists functions from rows of $I$ to columns $D$ that are not onto. The bijection between $D$ and $L$ need not use a bijection from $I$ to $D$ as a piece. The function that maps the "rows" of $L$ to digits (needed to perform diagonalization) does also map each row of $I$ to $D$, but that partial function is not onto. This is fine right?

 

[fresh_42]

I'm sorry, but as you keep hiding behind undefined ramblings you don't leave me a choice:

The infinite identity matrix is basically the diagonal in Cantor's proof...

It is not.

... I'm not aware of any other definition for "proper subset"...

Which subset? Of what?

... "My list" is the list of N given to Cantor's proof in the form of an enumeration of binary strings...

N what? You just mentioned f(n) followed by an undefined d(n) and now comes N.

... Yes, it's supposed to be R...

What is it again?

... But I'm trying to demonstrate that Cantor's proof has the same result on N.

This sentence hardly manages to pass the linguistic test, but terribly fails to provide content. Cantor's proof has only a truth value as a result, no N.

"Compare by digits" simply means matching digits. The position must be the same and the row must be the same. At that position, you compare the glyph (or whatever you want to call it) in each set.

Yes, and that is the point: We can construct an element from the "second", better modified list, which cannot possibly have been in the first, better original list. Nobody compares lists, or sets.

1. List all numbers.
2. Change all diagonal elements by adding one according to the basis the numbers are written in.
3. Extract the new diagonal and interpret it as number.
4. Recognize that it cannot have been listed under point 1.
5. Conclude that the list under point 1 wasn't complete.

That's all what is about to say - regardless how many phrases you invent to hide behind.

This thread will remain closed and reopenings will be deleted.