Hilbert's Paradox and Cantor's Diagonal Proof
Post Reply
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
03-09-2012, 08:43 AM
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(02-09-2012 10:06 PM)Chas Wrote:  Here is another explanation, and another.

Thanks for links.

Sadly, and I hate to admit this but I don't understand the terminology and every link (within the link) that is supposed to lead to a definition of a term just takes me to more terms I don't understand.

Weeping

I haven't even worked out where the word "diagonal" means anything... very frustrating.

But I can perfectly easily follow Starcrash's explanation because that's the way I visualise it too.

Sigh!

Find all posts by this user
Like Post Quote this message in a reply
03-09-2012, 09:20 AM
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(02-09-2012 04:10 PM)Starcrash Wrote:  You're wrong, Chas. You're wrong, HouseofCantor. Suck it up and move on.

The only thing I get right is my Gwynnies. Heart

I only act like I know wtf I'm talking about.

[Image: klingon_zps7e68578a.jpg]
Visit this user's website Find all posts by this user
Like Post Quote this message in a reply
[+] 1 user Likes houseofcantor's post
03-09-2012, 09:33 AM
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(03-09-2012 08:25 AM)Starcrash Wrote:  
(02-09-2012 10:06 PM)Chas Wrote:  That's an ad hominem? Really?

You don't understand the diagonal proof. I will be happy to help you, and tried with pointing out a flaw in your explanation - that you didn't understand the nature of the rationals and irrationals in the list.

Here is another explanation, and another.

I do understand the diagonal proof. I mentioned that you could do it with integers, too... all you have to do is remove the decimal point, and I think you'd have to go diagonally left instead of right. Why wouldn't you be able to do this? Again, when comparing these sets, there's a tendency to treat the real numbers as infinitely trailing sets but we keep treating integers as finite. They're able to go as far left as real numbers can go right.

You are missing the whole basis of the diagonal method.

It's not about integers, it's about real numbers. It's about comparing the cardinality of the natural numbers to that of the real numbers. The list is a list of real numbers, not integers. The integers are labels.

The index of a number in the list is an integer, and we have placed the list of real numbers in a one-to-one correspondence (mapping) with the natural numbers. We then construct a new real number (the diagonal) that is not in the list.
There is no natural number that corresponds to this newly constructed real number, so the number of real numbers between 0 and 1 is greater than the number of natural numbers.

And we can continue to construct real numbers that aren't in the list. Forever. Instead of starting with a difference in the first decimal place, start in the second decimal place, and so on.

Skepticism is not a position; it is an approach to claims.
Science is not a subject, but a method.
[Image: flagstiny%206.gif]
Visit this user's website Find all posts by this user
Like Post Quote this message in a reply
03-09-2012, 10:20 AM
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(03-09-2012 09:33 AM)Chas Wrote:  
(03-09-2012 08:25 AM)Starcrash Wrote:  I do understand the diagonal proof. I mentioned that you could do it with integers, too... all you have to do is remove the decimal point, and I think you'd have to go diagonally left instead of right. Why wouldn't you be able to do this? Again, when comparing these sets, there's a tendency to treat the real numbers as infinitely trailing sets but we keep treating integers as finite. They're able to go as far left as real numbers can go right.

You are missing the whole basis of the diagonal method.

It's not about integers, it's about real numbers. It's about comparing the cardinality of the natural numbers to that of the real numbers. The list is a list of real numbers, not integers. The integers are labels.

The index of a number in the list is an integer, and we have placed the list of real numbers in a one-to-one correspondence (mapping) with the natural numbers. We then construct a new real number (the diagonal) that is not in the list.
There is no natural number that corresponds to this newly constructed real number, so the number of real numbers between 0 and 1 is greater than the number of natural numbers.

And we can continue to construct real numbers that aren't in the list. Forever. Instead of starting with a difference in the first decimal place, start in the second decimal place, and so on.

I told you that I understand it. I did, I still do, and I'll continue to understand it. Have you considered what would happen if you did it with the integers? It's entirely possible... like I said, just remove the decimal point and you're doing it. Or do it from top left to bottom right away from the decimal point.

Supposedly you'll come up with "new" numbers that aren't on the list, but there's no way to prove that unless you know exactly what numbers are on the list. Consider the following:

5 2 3 8 1
6 2 9 0 1
4 2 3 7 6
3 0 9 8 5
1 5 7 0 1

Now if you draw a diagonal from the top left to the bottom right, you'll get a number that is already among the set. There's no reason why coming up with numbers from diagonals can't produce numbers that you produced from an ordered list. And even if you could add that number into the set a second time, drawing a diagonal down from the 6 into the "new" number still doesn't necessarily create a "new" number (in this case, it doesn't yet again).

Now you'll say "but we're talking about numbers that run infinitely off to the right". Those numbers can still find matches in my method with numbers that run infinitely off to the left. There's no number that you'll create with this diagonal system that will not already be among the matched sets, even if you tag it on to the bottom of the list. And more importantly, if you apply the same rules to integers you'll find the exact same results... no "new" numbers get created, because the diagonal system only finds numbers that we hadn't already thought of.

Give me an example of numbers created this way, and I'll show you a mirror image of the same set of numbers creating its match. Integers have "cardinality" as well, we just refer to them as "places" instead (such as "tens place"). There's absolutely no reason why this method can't be used both ways, and when used the other way, we see why it doesn't work to create anything new.


Also, as a note about .9 repeating, I ran it by a math buddy and he pointed out the obvious flaw that I should have caught.... because .9 repeating = 1, it is not a real number between 0 and 1... it is 1.

My girlfriend is mad at me. Perhaps I shouldn't have tried cooking a stick in her non-stick pan.
Visit this user's website Find all posts by this user
Like Post Quote this message in a reply
03-09-2012, 11:15 AM (This post was last modified: 03-09-2012 11:44 AM by Chas.)
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(03-09-2012 10:20 AM)Starcrash Wrote:  
(03-09-2012 09:33 AM)Chas Wrote:  You are missing the whole basis of the diagonal method.

It's not about integers, it's about real numbers. It's about comparing the cardinality of the natural numbers to that of the real numbers. The list is a list of real numbers, not integers. The integers are labels.

The index of a number in the list is an integer, and we have placed the list of real numbers in a one-to-one correspondence (mapping) with the natural numbers. We then construct a new real number (the diagonal) that is not in the list.
There is no natural number that corresponds to this newly constructed real number, so the number of real numbers between 0 and 1 is greater than the number of natural numbers.

And we can continue to construct real numbers that aren't in the list. Forever. Instead of starting with a difference in the first decimal place, start in the second decimal place, and so on.

I told you that I understand it. I did, I still do, and I'll continue to understand it. Have you considered what would happen if you did it with the integers? It's entirely possible... like I said, just remove the decimal point and you're doing it. Or do it from top left to bottom right away from the decimal point.

But why? What is it you are trying to demonstrate?

Quote:Supposedly you'll come up with "new" numbers that aren't on the list, but there's no way to prove that unless you know exactly what numbers are on the list.

No, you won't come up with new numbers, because all of the integers are already on the list. The method doesn't apply.

Quote:Consider the following:

5 2 3 8 1
6 2 9 0 1
4 2 3 7 6
3 0 9 8 5
1 5 7 0 1

Now if you draw a diagonal from the top left to the bottom right, you'll get a number that is already among the set. There's no reason why coming up with numbers from diagonals can't produce numbers that you produced from an ordered list. And even if you could add that number into the set a second time, drawing a diagonal down from the 6 into the "new" number still doesn't necessarily create a "new" number (in this case, it doesn't yet again).

Now you'll say "but we're talking about numbers that run infinitely off to the right". Those numbers can still find matches in my method with numbers that run infinitely off to the left. There's no number that you'll create with this diagonal system that will not already be among the matched sets, even if you tag it on to the bottom of the list. And more importantly, if you apply the same rules to integers you'll find the exact same results... no "new" numbers get created, because the diagonal system only finds numbers that we hadn't already thought of.

Give me an example of numbers created this way, and I'll show you a mirror image of the same set of numbers creating its match. Integers have "cardinality" as well, we just refer to them as "places" instead (such as "tens place"). There's absolutely no reason why this method can't be used both ways, and when used the other way, we see why it doesn't work to create anything new.


Also, as a note about .9 repeating, I ran it by a math buddy and he pointed out the obvious flaw that I should have caught.... because .9 repeating = 1, it is not a real number between 0 and 1... it is 1.

The same proof applies.

x = 0.09999...
10x = 0.9999...
9x = 0.9
x = 0.1
0.1 = 0.09999...


Maybe what you are missing is that the diagonal proof is RAA - reductio ad absurdum.
We assume that all of the reals between 0 and 1 are listed.
We assume a one-to-one mapping of the natural numbers to the members of this set.
We then construct a real number that is not, can not, be on the list.
Therefore, not all of the reals between zero and one are on the list, therefore no mapping exists, and the cardinality of the reals is greater than of the natural numbers.

Skepticism is not a position; it is an approach to claims.
Science is not a subject, but a method.
[Image: flagstiny%206.gif]
Visit this user's website Find all posts by this user
Like Post Quote this message in a reply
03-09-2012, 01:17 PM
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(03-09-2012 11:15 AM)Chas Wrote:  
(03-09-2012 10:20 AM)Starcrash Wrote:  I told you that I understand it. I did, I still do, and I'll continue to understand it. Have you considered what would happen if you did it with the integers? It's entirely possible... like I said, just remove the decimal point and you're doing it. Or do it from top left to bottom right away from the decimal point.

But why? What is it you are trying to demonstrate?

Quote:Supposedly you'll come up with "new" numbers that aren't on the list, but there's no way to prove that unless you know exactly what numbers are on the list.

No, you won't come up with new numbers, because all of the integers are already on the list. The method doesn't apply.

Quote:Consider the following:

5 2 3 8 1
6 2 9 0 1
4 2 3 7 6
3 0 9 8 5
1 5 7 0 1

Now if you draw a diagonal from the top left to the bottom right, you'll get a number that is already among the set. There's no reason why coming up with numbers from diagonals can't produce numbers that you produced from an ordered list. And even if you could add that number into the set a second time, drawing a diagonal down from the 6 into the "new" number still doesn't necessarily create a "new" number (in this case, it doesn't yet again).

Now you'll say "but we're talking about numbers that run infinitely off to the right". Those numbers can still find matches in my method with numbers that run infinitely off to the left. There's no number that you'll create with this diagonal system that will not already be among the matched sets, even if you tag it on to the bottom of the list. And more importantly, if you apply the same rules to integers you'll find the exact same results... no "new" numbers get created, because the diagonal system only finds numbers that we hadn't already thought of.

Give me an example of numbers created this way, and I'll show you a mirror image of the same set of numbers creating its match. Integers have "cardinality" as well, we just refer to them as "places" instead (such as "tens place"). There's absolutely no reason why this method can't be used both ways, and when used the other way, we see why it doesn't work to create anything new.


Also, as a note about .9 repeating, I ran it by a math buddy and he pointed out the obvious flaw that I should have caught.... because .9 repeating = 1, it is not a real number between 0 and 1... it is 1.

The same proof applies.

x = 0.09999...
10x = 0.9999...
9x = 0.9
x = 0.1
0.1 = 0.09999...


Maybe what you are missing is that the diagonal proof is RAA - reductio ad absurdum.
We assume that all of the reals between 0 and 1 are listed.
We assume a one-to-one mapping of the natural numbers to the members of this set.
We then construct a real number that is not, can not, be on the list.
Therefore, not all of the reals between zero and one are on the list, therefore no mapping exists, and the cardinality of the reals is greater than of the natural numbers.

0.1 is not an integer. The division is not part of the rules of my method. But you can screw up any mapping this way. 847 matches to .748, but when you divide them both by 10 you get 84.7 = .0748. It's not that the matching fails, but that you're no longer matching integers. When you go back to matching integers, you get the result I displayed. Please, stop doing dishonest math with the equations to try to prove a nonexistent point.

Your further assertion that all the natural numbers are used up is exactly what I disproved with 1-to-1 mapping. If you use up all the numbers in one set, you've used them up in the other. You're right, an assumption is being made that there are still numbers that haven't been used up. Stop making that false assumption. Calling it "constructing" a real number that hasn't been used up doesn't make it a new construction. You still have to demonstrate that it hasn't been mapped, and I've demonstrated exactly the opposite.

My girlfriend is mad at me. Perhaps I shouldn't have tried cooking a stick in her non-stick pan.
Visit this user's website Find all posts by this user
Like Post Quote this message in a reply
03-09-2012, 01:32 PM
RE: Hilbert's Paradox and Cantor's Diagonal Proof
You should get your hypothesis peer-reviewed, Starcrash. I'm far from being good enough at math to have a discussion about it, but when you're so confident that your claims are true, you should publish them to a wider audience.

[Image: 7oDSbD4.gif]
Find all posts by this user
Like Post Quote this message in a reply
[+] 1 user Likes Vosur's post
03-09-2012, 02:04 PM
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(03-09-2012 01:17 PM)Starcrash Wrote:  
(03-09-2012 11:15 AM)Chas Wrote:  But why? What is it you are trying to demonstrate?


No, you won't come up with new numbers, because all of the integers are already on the list. The method doesn't apply.


The same proof applies.

x = 0.09999...
10x = 0.9999...
9x = 0.9
x = 0.1
0.1 = 0.09999...


Maybe what you are missing is that the diagonal proof is RAA - reductio ad absurdum.
We assume that all of the reals between 0 and 1 are listed.
We assume a one-to-one mapping of the natural numbers to the members of this set.
We then construct a real number that is not, can not, be on the list.
Therefore, not all of the reals between zero and one are on the list, therefore no mapping exists, and the cardinality of the reals is greater than of the natural numbers.

0.1 is not an integer. The division is not part of the rules of my method. But you can screw up any mapping this way. 847 matches to .748, but when you divide them both by 10 you get 84.7 = .0748. It's not that the matching fails, but that you're no longer matching integers. When you go back to matching integers, you get the result I displayed. Please, stop doing dishonest math with the equations to try to prove a nonexistent point.

Your further assertion that all the natural numbers are used up is exactly what I disproved with 1-to-1 mapping. If you use up all the numbers in one set, you've used them up in the other. You're right, an assumption is being made that there are still numbers that haven't been used up. Stop making that false assumption. Calling it "constructing" a real number that hasn't been used up doesn't make it a new construction. You still have to demonstrate that it hasn't been mapped, and I've demonstrated exactly the opposite.

It's not a constructive proof, it's RAA.
It is assumed that the natural numbers map, one-to-one, to the real numbers between 0 and 1. From those assumptions, we derive a contradiction. Therefore the assumption that the naturals can map to the reals is proven false.

I have no idea what you are trying to do with mapping integers to integers. That is not part of the proof.

Skepticism is not a position; it is an approach to claims.
Science is not a subject, but a method.
[Image: flagstiny%206.gif]
Visit this user's website Find all posts by this user
Like Post Quote this message in a reply
[+] 1 user Likes Chas's post
03-09-2012, 02:14 PM (This post was last modified: 03-09-2012 02:22 PM by GirlyMan.)
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(02-09-2012 10:06 PM)Chas Wrote:  You don't understand the diagonal proof. I will be happy to help you, and tried with pointing out a flaw in your explanation - that you didn't understand the nature of the rationals and irrationals in the list.

Here is another explanation, and another.

Chas' latter link directly addresses your objection Starcrash. It shows that you can indeed demonstrate a bijection from the set of rational numbers to the set of natural numbers and hence rational numbers are countable. But not all real numbers are rational. To my mind the discourse in that link accurately reflects the discussion between you and Chas and I agree with Salviati's response to Simplicio:

"Overall, it sounds like you're trying to define a class of numbers that includes the rationals plus all the irrational magnitudes that have some acceptably simple definition. You would then call this overall set 'the real numbers', and assert that Cantor's diagonal argument does not apply (because any acceptably simple definition is presumably one of at most a countably infinite set of definitions). You would be right in asserting that your set of numbers has the same cardinality as the integers, but I think you would be better advised not to call them 'the real numbers', so as to avoid confusion with a set that has previously been postulated by other people on somewhat different premises. Think of a new name for your set of numbers, and call yourself a constructivist, and most of your critics will leave you alone."

(03-09-2012 02:04 PM)Chas Wrote:  It's not a constructive proof, it's RAA.
It is assumed that the natural numbers map, one-to-one, to the real numbers between 0 and 1. From those assumptions, we derive a contradiction. Therefore the assumption that the naturals can map to the reals is proven false.

That's right.

As it was in the beginning is now and ever shall be, world without end. Amen.
And I will show you something different from either
Your shadow at morning striding behind you
Or your shadow at evening rising to meet you;
I will show you fear in a handful of dust.
Find all posts by this user
Like Post Quote this message in a reply
04-09-2012, 04:00 PM (This post was last modified: 04-09-2012 04:07 PM by GirlyMan.)
RE: Hilbert's Paradox and Cantor's Diagonal Proof
(03-09-2012 08:43 AM)DLJ Wrote:  Sadly, and I hate to admit this but I don't understand the terminology and every link (within the link) that is supposed to lead to a definition of a term just takes me to more terms I don't understand.

Weeping

I haven't even worked out where the word "diagonal" means anything... very frustrating.

This is an excellent article for gaining an intuition on the "diagonalization" aspect. (pssst ... don't tell Chas I'm stealing from the NY Times again). Wink


(03-09-2012 08:43 AM)DLJ Wrote:  But I can perfectly easily follow Starcrash's explanation because that's the way I visualise it too.

Sigh!

Starcrash is just failing to appreciate that this is not a constructive proof but rather a proof by contradiction as Chas points out. The only 2 reasonable ways I can see to counter Cantor's argument is to either reject proofs by contradiction (i.e., constructivism) or reject the premise of infinity.

Other fun facts. We not only know that the cardinality of the set of real numbers is larger than the set of natural numbers, we know what it is. It's equal to the cardinality of the power set of the natural numbers (the set of all subsets of natural numbers). Which is 2 raised to the power of the size of the set of natural numbers (aka Chas' avatar aleph-naught) or aleph-one.

Well why stop there you might ask? Why indeed. What about the set of all subsets of real numbers? The cardinality of that set is 2 raised to the aleph-one power or aleph-two. And so on for well, forever.

Infinity is a mind fuck. Big Grin

As it was in the beginning is now and ever shall be, world without end. Amen.
And I will show you something different from either
Your shadow at morning striding behind you
Or your shadow at evening rising to meet you;
I will show you fear in a handful of dust.
Find all posts by this user
Like Post Quote this message in a reply
Post Reply
Forum Jump: