More Fun With Infinity

 Posts: 9999
 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. Nonmathematicians 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
....life purpose is pay taxes  pillory 12/05/13
And you run and you run to catch up with the sun but it's sinking
Racing around to come up behind you again
The sun is the same in a relative way, but you're older
Shorter of breath and one day closer to death.
"Time"  Pink Floyd
And you run and you run to catch up with the sun but it's sinking
Racing around to come up behind you again
The sun is the same in a relative way, but you're older
Shorter of breath and one day closer to death.
"Time"  Pink Floyd

 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?
For the record, I don't actually know anything. Not even this.
Ever wondered what being a Caltech undergrad was like?
[url=http://caltizzle.caltech.edu]caltizzle.caltech.edu[/url]
Ever wondered what being a Caltech undergrad was like?
[url=http://caltizzle.caltech.edu]caltizzle.caltech.edu[/url]

 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 oddnumbered 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 oddnumbered rooms.
So: inifnity + infinity = infinity
(Note: NOT responsible for exploding brains)
There is an old android saying. In binary it reads: 01001001001001110110110100100000011011100110111101110100001
00000011101110110010101100001011100100110100101101110011001
1100100000011100000110000101101110011101000111001100100001. Makes you think, huh?
00000011101110110010101100001011100100110100101101110011001
1100100000011100000110000101101110011101000111001100100001. Makes you think, huh?

 Posts: 9999
 Joined: Sun Jun 06, 2004 4:09 pm
 Location: Earning my avatar in the rain
Re: More Fun With Infinity
http://mathworld.wolfram.com/Aleph1.htmlrwald wrote: Anyway, so yea, I'm not entirely familiar with your definition of X1. Could you elaborate?
Cool Hand
....life purpose is pay taxes  pillory 12/05/13
And you run and you run to catch up with the sun but it's sinking
Racing around to come up behind you again
The sun is the same in a relative way, but you're older
Shorter of breath and one day closer to death.
"Time"  Pink Floyd
And you run and you run to catch up with the sun but it's sinking
Racing around to come up behind you again
The sun is the same in a relative way, but you're older
Shorter of breath and one day closer to death.
"Time"  Pink Floyd

 Posts: 28628
 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 oddnumbered 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 oddnumbered 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.
For the record, I don't actually know anything. Not even this.
Ever wondered what being a Caltech undergrad was like?
[url=http://caltizzle.caltech.edu]caltizzle.caltech.edu[/url]
Ever wondered what being a Caltech undergrad was like?
[url=http://caltizzle.caltech.edu]caltizzle.caltech.edu[/url]

 Posts: 804
 Joined: Fri Jun 04, 2004 11:11 pm
 Location: Starbug 1
Could be...I read it many many years ago and pulled it out from memory.rwald wrote:Wasn't that Hilbert's Hotel?
There is an old android saying. In binary it reads: 01001001001001110110110100100000011011100110111101110100001
00000011101110110010101100001011100100110100101101110011001
1100100000011100000110000101101110011101000111001100100001. Makes you think, huh?
00000011101110110010101100001011100100110100101101110011001
1100100000011100000110000101101110011101000111001100100001. Makes you think, huh?

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
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 padics?

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building

 Posts: 9999
 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 padics?
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 padics mean?
Cool Hand
....life purpose is pay taxes  pillory 12/05/13
And you run and you run to catch up with the sun but it's sinking
Racing around to come up behind you again
The sun is the same in a relative way, but you're older
Shorter of breath and one day closer to death.
"Time"  Pink Floyd
And you run and you run to catch up with the sun but it's sinking
Racing around to come up behind you again
The sun is the same in a relative way, but you're older
Shorter of breath and one day closer to death.
"Time"  Pink Floyd

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
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: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
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/scimathfaq/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 padics mean?
http://mathworld.wolfram.com/padicNumber.html
An example of a base 2 padic (also called 2adics) 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 ("nonCantorian") 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: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
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 ("nonCantorian") ones in which it is false. Thus it depends on your axioms, and in this sense is undecidable....
For example, what happens if C = Alephnull?

 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 ("nonCantorian") ones in which it is false. Thus it depends on your axioms, and in this sense is undecidable....
For example, what happens if C = Alephnull?

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
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 quantumlogical 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: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
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.