I Regarding Cantor's diagonal proof

  • Thread starter Thread starter ATAUD
  • Start date Start date
  • Tags Tags
    Proof
Click For Summary
Cantor's diagonal proof demonstrates that the set of real numbers cannot be listed in a complete sequence, as it allows for the construction of a new number that differs from every number in the list. The diagonal method modifies each digit of the diagonal entries to create a number not included in the original list, proving that the list was incomplete. This leads to the conclusion that there are more real numbers than natural numbers, establishing that the cardinality of the reals (##\aleph##1) is greater than that of the naturals (##\aleph##0). The discussion also touches on the misunderstanding of infinity, emphasizing that adding or altering numbers within an infinite list does not yield a new infinity but rather a distinct number outside the original list. Ultimately, the proof illustrates the uncountability of real numbers and the limitations of attempting to list infinite sets.
  • #61
AlienRenders said:
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.
 
  • Like
Likes FactChecker
Physics news on Phys.org
  • #62
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.

stevendaryl said:
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.
 
Last edited:
  • #63
@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.
 
  • #64
@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.
 
Last edited:
  • #65
AlienRenders said:
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".
 
  • #66
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.
 
  • #67
AlienRenders said:
@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.
 
  • Like
Likes FactChecker
  • #68
stevendaryl said:
What in the world do you mean by "countably infinite"?

That wasn't my term.

stevendaryl said:
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.
 
  • #69
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.
 
  • #70
stevendaryl said:
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.
 
  • #71
stevendaryl said:
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?
 
  • #72
AlienRenders said:
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.
 
  • #73
stevendaryl said:
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.
 
  • #74
AlienRenders said:
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.
 
  • #75
AlienRenders said:
@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.
 
  • #76
stevendaryl said:
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?
 
  • #77
FactChecker said:
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.
 
  • #78
AlienRenders said:
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##.
 
  • #79
@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.
 
  • #80
AlienRenders said:
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?
 
  • #81
@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.
 
  • #82
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.
 
  • #83
Do you really not understand how to compute the ##n^{th}## decimal of a real number, when ##n## is any nonnegative integer?
 
  • #84
AlienRenders said:
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.
 
  • #85
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##.
 
  • #86
This thread needs to be closed. It is a waist of time, energy, and expertise.
 
  • #87
FactChecker said:
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.
 
  • Like
Likes Klystron and FactChecker

Similar threads

B I have an issue with Cantor's diagonal argument
  • · Replies 6 ·
Replies
6
Views
2K
B Another consequence of Cantor's diagonal argument
  • · Replies 43 ·
2
Replies
43
Views
5K
I Cantor's diagonalization on the rationals
  • · Replies 25 ·
Replies
25
Views
3K
B One thing I don't understand about Cantor's diagonal argument
  • · Replies 55 ·
2
Replies
55
Views
8K
B Is this a finite argument of the countable infiniteness of the rationals?
  • · Replies 21 ·
Replies
21
Views
3K
I Add an exponential number of elements, what will be the final cardinality?
  • · Replies 16 ·
Replies
16
Views
2K
I Understanding Cantor's Diagonalization Proof: A Brief Explanation
  • · Replies 17 ·
Replies
17
Views
3K
MHB Is Cantor's second diagonal proof valid?
  • · Replies 6 ·
Replies
6
Views
3K
I Countability of binary Strings
  • · Replies 18 ·
Replies
18
Views
2K
I Countably Infinite Unions and the Real Numbers: Can They Really Be Uncountable?
  • · Replies 4 ·
Replies
4
Views
2K