I Regarding Cantor's diagonal proof

[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?

 

[Mark44]

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?

@AlienRenders, your mistake is that you are fixating on an infinite identity matrix, which has only a countably infinite number of rows, so the numbers represented in the rows of this identity matrix map one-to-one to the positive integers. In contrast, Cantor's list contains real numbers, and the whole point of the diagonal proof is to show that the set of real numbers is uncountably infinite, making the set of real numbers larger than the set of postivie integers.

 

[AlienRenders]

It's simple. If there exists a row from the identity matrix for each digit and all other rows of N can be constructed from combining these rows (binary OR operation), then there are no more digits remaining to construct the diagonal for the rest of my list. End of story. The assumption that the digits of N when written out as binary strings maps one to one with the rows is false. Unless there is a proof of this, Cantor's diagonal cannot be constructed.

@Mark44: You don't understand. Cantor's diagonal can't even get to N, much less Q, much less R. He can only get to a subset of N (which is also N), but regardless... He's using this limitation to show that |subset of N| is always < |R|. What I'm showing is that this is also showing |N| < |N| which is fatal to the proof.

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$.

The flaw is that you're using the same index for two positions that are not one to one. It makes it very easy to gloss over the flaw when you do this. What you have is f(n, x, y) where n is your number, x is the digit position and y is the row of n. You are claiming to use this when x=y. I'm saying that this is not possible because x and y are not one to one.

If there exists all the rows of the infinite identity matrix in my list, and they must, then all digits have been accounted for. But these are not all my rows.

What you all don't seem to understand is WHERE the new number comes from. It doesn't come from using up all N rows. It comes from using up a SUBSET of N rows. This is fatal. If Cantor's proof only used every second row, it would be trivial to show this doesn't work, correct? Well, that's all I'm trying to show. That Cantor's diagonal does not use the whole list.

To make it even easier to explain, I'm saying that Cantor's proof is using base 3 numbers not found in base 2 numbers to prove that |N base 2| < |N base 3|. We all know that it is not valid to compare bases like this. Yet Cantor does the exact same thing except he's using the identity matrix and base 2. I'll use I for identity matrix. So he's using |I| < |R|. The problem is that his proof also shows |I| < |N| and that's fatal.

The identity matrix is a restricted form of writing out N the same way base 2 is a restricted form of writing N compared to base 3. There are numbers in base 3 that do not appear in base 2 in the same way there are number in base 2 that do not appear in I when comparing digit by digit. But since I has never been called base 1 or whatever, then people have glossed over it. But it IS a restricted form, is it not? The identity matrix does have N rows and N digits, does it not? But it does not contain all base 2 numbers when comparing digit by digit, correct? So why is this technique accepted?

All the numbers in base 2 exist in base 3 when comparing digit by digit, does that mean |N in base 3| > |N in base 2|? Of course not.
All the numbers in the Identity matrix exist in base 2 when comparing digit by digit, does that mean |N in base 2| > |I|? Of course not. This last one is fatal to Cantor's diagonal because that's the technique he's using. This is where the new number comes from.

 

[FactChecker]

@AlienRenders ,Is there something in my post #54 that can not be continued to countably infinite? If so, please point it out specifically and state where it must stop and why, in concrete terms. Otherwise, I must continue to believe that it can be continued to countably infinity and that Cantor's proof is valid.

 

[AlienRenders]

@FactChecker That's an extremely weak argument. The rows and digits are not one to one. You must prove that they are before Cantor's diagonal proof can work. Countably infinite is not enough otherwise you could prove that |N in base 2| < |N in base 3| by showing that there are numbers in base 3 that don't exist in base 2 when comparing by digit.

So far, the only argument has been to not look at the flaw. That's simply not realistic.

Here's another way to answer your question. How many rows from the identity matrix is in an enumeration of N in base 2 when comparing digit by digit? There are countably infinitely many of them, correct? Yet, this is not my entire list.

 

[stevendaryl]

The flaw is that you're using the same index for two positions that are not one to one. It makes it very easy to gloss over the flaw when you do this. What you have is f(n, x, y) where n is your number, x is the digit position and y is the row of n. You are claiming to use this when x=y. I'm saying that this is not possible because x and y are not one to one.

You're using words as if you know what they mean, but you clearly don't. What do you think it means to say "x and y are not one to one"? It doesn't mean anything.

A function is said to be one-to-one if two different values of the input produce two different values of the output. So for example, the function $f(x) = x+1$ is one-to-one, because if $x_1 \neq x_2$, then $f(x_1) \neq f(x_2)$. On the other hand, the function $f(x) = x \cdot x$ is not one-to-one, because $f(+1) = f(-1)$.

It doesn't mean anything to say that two variables are not one-to-one.

Why don't you say what you mean with a particular case, which is the real number $\pi$. Corresponding to the real number $\pi$ is a corresponding function $f$ from the integers to the digits $0, ... , 9$. $f(n)$ gives the $n^{th}$ decimal place of $\pi$ (using decimal place number 0 as the 1s place, decimal place number 1 as the tenths place, etc.)

$f(0) = 3$
$f(1) = 1$
$f(2) = 4$
etc.

I don't know what you are talking about when you introduce extra arguments, $f(n, x, y)$. Do you understand that nonnegative real number is associated with a function from integers to $\{ 0, 1, ... 9 \}$? There is nothing in this concept that involves "rows".

 

[Klystron]

String manipulation aside how are different number bases relevant? Proof constructs a matrix of real numbers.

Also, in the posts using functions to cover Cantor's proof, the function g(x,y) returns n. Adding arguments is not necessary.

 

[stevendaryl]

@FactChecker That's an extremely weak argument. The rows and digits are not one to one. You must prove that they are before Cantor's diagonal proof can work. Countably infinite is not enough otherwise you could prove that |N in base 2| < |N in base 3| by showing that there are numbers in base 3 that don't exist in base 2 when comparing by digit.

So far, the only argument has been to not look at the flaw. That's simply not realistic.

What in the world do you mean by "countably infinite"? Cantor is the one who introduced that term, and his proof is the reason that we know that something can be infinite but not countably infinite. If you don't accept Cantor's proof, then it makes no sense for you to bring up something being not countably infinite, unless you have an alternative proof.

 

[AlienRenders]

What in the world do you mean by "countably infinite"?

That wasn't my term.

If you don't accept Cantor's proof, then it makes no sense for you to bring up something being not countably infinite, unless you have an alternative proof.

I never said something was not countably infinity. Nice of you to jump in so aggressively though.

 

[stevendaryl]

This discussion is completely fruitless. @AlienRenders doesn't seem to know what he's talking about. I should put that more strongly: He doesn't know what he's talking about. He is very confused about Cantor's proof, but rather than attempting to understand it, he thinks of himself as competent to show it wrong. This might sound boring, but Physics Forums is the place to go to understand mainstream mathematics and science, not to overturn it. Cantor's arguments are very thoroughly mainstream---they are the foundation of pretty much all advanced mathematics for the last 100 years or so. If they are going to be overturned by some brilliant new way of thinking, Physics Forums is not the place for that. I'm going to request that this thread be closed.

 

[AlienRenders]

What do you think it means to say "x and y are not one to one"? It doesn't mean anything.

Of course it does. You are grabbing a digit x from a row y. The digits and rows are two different sets. My apologies for not adding g(n, x) and h(n, y). These sets are not one to one. Please stop the trite aggressive statements please. They don't help. You didn't add a function either. So there.

The rest of your comment is nonsense. You're still conflating two sets.

 

[AlienRenders]

This discussion is completely fruitless. @AlienRenders doesn't seem to know what he's talking about. I should put that more strongly: He doesn't know what he's talking about. He is very confused about Cantor's proof, but rather than attempting to understand it, he thinks of himself as competent to show it wrong. This might sound boring, but Physics Forums is the place to go to understand mainstream mathematics and science, not to overturn it. Cantor's arguments are very thoroughly mainstream---they are the foundation of pretty much all advanced mathematics for the last 100 years or so. If they are going to be overturned by some brilliant new way of thinking, Physics Forums is not the place for that. I'm going to request that this thread be closed.

So because you get completely destroyed in your arguments, you resort to appeals to authority?

 

[stevendaryl]

So because you get completely destroyed in your arguments, you resort to appeals to authority?

Physics Forums is about mainstream mathematics and science. Mainstream mathematics and science can certainly be wrong, but THIS is not the place to overturn it.

 

[AlienRenders]

Physics Forums is about mainstream mathematics and science. Mainstream mathematics and science can certainly be wrong, but THIS is not the place to overturn it.

Fair enough. I was just looking for the proof that the digits and rows were one to one. If that proof doesn't exist, then so be it. I'm satisfied that Cantor's proof is incomplete.

 

[stevendaryl]

Fair enough. I was just looking for the proof that the digits and rows were one to one. If that proof doesn't exist, then so be it. I'm satisfied that Cantor's proof is incomplete.

I think you are extremely confused. Digits and rows of WHAT? Cantor's proof is a proof by contradiction: You ASSUME that there are as many real numbers as there are digits in a single real number, and then you show that that leads to a contradiction. You want a proof of something that Cantor proves was false.

 

[FactChecker]

@FactChecker That's an extremely weak argument. The rows and digits are not one to one.

What? That is just obviously wrong. I will leave this discussion to others.

 

[AlienRenders]

I think you are extremely confused. Digits and rows of WHAT? Cantor's proof is a proof by contradiction: You ASSUME that there are as many real numbers as there are digits in a single real number, and then you show that that leads to a contradiction. You want a proof of something that Cantor proves was false.

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?

 

[AlienRenders]

What? That is just obviously wrong. I will leave this discussion to others.

Let me ask you this. How many rows in my list match a row in the infinite identity matrix when comparing digit by digit? Yet, this is not my entire list.

 

[stevendaryl]

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

It's a proof by contradiction. You assume something, then you show that that leads to a contradiction. That proves that the assumption is false.

The assumption that Cantor started with was that there are as many real numbers as there are digits in a single real number. He proved that that is false.

Now you seem to be agreeing with Cantor's conclusion.

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.

You are very confused. A real number has as many digits as there are natural numbers. Every real number $r \geq 0$ can be represented by the form:

$r = K + \sum_{n=0}^{\infty} r_n$

where $r_n$ is the $n^{th}$ digit of $r$ and $K$ is the integer part of $r$. That notation assumes that there is exactly one digit of $r$ for every natural number $n$.

 

[AlienRenders]

@stevendaryl You're ignoring what I'm saying and throwing insults. I'll ask my same question again.

How many rows in my list match a row in the infinite identity matrix when comparing digit by digit?

That's all of the rows from the identity matrix. There are infinitely many of them. They are even N of them. But it is not the entirety of MY list. This does not mean that |N| > |N|. But for some reason, it's enough to prove that |R| > |N|. That's nonsense.

I'm not going to quote your comment because you're still using two different sets that don't have a bijection.

 

[stevendaryl]

I'm not going to quote your comment because you're still using two different sets that don't have a bijection.

What do you think a real number is? What do you think a "decimal expansion" means? You are confused about the most basic concepts of mathematics.

Have you never learned how to represent a real number as an infinite sum?

 

[AlienRenders]

@stevendaryl You're again using the same variable n to index into two sets that don't have a bijection. You're just avoiding the issue now.

 

[AlienRenders]

How many rows in my list match a row in the infinite identity matrix when comparing digit by digit?
Are there not infinitely many?
Yet it is not my entire list N which consists of only strings in base 2.

How can this be if there is a bijection between the rows and digits of my list?

Just answer these questions.

 

[stevendaryl]

Do you really not understand how to compute the $n^{th}$ decimal of a real number, when $n$ is any nonnegative integer?

 

[stevendaryl]

How many rows in my list match a row in the infinite identity matrix when comparing digit by digit?
Are there not infinitely many?
Yet it is not my entire list N which consists of only strings in base 2.

How can this be if there is a bijection between the rows and digits of my list?

Just answer these questions.

You don't understand the very basics. Your questions are not relevant until you understand the basics.

 

[stevendaryl]

If $r$ is a real number greater than or equal to 0, then let's define $floor(r)$ to be the largest integer that is less than or equal to $r$. Now, we define the ones place of $r$ to be:

$ones(r) = floor(r) - floor(r/10) \cdot 10$

Then we can define the $n^{th}$ place of $r$ via:

$r_n = ones(r \cdot 10^n)$

That's a map from the naturals $n$ to the digits of $r$.

 

[FactChecker]

This thread needs to be closed. It is a waist of time, energy, and expertise.

 

[fresh_42]

This thread needs to be closed. It is a waist of time, energy, and expertise.

This thread is obviously running in - unpleasant - circles. There is nothing wrong with Cantor's argument.
It seems as if there is no common basis for a discussion anymore and we had to delete a couple of post which became personal.

Thread closed.