Undergrad Regarding Cantor's diagonal proof

[AlienRenders]

Sorry to dig this up, but what happens if my list is not square? The digits and rows are not one to one. They are both countable, but when my list is enumerated, they are not one to one. What then? It seems to me Cantor's diagonal proof only proves the digits and rows are not one to one in that configuration. It's been incorrectly interpreted as meaning different cardinality. Cantor's diagonal can only take a subset of any infinite list. Unless I'm missing something, you can't even provide it N in base 2. It will not use all the numbers in my list.

Another way to see this is if I don't give you the numbers in my list, but instead another list that is mapped one to one. This mapping is for visualization purposes only. The same effect will happen with or without the mapping.

The first row maps to 10000...
The second row maps to 01000...
The third row maps to 00100...

etc. The 1's are on the diagonal.

This isn't even N. Not even close. If you take a diagonal and flip, you'll get zero. And zero is definitely in my mapping.

The mapping just shows what subset Cantor's diagonal is using. It's easier to see. And it's clear it can't possibly go through all N, much less R. It's the fallacy of using base 3 to show numbers that don't exist in base 2 for example. It's the same thing.

So when people ask for a counter-example, it doesn't exist. Not because such an enumeration can't be provided, but because Cantor's diagonal will never use the entire list given. It will only ever use a subset. The only way to demonstrate the flaw is to show how it only uses a subset on an known countable enumeration as I've done above. The reason people have difficulty explaining the flaw is because the very fact that it always finds a number not in the list is itself the flaw.

Short story is that Cantor's diagonal DOES give a number already in the list. It just doesn't use the whole list. The assumption that the rows and digits are one to one in this configuration is flawed. Base 2, 3, 4, etc is not square. Just list N in binary. The diagonal is all zeros. The diagonal is well beyond the most significant digit on every row except the first few. The only square matrix is where only one digit is different from the rest. (All 0's and a single 1). This is a restricted numbering system that requires more digits per row than base 2 in the same way that base 2 requires more digits per row than base 3. It has been well known that you can't compare cardinality this way.

 

[FactChecker]

Sorry to dig this up, but what happens if my list is not square? The digits and rows are not one to one. They are both countable, but when my list is enumerated, they are not one to one. What then?

I'm not sure what you mean. Each number in its row is expressed in the digits that represent it. A number in row n has some digit in column place n. You just have to make your generated number have a different digit there and the proof will work. The generated number will be different from every number on the list.

 

[AlienRenders]

The infinite identity matrix will provide a digit for every digit in the diagonal. But 11000... for example will never be on that list. Cantor's diagonal will always a proper subset of any list given to it (aside from the identity matrix). There's no way around it. Your assumption is that the digits are mapped one to one with the rows which is not the case.

Said another way, as long as x = y when taking row x and digit y, you'll never get all the rows.

 

[FactChecker]

The infinite identity matrix will provide a digit for every digit in the diagonal. But 11000... for example will never be on that list.

That is a mistake. The assumption, for a proof by contradiction, is that the list includes every number. Then a number is generated which is not on the list. So the contradiction is proven. The generated number is known to be missing from the list because it is different from every number that is on the list. If you say at the beginning that there is a number missing from the list, you are already assuming what Cantor needs to prove.

 

[AlienRenders]

I don't think you understand. The string IS in the list. That's the whole point of this. Heck, it's trivial to show it's part of N. Clearly enumerable. But Cantor's diagonal cannot use it.

That's how Cantor's diagonal works. You give the entire list. Cantor's diagonal says "I'll just use this subset", then provides a number already in your list.

Here's another way to look at it. The identity matrix is a subset of my entire list. But I have infinitely more rows that don't require more digits. Cantor's diagonal won't let me add strings unless I also add digits.

 

[FactChecker]

I don't think you understand. The string IS in the list. That's the whole point of this. Heck, it's trivial to show it's part of N. Clearly enumerable. But Cantor's diagonal cannot use it.

That's how Cantor's diagonal works. You give the entire list. Cantor's diagonal says "I'll just use this subset", then provides a number already in your list.

No. That is completely wrong. The Cantor diagonalization method is meant to generate a number that is not on the list. That would prove that the set of all numbers can not be put in a list, and so is uncountable. See https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

 

[AlienRenders]

I'm explaining the flaw in Cantor's diagonal proof. It's impossible for it to use the whole list. And we're talking about N, never mind Q or R. Clearly, N is countable by definition.

 

[FactChecker]

I'm explaining the flaw in Cantor's diagonal proof. It's impossible for it to use the whole list. And we're talking about N, never mind Q or R. Clearly, N is countable by definition.

You have some misconceptions about the Cantor diagonal proof. I suggest that you review the link above in post #36.

 

[AlienRenders]

I understand the proof perfectly well.

The fact that it can only use a subset of N is how it always creates a "new" number. The flaw is simple. If there are N digits, then there will be a row for each digit where all digits on said row are 0's except for a single 1 (infinite identity matrix). There's no way around this. How do I add all the other rows in my list such as 110000...? I can't. The only way I can add a row is by associating it with a digit for Cantor's diagonal. But all digits are already accounted for.

It is this very limitation that Cantor uses to show that |R|>|N|, but it also shows that |N|>|N| which is fatal.

 

[FactChecker]

I understand the proof perfectly well.

The fact that it can only use a subset of N is how it always creates a "new" number. The flaw is simple. If there are N digits, then there will be a row for each digit where all digits on said row are 0's except for a single 1 (infinite identity matrix). There's no way around this. How do I add all the other rows in my list such as 110000...? I can't. The only way I can add a row is by associating it with a digit for Cantor's diagonal. But all digits are already accounted for.

It is this very limitation that Cantor uses to show that |R|>|N|, but it also shows that |N|>|N| which is fatal.

Do you truly think that you have found such a simple flaw in a proof that has been studied and used for almost 130 years by famous mathematicians? I do not understand what you are saying, but I very clearly understand the extremely simple and convincing Cantor method. You should review your logic in this proof very carefully.

 

[AlienRenders]

The flaw is indeed simple but extremely difficult to explain. My logic is sound. And I don't care for appeals to authority. If it's flawed, it's flawed. And it is. The simplicity of the "proof" is what makes it easy to gloss over its flaws.

I'll state the flaw in one more way.
These are trivial. I trust everyone agrees with the following.
1. For each digit column (assuming a grid of columns and rows), there will be a corresponding row in my list identical to a row from the identity matrix with a 1 in the same column. Basically, the strings 1000..., 0100..., 0010... etc will all be in my list somewhere.
2. The infinite identity matrix is a subset of N binary strings.
3. Using the columns necessary to enumerate the subset from #1, I can also enumerate all of N binary strings.

Now for the flaw... How do I add the rest of N strings to Cantor's list? All the digits have been accounted for.

The problem stems from the fact that the infinite identity matrix is also N, but does not represent all binary strings N.

 

[FactChecker]

The flaw is indeed simple but extremely difficult to explain. My logic is sound. And I don't care for appeals to authority. If it's flawed, it's flawed. And it is. The simplicity of the "proof" is what makes it easy to gloss over its flaws.

I'll state the flaw in one more way.
These are trivial. I trust everyone agrees with the following.
1. For each digit column (assuming a grid of columns and rows), there will be a corresponding row in my list identical to a row from the identity matrix with a 1 in the same column. Basically, the strings 1000..., 0100..., 0010... etc will all be in my list somewhere.
2. The infinite identity matrix is a subset of N binary strings.
3. Using the columns necessary to enumerate the subset from #1, I can also enumerate all of N binary strings.

Now for the flaw... How do I add the rest of N strings to Cantor's list?

Who says that it is necessary to add to the list? If you are claiming that, then you are already claiming that Canter's proof is done. But that is premature.

All the digits have been accounted for.

The problem stems from the fact that the infinite identity matrix is also N, but does not represent all binary strings N.

Likewise, there are an infinite number of even natural numbers, but they do not represent all natural numbers. IMHO, that proves nothing.

 

[AlienRenders]

Who says that it is necessary to add to the list? If you are claiming that, then you are already claiming that Canter's proof is done. But that is premature.

What? It's my list. More than that, it's all of N in binary. Pretty trivial stuff. If I can't add the rest, the proof is flawed. End of story.

Likewise, there are an infinite number of even natural numbers, but they do not represent all natural numbers. IMHO, that proves nothing.

But if the "proof" only uses even numbers, and never uses the odd numbers in your list, then produced odd numbers as the "new" numbers, it'd be trivial that this "proof" is flawed, wouldn't it? Well, same thing here. Cantor's diagonal proof only uses a subset of whatever list you give it. It's just not as trivial to see the subset it uses.

 

[FactChecker]

Cantor's diagonal proof only uses a subset of whatever list you give it.

The whole idea is to prove that the list can not be complete. As long as the Cantor method can come up with ONE number that is not on the list, then his proof is valid. In doing that, he makes sure that his number is different from EVERY number on the list by going one-by-one down the list and making one digit different from each number on the list. That is all I can say to explain it.
Are you saying that :
1) It is not possible to go one-by-one down the list, or that
2) Some number on the list does not have an n'th digit, or that
3) It is not possible to make a digit that is different from the n'th digit
4) The different digits of (3) make a number that is different from every number on the list.

You must specify which of those steps you object to and clearly expalin why, otherwise his logic is unescapable.

(PS. I do not understand where an identity matrix that you mention comes into this at all.)

 

[willem2]

These are trivial. I trust everyone agrees with the following.

These really aren't clear enough to agree or disagree with.

1. For each digit column (assuming a grid of columns and rows), there will be a corresponding row in my list identical to a row from the identity matrix with a 1 in the same column. Basically, the strings 1000..., 0100..., 0010... etc will all be in my list somewhere.

It's unclear what you mean with "my list". The way to state this is: Let L be a list of infinite strings that contain 10000..., 010000..., 001000.. etc..
2. The infinite identity matrix is a subset of N binary strings.

The matrix is a subset of what ?. I suppose you mean the rows of the identity matrix are a subset of the list L from step 1.
I take it that with "of N binary strings" means, that the number of strings is countable, which meansthat there is a bijection (a mapping that is one to one and onto) between the natural numbers and the rows of the identity matrix.

3. Using the columns necessary to enumerate the subset from #1, I can also enumerate all of N binary strings.

It's completely unclear what you mean with "the columns necessary to enumerate the subset from #1".

If you write like this you won't be able to communicate with mathematicians.

 

[AlienRenders]

But that's just it. It's impossible for Cantor's diagonal proof to use the whole list. Any number generated by Cantor's diagonal WILL be in the original list. It just won't be in the subset that it chose to use. Stating it more plainly, Cantor's diagonal does not in fact do what is claimed. It does not generate a new number. It's actually impossible for it to do so despite claims to the contrary. Going down the list in your #1 requires adding a new digit in order to construct the diagonal. This is not necessary for enumerating a list of binary strings. In fact, it's impossible except in the case of the identity matrix. That's where that comes into play. The infinite identity matrix is the subset that Cantor's diagonal uses. More than that, it's the ONLY set that it can use. You can swap rows to scramble the digits if you want, but the same subset remains.

So if Cantor's diagonal proof cannot use all the rows in my list, it is flawed. End of story.

 

[AlienRenders]

I take it that with "of N binary strings" means, that the number of strings is countable, which meansthat there is a bijection (a mapping that is one to one and onto) between the natural numbers and the rows of the identity matrix.

There is, but only outside of Cantor's diagonal as the digits and rows will no longer be one to one.

It's completely unclear what you mean with "the columns necessary to enumerate the subset from #1".

With the infinite identity matrix, there is one row per column. A bijection. The rest of N in the form of binary strings can be represented using the same columns as the infinite identity matrix. (edit: Or said simpler, by using a combination of rows from the identity matrix). But Cantor's diagonal needs to map rows to columns/digits. The columns have already been mapped.

 

[FactChecker]

But that's just it. It's impossible for Cantor's diagonal proof to use the whole list. Any number generated by Cantor's diagonal WILL be in the original list. It just won't be in the subset that it chose to use. Stating it more plainly, Cantor's diagonal does not in fact do what is claimed. It does not generate a new number. It's actually impossible for it to do so despite claims to the contrary. Going down the list in your #1 requires adding a new digit in order to construct the diagonal.

Why? Going down a list is simple and does not require adding a new digit. What new digit do you think needs to be "added"? Any number at list entry, n, already has a digit in position n and I can name a different digit for my created number.

 

[AlienRenders]

Going down a list is simple and does not require adding a new digit.

Agreed. Kind of my point actually. But you do need a new digit when constructing the diagonal.

Any number at list entry, n, already has a digit in position n and I can name a different digit for my created number.

Yes, but that digit in position n has already been used in the diagonal. To say otherwise, you'd need to prove there is no row with a 1 at position n and 0's everywhere else. If those rows do exist, and we know they do, then we know there is one such row for each digit. Where are you getting the other positions for the other rows?

 

[FactChecker]

Agreed. Kind of my point actually. But you do need a new digit when constructing the diagonal.

I just need a different digit from the one that is there. That is always possible. Other digits in other positions do not matter.

 

[AlienRenders]

I just need a different digit from the one that is there. That is always possible. Other digits in other positions do not matter.

No it isn't. There are no positions remaining. You've used them all up already. To say you have more positions means you need to prove there are "more" digits than there are in the infinite identity matrix. By "more", I mean positions that were not used in the diagonal of the infinite identity matrix which isn't possible. And since all binary strings can be created using a combination of those rows (binary OR operation if you will), what position isn't in use already?

 

[FactChecker]

No it isn't. There are no positions remaining. You've used them all up already.

We are talking about a different number, not a different position. IMHO, Canter's proof is easier in decimal notation. If the n'th number on the list has a 0 in position n, than there are any of {1,...,9} that I can put in the n'th position of my generated number. Proceding in that way, a number is generated which is guaranteed to be missing from the list. (The multitude of choises for generating numbers missing from the list shows clearly that there are orders of magnitude more missing from the list than are on the list.)

 

[SSequence]

I think there are some misconceptions in post#41. But, for someone having trouble understanding the proof, I don't know how they can be cleared without extensive explanations and diagrams.

One thing is that if you have a 1-1 correspondence f:ℕ→ E (natural to even), I can also define a set A so that A={0,4,8,12,16,20,24,...} and claim that f doesn't describe a 1-1 correspondence between ℕ and A ... which is correct, but it doesn't prove much.

But this doesn't matter, and we still have |ℕ|=|A|. And that's simply because of the function g:ℕ→ℕ so that g(x)=4x. This function g serves as 1-1 correspondence between ℕ and A. In general, we can easily show this kind of 1-1 correspondence between ℕ and any (infinite) subset of ℕ. That's by using the property that every non-empty subset of ℕ has a least element.

 

[FactChecker]

I'm afraid that this is my last attempt at making the proof clear. If there are any objections to any step, I can do no more.

 

[SSequence]

Also, in post#31 something to the effect of list not being "square" is mentioned. I thing this probably amounts to assumption that for a terminating decimal like:
0.3330
we only write down its first three digits(after decimal) in the list we make, which isn't correct. We always write-down its full expansion:
0.3330000000...

===================

Though, we do have to be a bit careful about the rule for changing the digits, as I mentioned in post#10. I think a good question to ask might be what should be the minimum restriction on the "digit change rule" so that the diagonalisation will "always" work (independent of the candidate list). Let's call the "digit change rule" as good in this case.

One example, of bad digit change rule I already mentioned in post#10:
0 to 1
1 to 2
2 to 3
...
9 to 0

====================

Here is an example of a good digit change rule:
0 to 2
1 to 3
2 to 4
3 to 5
4 to 6
5 to 7
6 to 8
7 to 9
8 to 0
9 to 1

====================

To elaborate a bit further if we consider the ambiguity related to terminating decimals, one thing that we see is that only the following transitions among digits are possible with two equivalent representations of the same terminating decimal.
0→1 and 1→0
1→2 and 2→1
2→3 and 3→2
3→4 and 4→3
4→5 and 5→4
5→6 and 6→5
6→7 and 7→6
7→8 and 8→7
8→9 and 9→8
9→0 and 0→9

So any digit change rule/function f:d→d (where d={0,1,2,3,4,5,6,7,8,9}) which avoids these transitions (while still diagonalising***) is already guaranteed to be a good one. But while this is a sufficient condition for a good digit change rule, I think there should be many digit change functions which contain some of these transitions and are still good.*** By diagonalising, I mean excluding the following transitions:
0→0
1→1
2→2
3→3
4→4
5→5
6→6
7→7
8→8
9→9
It can be easily shown that any good digit change rule must exclude all these transitions. In other words, excluding these transitions is a necessary condition for a good digit change rule.

 

[stevendaryl]

The flaw is indeed simple but extremely difficult to explain. My logic is sound. And I don't care for appeals to authority. If it's flawed, it's flawed. And it is. The simplicity of the "proof" is what makes it easy to gloss over its flaws.

Let me put this in terms of computable functions.

Let's say that a real number $r$ between 0 and 1 is computable if there is a computer function $f(n)$ that takes an integer $n$ and returns the digit in decimal place number $n$ of $r$.

Let's say that a sequence of reals between 0 and 1 $r_1, r_2, ...$ is computable if there is a two-argument function $g(m,n)$ which gives the digit in decimal place number $n$ of the real $r_m$. We will say that a real $r$ is on the list $g$ if there is some number $m$ such that $g(m,n)$ always gives decimal place number $n$ of $r$.

Here's the claim: You give me a function $g$, then I will give you a computable real that is not on the list $g$.

 

[stevendaryl]

Here's the claim: You give me a function $g$, then I will give you a computable real that is not on the list $g$.

The computable real $r$ has a decimal expansion given by the following algorithm: To compute decimal place number $n$,

1. First compute $g(n,n)$
2. If $g(n,n) = 5$, then return 3.
3. Otherwise, return 5.

This real number is not on the list $g$

 

[stevendaryl]

Cantor's proof is pretty air-tight.

1. Definition: If $M$ is a function of type $\mathcal{N} \times \mathcal{N} \rightarrow \{ 0, 1 \}$, and $R$ is a function of type $\mathcal{N} \rightarrow \{0, 1\}$, we can say that $R$ is a row of $M$, denoted by $R \in M$, if $\exists n: \mathcal{N} \forall j: \mathcal{N}\ | \ M(n,j) = R(j)$. In that case, we can say that $R$ is row number $n$ of $M$. We say that $R \not \in M$ if $\forall n: \mathcal{N} \exists j: \mathcal{N}\ | \ M(n,j) \neq R(j)$

2. Definition: If $M$ is a function of type $\mathcal{N} \times \mathcal{N} \rightarrow \{ 0, 1 \}$, then let $D[M]$ be the function of type $\mathcal{N} \rightarrow \{ 0, 1 \}$ defined by: $D[M](j) = 1 - M(j,j)$

3. Claim: $D[M](n) \neq M(n,n)$ Obvious

4. Claim: $\exists j: \mathcal{N}\ | \ D[M](j) \neq M(n,j)$ Obvious

5. Claim: $\forall n: \mathcal{N} \exists j : \mathcal{N}\ | \ D[M](j) \neq M(n,j)$ Since 4 is true for any $n$

6. Claim: $D[M] \not \in M$. That follows from Definition 1.

 

[JeffJo]

Sorry to dig this up, but what happens if my list is not square?

With infinite lists, "square" does not have the same meaning that it does with finite ones. If it has any meaning at all. Try this:

1. Imagine an infinite table, call it T1, where the rows and columns are labeled with the set of natural numbers. I don't care what you put in the table, just the labels. Since it has the same set labeling each dimension, it's "square," right?
   
2. Make a second table, call it T2, by simply doubling the labels for the columns in T1. You didn't change anything about the size of the table, so T2 is just as "square" as T1.
3. Make a third table, call it T3, by taking the odd-numbered columns out of T1. It seems like T3 cannot be square since you removed columns, but not rows, from a table that was already "square." But if you compare T3 to T2, you will see that they use the same sets as labels, so they are exactly the same size.

If the rows of your table are countably infinite, that means you can pair them up in a way you called one-to-one (which means something else in set theory) with the natural numbers |N. That is, there is a function R(n) that returns the nth real number in your table for every n in |N, and for the whole table. If R(n) is a real number, that means that it has a decimal representation where there is a digit associated with each power (1/10)^n. If you apply Diagonalization to this function R(n), it defines a new decimal representation that is different from every one that R(n) returns.

Now, you seem to think you have a table that is countably infinite in two dimensions, but not square. That just meand you are using a different function R(n) that you should. So just count the row labels, and replace each label ROW(n) with n. Viola! Your table is square by your standards.

This is one of the unusual properties of infinite sets that Cantor was trying to understand. Probably 90% of the arguments ever presented against Diagonalization, including yours, are based on misunderstanding these properties.

The digits and rows are not one to one.

"One-to-one," by which I think you mean "one-to-one and onto" or "bijective," is not a property of a pair of sets. It is a property of a function that maps one set to the other.

A function maps every member of the first set to one of the second. A function is "one-to-one" if every member of the first set is mapped to a different one of the second. It is "onto" if every one of the second is mapped this way. A function that has both properties is called a bijective function, or a bijection. That is the property I think you mean.​

With finite sets, the distinction between whether the description applies to the pair of sets, or the function, is irrelevant. If a bijective function exists, any function that is one-to-one is also onto, and any function that is onto is also one-to-one. That's why you have gotten away with ignoring it with finite sets. The same is not true with infinite sets. Even if a bijective function exists, you can find other functions that are one-to-one but not onto, or that are onto but not one-to-one. That's what makes the existence of a bijective function from |N the only requirement to apply Diagonalization.

1. For each digit column (assuming a grid of columns and rows), there will be a corresponding row in my list identical to a row from the identity matrix with a 1 in the same column. Basically, the strings 1000..., 0100..., 0010... etc will all be in my list somewhere.

Why? Even if you assume the table is complete, you can construct it so there is always a 0 in column n of R(n).

The problem stems from the fact that the infinite identity matrix is also N, but does not represent all binary strings N.

This is, in fact, related to the reason why the reals cannot be counted. In fact you can translate your statement directly into "|N cannot represent every binary string." Which is what Cantor proved with diagonalization.

 

[FactChecker]

No it isn't. There are no positions remaining. You've used them all up already. To say you have more positions means you need to prove there are "more" digits than there are in the infinite identity matrix. By "more", I mean positions that were not used in the diagonal of the infinite identity matrix which isn't possible. And since all binary strings can be created using a combination of those rows (binary OR operation if you will), what position isn't in use already?

This really confuses me and it may be why we do not understand each other. I don't know what relevance an "infinite identity matrix" has and why I would need any additional positions at all. Since we are assuming (to reach a contradiction) that the reals are countable and since each real has an countably infinite number of decimal places, why do we need more than a countable number of positions?