More Fun With Infinity
-
- Posts: 10000
- Joined: Sun Jun 06, 2004 4:09 pm
- Location: Earning my avatar in the rain
More Fun With Infinity
OK, this one is a little tougher and mind blowing than .999.... = 1. Non-mathematicians are certainly welcome, but I'll caution you that this one is a little tougher to grasp. I might say "don't try this at home."
Since I am HTML illiterate, I will use different symbols to denote what should be the proper and conventional mathematical symbols in this discussion.
Remember our old friend Aleph Naught? Let's denote it as "X0" which is as close as I can get to displaying it properly.
Definition 1:
X0 is the set of all rational numbers, which is of course an unbounded set (infinitely large). It is referred to as a transfinite number. The following two sets defined are also transfinite.
Definition 2:
X1 is the smallest infinite set > X0, and = the cardinality of the set of countable ordinal numbers (also unbounded).
Definition 3:
C (also known as the Continuum) is the set of all irrational numbers, again an unbounded set.
Axiom 1:
The cardinality (the number of) of rational numbers (X0) = the cardinality of integers (also an unbounded set).
Axiom 2:
The cardinality of irrational numbers (C) = the cardinality of real numbers (again, an unbounded set).
Conclusion:
Thus, we know that C > X0. If fact, C = 2 Xo (I mean this to be 2 to the X0 power, but I don't know how to write superscripts.)
Thus, this is one way of stating that there are different sizes, or levels if you prefer, of infinity. (I prefer to use set theory to think about it).
********************************************
Georg Cantor came up with an interesting hypothesis for set theory. It is known as the Continuum Hypothesis and is written as:
C = X1
Question:
Does anyone know how to prove the Continuum Hypothesis? (Kurt Godel) How to disprove it? (Paul Cohen)
Decide, discuss, have fun.
Cool Hand
Since I am HTML illiterate, I will use different symbols to denote what should be the proper and conventional mathematical symbols in this discussion.
Remember our old friend Aleph Naught? Let's denote it as "X0" which is as close as I can get to displaying it properly.
Definition 1:
X0 is the set of all rational numbers, which is of course an unbounded set (infinitely large). It is referred to as a transfinite number. The following two sets defined are also transfinite.
Definition 2:
X1 is the smallest infinite set > X0, and = the cardinality of the set of countable ordinal numbers (also unbounded).
Definition 3:
C (also known as the Continuum) is the set of all irrational numbers, again an unbounded set.
Axiom 1:
The cardinality (the number of) of rational numbers (X0) = the cardinality of integers (also an unbounded set).
Axiom 2:
The cardinality of irrational numbers (C) = the cardinality of real numbers (again, an unbounded set).
Conclusion:
Thus, we know that C > X0. If fact, C = 2 Xo (I mean this to be 2 to the X0 power, but I don't know how to write superscripts.)
Thus, this is one way of stating that there are different sizes, or levels if you prefer, of infinity. (I prefer to use set theory to think about it).
********************************************
Georg Cantor came up with an interesting hypothesis for set theory. It is known as the Continuum Hypothesis and is written as:
C = X1
Question:
Does anyone know how to prove the Continuum Hypothesis? (Kurt Godel) How to disprove it? (Paul Cohen)
Decide, discuss, have fun.
Cool Hand
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
Re: More Fun With Infinity
No.Cool Hand wrote:Does anyone know how to prove the Continuum Hypothesis? (Kurt Godel) How to disprove it? (Paul Cohen)
(and about that I am decided...)
;)
-
- Posts: 145
- Joined: Sun Jun 13, 2004 11:43 am
- Location: Caltech
Re: More Fun With Infinity
Hmm. The way I heard it, I was just given C = X1 as a definition. (That is, someone told me, "X0 is the cardinality of the set of the integers (which happens to be the same as the cardinality of the set of rationals), and X1 is the cardinality of the set of the reals (which happens to be the same as the cardinality of the set of the irrationals.)") Apparently, either they were wrong, or there is a trick here that I'm missing. I'm really not getting the "set of countable ordinal numbers." Weren't ordinal numbers the ones with "st," "nd," "rd," or "th" after them? I remember seeing a funny comic in the back of Sci Am or something that showed a picture of two baseball teams: the Cardinals and the Ordinals. The Cardinal's uniforms had numbers like 2, 5, 17, etc., while the Ordinal's uniforms had 3rd, 6th, and 22nd. Anyway, so yea, I'm not entirely familiar with your definition of X1. Could you elaborate?
-
- Posts: 804
- Joined: Fri Jun 04, 2004 11:11 pm
- Location: Starbug 1
So there's this guy who runs the Hotel D'Infinitie, which boasts an infinite number of rooms. A man seeking accomodations for the night rides by the hotel, but sees the NO VACANCY sign lit. Upset, he pulls in and demands to talk to the manager, accusing him of false advertising since he's supposed to have an infinite number of rooms.
The manager politely informs him that, while they do indeed have an infinite number of rooms, they have an infinite number of guests as well.
But the young college girl working at the front desk on her summer job has an idea: They'll inform all of the tenants that they will be moving up a room at precisely 4:00, and they should be packed and ready. At that moment, the person in room 1 will move to room 2, the one in room 2 will move to room 3, etc. Then the man can stay in room 1.
So: infinity + 1 = infinity
The next day, an infinite number of busses pull up and an infinite number of customers pour out of them wanting rooms. In a panic, the manager goes to the college girl again and asks her what to do. She proposes that they do a similar room shift as yesterday, only this time they will move the current tenants into even numbered rooms by telling them to multiply their current room number by 2 to get the room number. So room 1 will go to room 2, room 2 will be room 4, room 3 will be room 6, etc. The new tenants can therefore be placed in the odd-numbered rooms.
So: inifnity + infinity = infinity
(Note: NOT responsible for exploding brains)
The manager politely informs him that, while they do indeed have an infinite number of rooms, they have an infinite number of guests as well.
But the young college girl working at the front desk on her summer job has an idea: They'll inform all of the tenants that they will be moving up a room at precisely 4:00, and they should be packed and ready. At that moment, the person in room 1 will move to room 2, the one in room 2 will move to room 3, etc. Then the man can stay in room 1.
So: infinity + 1 = infinity
The next day, an infinite number of busses pull up and an infinite number of customers pour out of them wanting rooms. In a panic, the manager goes to the college girl again and asks her what to do. She proposes that they do a similar room shift as yesterday, only this time they will move the current tenants into even numbered rooms by telling them to multiply their current room number by 2 to get the room number. So room 1 will go to room 2, room 2 will be room 4, room 3 will be room 6, etc. The new tenants can therefore be placed in the odd-numbered rooms.
So: inifnity + infinity = infinity
(Note: NOT responsible for exploding brains)
-
- Posts: 10000
- Joined: Sun Jun 06, 2004 4:09 pm
- Location: Earning my avatar in the rain
Re: More Fun With Infinity
http://mathworld.wolfram.com/Aleph-1.htmlrwald wrote: Anyway, so yea, I'm not entirely familiar with your definition of X1. Could you elaborate?
Cool Hand
-
- Posts: 34136
- Joined: Sat Jun 05, 2004 2:17 am
- Title: Man in Black
- Location: Division 6
So where's the other dollar?shanek wrote:So there's this guy who runs the Hotel D'Infinitie, which boasts an infinite number of rooms. A man seeking accomodations for the night rides by the hotel, but sees the NO VACANCY sign lit. Upset, he pulls in and demands to talk to the manager, accusing him of false advertising since he's supposed to have an infinite number of rooms.
The manager politely informs him that, while they do indeed have an infinite number of rooms, they have an infinite number of guests as well.
But the young college girl working at the front desk on her summer job has an idea: They'll inform all of the tenants that they will be moving up a room at precisely 4:00, and they should be packed and ready. At that moment, the person in room 1 will move to room 2, the one in room 2 will move to room 3, etc. Then the man can stay in room 1.
So: infinity + 1 = infinity
The next day, an infinite number of busses pull up and an infinite number of customers pour out of them wanting rooms. In a panic, the manager goes to the college girl again and asks her what to do. She proposes that they do a similar room shift as yesterday, only this time they will move the current tenants into even numbered rooms by telling them to multiply their current room number by 2 to get the room number. So room 1 will go to room 2, room 2 will be room 4, room 3 will be room 6, etc. The new tenants can therefore be placed in the odd-numbered rooms.
So: inifnity + infinity = infinity
(Note: NOT responsible for exploding brains)
-
- Posts: 145
- Joined: Sun Jun 13, 2004 11:43 am
- Location: Caltech
Wasn't that Hilbert's Hotel?shanek wrote:So there's this guy who runs the Hotel D'Infinitie, which boasts an infinite number of rooms. A man seeking accomodations for the night rides by the hotel, but sees the NO VACANCY sign lit. Upset, he pulls in and demands to talk to the manager, accusing him of false advertising since he's supposed to have an infinite number of rooms.
The manager politely informs him that, while they do indeed have an infinite number of rooms, they have an infinite number of guests as well.
But the young college girl working at the front desk on her summer job has an idea: They'll inform all of the tenants that they will be moving up a room at precisely 4:00, and they should be packed and ready. At that moment, the person in room 1 will move to room 2, the one in room 2 will move to room 3, etc. Then the man can stay in room 1.
So: infinity + 1 = infinity
The next day, an infinite number of busses pull up and an infinite number of customers pour out of them wanting rooms. In a panic, the manager goes to the college girl again and asks her what to do. She proposes that they do a similar room shift as yesterday, only this time they will move the current tenants into even numbered rooms by telling them to multiply their current room number by 2 to get the room number. So room 1 will go to room 2, room 2 will be room 4, room 3 will be room 6, etc. The new tenants can therefore be placed in the odd-numbered rooms.
So: inifnity + infinity = infinity
(Note: NOT responsible for exploding brains)
And thanks for the link, Cool Hand. I should have looked there before asking.
-
- Posts: 804
- Joined: Fri Jun 04, 2004 11:11 pm
- Location: Starbug 1
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
Interesting that you should bring up this particular topic. Are there any proofs of the uncountability of the reals that do not depend on Cantor's diagonal argument?Cool Hand wrote:Axiom 1:
The cardinality (the number of) of rational numbers (X0) = the cardinality of integers (also an unbounded set).
Axiom 2:
The cardinality of irrational numbers (C) = the cardinality of real numbers (again, an unbounded set).
Conclusion:
Thus, we know that C > X0.
It's certainly difficult to go against 100 years of math, but I am not (yet) convinced that the reals are uncountable. Seems to me there is something fishy about Cantor's diagonal argument, but I have not yet been able to find the hidden assumption. For example, if we assume we have a list of all the irrational numbers, and we apply Cantor's diagonal argument, how do we prove that the resulting number is irrational?
A few months ago, I discovered what seems to be a method that enumerates the reals, but if Cantor is right, then there is a flaw in my method. Unfortunately, I am unable to find it, due to gaps in my math knowledge. I need to study some more. Any recommendations what I should look at?
Second question, what is the cardinality of base 2 p-adics?
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
-
- Posts: 10000
- Joined: Sun Jun 06, 2004 4:09 pm
- Location: Earning my avatar in the rain
Re: More Fun With Infinity
Actually, I think Tez is right, as Godel and Cohen each used rigorous proofs and got opposite results.xouper wrote:Interesting that you should bring up this particular topic. Are there any proofs of the uncountability of the reals that do not depend on Cantor's diagonal argument?Cool Hand wrote:Axiom 1:
The cardinality (the number of) of rational numbers (X0) = the cardinality of integers (also an unbounded set).
Axiom 2:
The cardinality of irrational numbers (C) = the cardinality of real numbers (again, an unbounded set).
Conclusion:
Thus, we know that C > X0.
It's certainly difficult to go against 100 years of math, but I am not (yet) convinced that the reals are uncountable. Seems to me there is something fishy about Cantor's diagonal argument, but I have not yet been able to find the hidden assumption. For example, if we assume we have a list of all the irrational numbers, and we apply Cantor's diagonal argument, how do we prove that the resulting number is irrational?
A few months ago, I discovered what seems to be a method that enumerates the reals, but if Cantor is right, then there is a flaw in my method. Unfortunately, I am unable to find it, due to gaps in my math knowledge. I need to study some more. Any recommendations what I should look at?
Second question, what is the cardinality of base 2 p-adics?
I don't know how to prove that the set of real numbers is unbounded. I simply took it as axiomatic.
Perhaps you could expound on your dissatisfaction with Cantor's diagonal method and others could critique it.
I have no idea what your second question means. I am very rusty with my math and its terminology. I have to refer to my textbooks or google it most of the time. Of course, I know what base 2 is, but what does p-adics mean?
Cool Hand
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Another way to say the same thing is that the set of all odd counting numbers is infinite, the set of all even counting numbers is infinite, and if you take the union of the two sets, you get the set of all counting numbers, which is also infinite. But Hilbert's Hotel is a more dramatic way of saying that.shanek wrote:inifnity + infinity = infinity
Galileo's Paradox was similar. For every positive integer, there exists one and only one square (for example, 3 squared is 9). And for every perfect square, there exists one and only one positive integer root (for example, 25 corresponds to 5). Since there is a bijection between them, the set of perfect squares is the same "size" (or cardinality) as the set of positive integers.
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
For example:Cool Hand wrote:Actually, I think Tez is right, as Godel and Cohen each used rigorous proofs and got opposite results.
http://www.faqs.org/faqs/sci-math-faq/AC/ContinuumHyp/
I mentioned one of them already. But basically any proof by contradiction must have only one assumption, which is proven false by the contradiction. But if there is another assumption hiding in Cantor's diagonal argument, then which assumption has been contradicted? I have this uneasy feeling that there is a hidden assumption in Cantor's diagonal argument, but I do not know what it is or even whether it exists.Perhaps you could expound on your dissatisfaction with Cantor's diagonal method and others could critique it.
See for example:I have no idea what your second question means. ... what does p-adics mean?
http://mathworld.wolfram.com/p-adicNumber.html
An example of a base 2 p-adic (also called 2-adics) is:
<--111.
where there are infinitely many digits to the left of the decimal point.
For those who think 0.999...=1 is strange, then try wrapping your mind around this one:
<--111. = -1
Those who are familiar with two's complement arithmetic will immediately see the beauty of that.
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
Re: More Fun With Infinity
Cohen proved something stronger - basically that there are consistent ("Cantorian") set theories in which the hypothesis is true, and consistent ("non-Cantorian") ones in which it is false. Thus it depends on your axioms, and in this sense is undecidable....Cool Hand wrote:[Actually, I think Tez is right, as Godel and Cohen each used rigorous proofs and got opposite results.
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
This is one direction I need to study more.Tez wrote:Cohen proved something stronger - basically that there are consistent ("Cantorian") set theories in which the hypothesis is true, and consistent ("non-Cantorian") ones in which it is false. Thus it depends on your axioms, and in this sense is undecidable....
For example, what happens if C = Aleph-null?
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
Re: More Fun With Infinity
Sorry xoup, I'm not reading this thread properly so may have missed something above. If by C you mean the continuum, then C is Aleph_1, and the integers (or whatever) are Aleph_null. The continuum hypothesis is whether there are sets with cardinality inbetween Aleph_0 and Aleph_1. Cohen proved that this is undecidable - it'll depend on your axioms of set theory, and consistent set theories exist with both. But even in set theories in which there is nothing with "inbetween" cardinality, one still does not have C=Aleph_null....xouper wrote:This is one direction I need to study more.Tez wrote:Cohen proved something stronger - basically that there are consistent ("Cantorian") set theories in which the hypothesis is true, and consistent ("non-Cantorian") ones in which it is false. Thus it depends on your axioms, and in this sense is undecidable....
For example, what happens if C = Aleph-null?
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
Right. Got all that. We are on the same page. :)Tez wrote:Sorry xoup, I'm not reading this thread properly so may have missed something above. If by C you mean the continuum, then C is Aleph_1, and the integers (or whatever) are Aleph_null. The continuum hypothesis is whether there are sets with cardinality inbetween Aleph_0 and Aleph_1. Cohen proved that this is undecidable - it'll depend on your axioms of set theory, and consistent set theories exist with both. But even in set theories in which there is nothing with "inbetween" cardinality, one still does not have C=Aleph_null....
My question is what if it turns out that C = aleph_0?
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
Re: More Fun With Infinity
Its provably not (e.g. one can prove that there is no isomorphism between the reals and the rationals...), though one can certainly say "provable under which axiomatic systems", to which I can only say "all the ones which reduce to the standard intuitive properties of set theory we were taught in school and that include number theory as we know and love it!".xouper wrote:Right. Got all that. :)Tez wrote:Sorry xoup, I'm not reading this thread properly so may have missed something above. If by C you mean the continuum, then C is Aleph_1, and the integers (or whatever) are Aleph_null. The continuum hypothesis is whether there are sets with cardinality inbetween Aleph_0 and Aleph_1. Cohen proved that this is undecidable - it'll depend on your axioms of set theory, and consistent set theories exist with both. But even in set theories in which there is nothing with "inbetween" cardinality, one still does not have C=Aleph_null....
My question is what if it turns out that C = aleph_0?
By somewhat poor analogy: Take geometrical systems - I can add Euclids 5th postulate, or not, and I get different theories - but ones which agree on certain "core" geometrical features that underlie what we mean by "geometry". Proofs that rely only on those features/axioms are somehow more fundamental. My recollection is that Cohens proof of the undecidability of the CH is made under such a core set of axioms (known as the ZF axioms) of set theory and thus is quite universal. Other set theories tend to add things to the ZF axioms. (Come to think of it Cohen may have needed to add to the ZF axioms the "axiom of choice", which would make it a bit weaker than what I just said...)
Sorry, I'm really no expert on this stuff - I had the misfortune of doing a course in it, and the even greater misfortune of working with some logicians on certain quantum-logical systems that have weird properties in the classical logic/set theory context, and that is very vaguely related to this stuff. But that is the extent of my experience. [ So push me a bit harder and I'll start to crack ;) ]
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
Are any of those proofs independent of Cantor's diagonal argument? Or is Cantor's the only proof that C > aleph_0? I don't know, is why I am asking.Tez wrote:Its provably not (e.g. one can prove that there is no isomorphism between the reals and the rationals...),xouper wrote:My question is what if it turns out that C = aleph_0?
We're on the same page here.By somewhat poor analogy: Take geometrical systems - I can add Euclids 5th postulate, or not, and I get different theories - but ones which agree on certain "core" geometrical features that underlie what we mean by "geometry". Proofs that rely only on those features/axioms are somehow more fundamental.
I am not familiar enough with Cohen's work to know, so I am just asking - does he actually prove that C > aleph_0? Or does his work just assume that as already proven?My recollection is that Cohens proof of the undecidability of the CH is made under such a core set of axioms (known as the ZF axioms) of set theory and thus is quite universal. Other set theories tend to add things to the ZF axioms. (Come to think of it Cohen may have needed to add to the ZF axioms the "axiom of choice", which would make it a bit weaker than what I just said...)
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
Re: More Fun With Infinity
Hmm - 4 questions, none of which I'm certain of the answer to! I'd have to read around a bit, which means it'll have to join the list of "things to do (other than reading internet forums!) when seeking to procrastinate things I should be doing". One of my grad students is actually a mathematician, next time he shows his ugly face I'll ask him if he knows...xouper wrote:Are any of those proofs independent of Cantor's diagonal argument? Or is Cantor's the only proof that C > aleph_0? I don't know, is why I am asking.Tez wrote:Its provably not (e.g. one can prove that there is no isomorphism between the reals and the rationals...),xouper wrote:My question is what if it turns out that C = aleph_0?
We're on the same page here.By somewhat poor analogy: Take geometrical systems - I can add Euclids 5th postulate, or not, and I get different theories - but ones which agree on certain "core" geometrical features that underlie what we mean by "geometry". Proofs that rely only on those features/axioms are somehow more fundamental.
I am not familiar enough with Cohen's work to know, so I am just asking - does he actually prove that C > aleph_0? Or does his work just assume that as already proven?My recollection is that Cohens proof of the undecidability of the CH is made under such a core set of axioms (known as the ZF axioms) of set theory and thus is quite universal. Other set theories tend to add things to the ZF axioms. (Come to think of it Cohen may have needed to add to the ZF axioms the "axiom of choice", which would make it a bit weaker than what I just said...)
Sorry.
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
Another question I have is about isomorphisms of enumerations.Cool Hand wrote:Perhaps you could expound on your dissatisfaction with Cantor's diagonal method and others could critique it.
It's obvious that if there's a bijection between set S and the counting numbers, then the cardinality of set S is aleph_0.
Is the converse true? If set S has cardinality of aleph_0, then is it always the case that it can be enumerated in the form used in Cantor's diagonal argument?
How about the inverse? If there is no bijection between S and the counting numbers, does that mean S cannot have a cardinality of aleph_0?
Moving on . . .
On page 421 of Douglas Hofstadter's book, Godel, Escher, Bach, he gives an example of Cantor's diagonal argument. An example I believe to be flawed. I'm going to leave out some of Hofstadter's description of Cantor's argument, assuming that you already know it.
He goes on to explain why that number is not in the original list, using Cantor's diagonal argument. But there is a fatal flaw in his choice of the digits for the number d, which should be immediately obvious to those who have been following your thread about 0.999... = 1.Hofstadter wrote:Let us consider just real numbers between 0 and 1. ... Since real numbers are given by infinite decimals, we can imagine that the beginning of the table might look as follows:
r(1): . 1 4 1 3 9 2 6 5 3 . . .
r(2): . 3 3 3 3 3 3 3 3 3 . . .
r(3): . 7 1 8 2 8 1 8 2 8 . . .
r(4): . 4 1 4 2 1 3 5 6 2 . . .
r(5): . 5 0 0 0 0 0 0 0 0 . . .
The digits that run down the diagonal are in boldface: 1, 3, 8, 2, 0, ... Now those diagonal digits are going to be used in making a special real number d, which is betwen 0 and 1 but which we will see, is not in the list. ... Suppose, for example, that we subtract 1 from the diagonal digits (with the convention that 1 taken from 0 is 9). Then our number d will be:
. 0 2 7 1 9 . . .
Hofstadter says that d cannot be equal to r(5) because even if all the other digits of d matched up with r(5), the fifth digit does not. Except Hofstadter overlooks that r(5) can also be expressed as .49999... in which the fifth digit IS the same as d. So he has not proven that d is not in the list.
However, this flaw is a result of the way he chooses the digits for d. Instead of subtracting 1 from each digit of the diagonal to make d, suppose we subtract 3, and the flaw seems to be fixed. Or is it?
Can you see why I have an uneasy feeling about Cantor's diagonal argument?
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
Re: More Fun With Infinity
Xouper, I specifically remember in a book I read about the slash diagonal argument, that they took care to rule out that "recurring 9" problem you mention. Obviously Hofstadter didn't. I'll see if I can hunt it up...xouper wrote:Another question I have is about isomorphisms of enumerations.Cool Hand wrote:Perhaps you could expound on your dissatisfaction with Cantor's diagonal method and others could critique it.
It's obvious that if there's a bijection between set S and the counting numbers, then the cardinality of set S is aleph_0.
Is the converse true? If set S has cardinality of aleph_0, then is it always the case that it can be enumerated in the form used in Cantor's diagonal argument?
How about the inverse? If there is no bijection between S and the counting numbers, does that mean S cannot have a cardinality of aleph_0?
Moving on . . .
On page 421 of Douglas Hofstadter's book, Godel, Escher, Bach, he gives an example of Cantor's diagonal argument. An example I believe to be flawed. I'm going to leave out some of Hofstadter's description of Cantor's argument, assuming that you already know it.
He goes on to explain why that number is not in the original list, using Cantor's diagonal argument. But there is a fatal flaw in his choice of the digits for the number d, which should be immediately obvious to those who have been following your thread about 0.999... = 1.Hofstadter wrote:Let us consider just real numbers between 0 and 1. ... Since real numbers are given by infinite decimals, we can imagine that the beginning of the table might look as follows:
r(1): . 1 4 1 3 9 2 6 5 3 . . .
r(2): . 3 3 3 3 3 3 3 3 3 . . .
r(3): . 7 1 8 2 8 1 8 2 8 . . .
r(4): . 4 1 4 2 1 3 5 6 2 . . .
r(5): . 5 0 0 0 0 0 0 0 0 . . .
The digits that run down the diagonal are in boldface: 1, 3, 8, 2, 0, ... Now those diagonal digits are going to be used in making a special real number d, which is betwen 0 and 1 but which we will see, is not in the list. ... Suppose, for example, that we subtract 1 from the diagonal digits (with the convention that 1 taken from 0 is 9). Then our number d will be:
. 0 2 7 1 9 . . .
Hofstadter says that d cannot be equal to r(5) because even if all the other digits of d matched up with r(5), the fifth digit does not. Except Hofstadter overlooks that r(5) can also be expressed as .49999... in which the fifth digit IS the same as d. So he has not proven that d is not in the list.
However, this flaw is a result of the way he chooses the digits for d. Instead of subtracting 1 from each digit of the diagonal to make d, suppose we subtract 3, and the flaw seems to be fixed. Or is it?
Can you see why I have an uneasy feeling about Cantor's diagonal argument?
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
As part of a google search for the cardinality of p-adics, I stumbled across a usenet post by none other than "Archimedes Plutonium" that challenges Cantor using p-adics. Now I'm worried. I don't want my questioning to be associated or linked in any way to that fruitcake, lest I get tarred by accidental association. On the other hand, it gives me a line of research to follow, since I assume real mathematicians will have refuted Mr. Plutonium's blatherings on sci.math, and somewhere in all that I may find answers to some of my questions.
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
ok, Xoup, I think the simple answer is this: Take any terminating decimal - 0.2 say, and represent it by the non-terminating expression 0.19999
Then every number has a unique representation, and (importantly) when you do the slash diagonal thing you will NOT have a recurring decimal "on the tail" as it were.
Then every number has a unique representation, and (importantly) when you do the slash diagonal thing you will NOT have a recurring decimal "on the tail" as it were.
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
Huh - sometimes recurring 9's came back to bite Cantor in the ass too!
http://www.math.toronto.edu/jkorman/Mat ... nscard.htm
http://www.math.toronto.edu/jkorman/Mat ... nscard.htm
Again, you have no doubt heard of the way Cantor proved this by proving |(0, 1) ´ (0, 1)| = |(0, 1)|. He mapped (a, b) to c where, c is the number whose decimal representation alternates the digits of the representations of a and b. If you thought that this would be a one-one and onto function, and therefore we are done, you are wrong. Actually, because of a problem with recurring 9's, this function is only one-one. It is not onto! Cantor originally thought this is a one-one and onto function, and mailed his proof to Dedekind. Dedekind spotted the error! ( Hey, that's what friends are for! ).
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Thanks for the link. That will keep me busy for a few minutes. :shock:Tez wrote:not exactly what you want, but a quarter of the way down this guy is careful about the uniqueness of a decimal representation of the reals for constructing cantor sets:
http://www.math.nus.edu.sg/~matngtb/Cal ... cantor.htm
I'm still not clear how being careful with uniqueness of decimal representation solves the problem. The value from the diagonal could still be the same value represented the other way. I need to study this more.
I am also still looking for an answer to the question about enumerating the irrationals. How do we prove that Cantor's diagonal is not a rational number? Because if the diagonal is a rational number, then proving it's not on the list doesn't lead to a contradiction.
-
- Posts: 1296
- Joined: Fri Jun 04, 2004 5:28 am
- Location: Wisconsin
This article may be of interest to you: Cantor's Diagonal Proofxouper wrote:Thanks for the link. That will keep me busy for a few minutes. :shock:Tez wrote:not exactly what you want, but a quarter of the way down this guy is careful about the uniqueness of a decimal representation of the reals for constructing cantor sets:
http://www.math.nus.edu.sg/~matngtb/Cal ... cantor.htm
I'm still not clear how being careful with uniqueness of decimal representation solves the problem. The value from the diagonal could still be the same value represented the other way. I need to study this more.
I am also still looking for an answer to the question about enumerating the irrationals. How do we prove that Cantor's diagonal is not a rational number? Because if the diagonal is a rational number, then proving it's not on the list doesn't lead to a contradiction.
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Yes it was. Thanks. I was asking the question backwards. I should have asked is it possible to choose a diagonal number that is provably irrational, and according to that article, the answer is yes. Although there was no formal proof of that, just a narrative, it gets me in the right direction.Skeptoid wrote:This article may be of interest to you: Cantor's Diagonal Proof
-
- Posts: 29
- Joined: Mon Jun 07, 2004 11:11 pm
If you choose the unique representation, then the rationals are those which end in a string of recurring 9's (since these are the ones which have terminating decimals in the regular way of representing them). Cantor's diagonal does not end in a string of recurring 9's, and thus is irrational....xouper wrote:Yes it was. Thanks. I was asking the question backwards. I should have asked is it possible to choose a diagonal number that is provably irrational, and according to that article, the answer is yes. Although there was no formal proof of that, just a narrative, it gets me in the right direction.Skeptoid wrote:This article may be of interest to you: Cantor's Diagonal Proof
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
The article went a little further than that, since not all rational numbers have an infinite string of nines on the end (1/7 for example). Cantor's diagonal could possibly end in a string of nines given an appropriate construction, but it appears to be easy enough to choose something else for the diagonal to avoid that possibilty.Tez wrote:If you choose the unique representation, then the rationals are those which end in a string of recurring 9's (since these are the ones which have terminating decimals in the regular way of representing them). Cantor's diagonal does not end in a string of recurring 9's, and thus is irrational....xouper wrote:Yes it was. Thanks. I was asking the question backwards. I should have asked is it possible to choose a diagonal number that is provably irrational, and according to that article, the answer is yes. Although there was no formal proof of that, just a narrative, it gets me in the right direction.Skeptoid wrote:This article may be of interest to you: Cantor's Diagonal Proof
Strangely, I find I have to keep in mind that finding a single diagonal that doesn't lead to a contradiction is insufficent to refute the proof. To disprove Cantor's argument with that tactic, one must show that all possible diagonals do not lead to a contridiction. I would suspect that's not a fruitful direction to go in. :D
-
- Posts: 95
- Joined: Sun Jun 13, 2004 10:13 pm
Re: More Fun With Infinity
xouper wrote:See for example:I have no idea what your second question means. ... what does p-adics mean?
http://mathworld.wolfram.com/p-adicNumber.html
An example of a base 2 p-adic (also called 2-adics) is:
<--111.
where there are infinitely many digits to the left of the decimal point.
For those who think 0.999...=1 is strange, then try wrapping your mind around this one:
<--111. = -1
Those who are familiar with two's complement arithmetic will immediately see the beauty of that.
Mah hed is hruting!
Please enlighten this savage to the intricacies of ...that. I just don't get it.
I believe I was slack-jawed for a moment there, trying to push the little gears in my head to understand that.
-
- Posts: 1296
- Joined: Fri Jun 04, 2004 5:28 am
- Location: Wisconsin
Re: More Fun With Infinity
This wikipedia article is somewhat more accessible to the layman: p-adic numberSorgoth wrote:xouper wrote:See for example:I have no idea what your second question means. ... what does p-adics mean?
http://mathworld.wolfram.com/p-adicNumber.html
An example of a base 2 p-adic (also called 2-adics) is:
<--111.
where there are infinitely many digits to the left of the decimal point.
For those who think 0.999...=1 is strange, then try wrapping your mind around this one:
<--111. = -1
Those who are familiar with two's complement arithmetic will immediately see the beauty of that.
Mah hed is hruting!
Please enlighten this savage to the intricacies of ...that. I just don't get it.
I believe I was slack-jawed for a moment there, trying to push the little gears in my head to understand that.
The article also makes a brief reference to our old friend 0.999... =1:
The real numbers can be defined as equivalence classes of Cauchy sequences of rational numbers; this allows us to, for example, write 1 as 1.000... = 0.999... .
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
In case you are not familiar with binary, I will first do it in decimal (base ten), although technically, base ten is not a prime number base for p-adics, but it will work for this example:Sorgoth wrote:Please enlighten this savage to the intricacies of ...that. I just don't get it.xouper wrote: An example of a base 2 p-adic (also called 2-adics) is:
<--111.
where there are infinitely many digits to the left of the decimal point.
For those who think 0.999...=1 is strange, then try wrapping your mind around this one:
<--111. = -1
Those who are familiar with two's complement arithmetic will immediately see the beauty of that.
<--9999. = x
<--9990. = 10x
subtract the bottom one from the top one:
9 = -9x
x = -1
In binary (base 2):
<--1111. = x
<--1110. = 10x
subtract the bottom one from the top one:
1 = -1x
x = -1
In general, for any prime number base p>1 and d=p-1:
<--dddd. = x
<--ddd0. = 10x
subtract the bottom one from the top one:
d = -dx
x = -1
-
- Posts: 145
- Joined: Sun Jun 13, 2004 11:43 am
- Location: Caltech
Ahh! When I saw the identical proof for .999... = 1 (a fact I believed anyway), I thought, "That's a nice proof, it makes sense and everything." But now that I see the same proof being used to show such a counterintuitive result...does this result apply to all numbers, or just p-adic ones? Or does the <--- symbol only make sense in p-adic numbers?
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
The article also mentions this:Skeptoid wrote:This wikipedia article is somewhat more accessible to the layman: p-adic number
Dang. I was hoping that they were countable, since that would have been consistent with my method for enumerating the reals. In other words, my method requires the set of 2-adic integers to be countable. Not looking so good for my enumeration method.wikipedia wrote:The set of p-adic integers is uncountable.
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
Re: More Fun With Infinity
Does anyone know where I can find a proof of this for the 2-adics?wikipedia wrote:The set of p-adic integers is uncountable.
I can't seem to get Cantor's diagonal to work on it, for the exact same reason I can't get Cantor's diagonal to work on my enumeration of the reals. For those of you who are clever, that may be enough information to reveal how I am trying to enumerate the reals. If you figure it out, remember, I thought of it first. Unless of course, it has already been published and refuted and I just haven't found it yet.
Jeebus, I sound just like one of those math crackpots that thinks he's found a proof of Fermat's Last Theorem that's small enough to fit in the margin of a book page. :shock:
-
- Posts: 11741
- Joined: Fri Jun 11, 2004 4:52 am
- Title: mere ghost of his former self
I invented the <-- symbol for this message board, and I suspect it is only useful for p-adics that extend to the left without bound. I was going to use an ellipsis to the left, but I feared confusion with where the decimal point was. The usual math notation is to use an overbar (also called a vinculum) to indicate the repeating digits, but that requires html which is not fully enabled on this forum. For p-adics, the vinculum also has an arrowhead pointing to the left, which is hard to do in html.rwald wrote:Ahh! When I saw the identical proof for .999... = 1 (a fact I believed anyway), I thought, "That's a nice proof, it makes sense and everything." But now that I see the same proof being used to show such a counterintuitive result...does this result apply to all numbers, or just p-adic ones? Or does the <--- symbol only make sense in p-adic numbers?
-
- Posts: 145
- Joined: Sun Jun 13, 2004 11:43 am
- Location: Caltech
Well, in theory (and by that I mean, "it would make sense to me if..."), a number such as <---999 should equal an infinity of some sort. Also, my intuition would suggest that any number with an infinite number of digits to the left equals any other number with an infinite number of digits to the left. And so <---999 = -1 seems to imply that infinity = -1, which is counterintuitive to say the least. Of course, I don't know anything about p-adic numbers, and I freely admit that my intuition is probably not very reliable in this field.
-
- Posts: 10000
- Joined: Sun Jun 06, 2004 4:09 pm
- Location: Earning my avatar in the rain