Regarding Cantor's diagonal proof

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