More Fun With Infinity

We are the Borg.
User avatar
Cool Hand
Posts: 9999
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain

More Fun With Infinity

Post by Cool Hand » Sun Jun 20, 2004 6:42 pm

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

User avatar
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez » Sun Jun 20, 2004 7:03 pm

Cool Hand wrote:Does anyone know how to prove the Continuum Hypothesis? (Kurt Godel) How to disprove it? (Paul Cohen)
No.

(and about that I am decided...)

;)

User avatar
rwald
Posts: 145
Joined: Sun Jun 13, 2004 11:43 am
Location: Caltech

Re: More Fun With Infinity

Post by rwald » Sun Jun 20, 2004 11:05 pm

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]

User avatar
shanek
Posts: 804
Joined: Fri Jun 04, 2004 11:11 pm
Location: Starbug 1

Post by shanek » Mon Jun 21, 2004 12:57 am

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)
There is an old android saying. In binary it reads: 01001001001001110110110100100000011011100110111101110100001
00000011101110110010101100001011100100110100101101110011001
1100100000011100000110000101101110011101000111001100100001. Makes you think, huh?

User avatar
Cool Hand
Posts: 9999
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain

Re: More Fun With Infinity

Post by Cool Hand » Mon Jun 21, 2004 1:34 am

rwald wrote: Anyway, so yea, I'm not entirely familiar with your definition of X1. Could you elaborate?
http://mathworld.wolfram.com/Aleph-1.html

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

User avatar
Pyrrho
Posts: 27890
Joined: Sat Jun 05, 2004 2:17 am
Title: Man in Black
Location: Division 6

Post by Pyrrho » Mon Jun 21, 2004 1:34 am

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)
So where's the other dollar?

User avatar
rwald
Posts: 145
Joined: Sun Jun 13, 2004 11:43 am
Location: Caltech

Post by rwald » Mon Jun 21, 2004 1:37 am

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)
Wasn't that Hilbert's Hotel?

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]

User avatar
shanek
Posts: 804
Joined: Fri Jun 04, 2004 11:11 pm
Location: Starbug 1

Post by shanek » Mon Jun 21, 2004 2:02 am

rwald wrote:Wasn't that Hilbert's Hotel?
Could be...I read it many many years ago and pulled it out from memory.
There is an old android saying. In binary it reads: 01001001001001110110110100100000011011100110111101110100001
00000011101110110010101100001011100100110100101101110011001
1100100000011100000110000101101110011101000111001100100001. Makes you think, huh?

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

Re: More Fun With Infinity

Post by xouper » Tue Jun 22, 2004 2:35 pm

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

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?

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

Post by xouper » Tue Jun 22, 2004 2:38 pm

rwald wrote:Wasn't that Hilbert's Hotel?
Yep.

User avatar
Cool Hand
Posts: 9999
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain

Re: More Fun With Infinity

Post by Cool Hand » Tue Jun 22, 2004 2:43 pm

xouper wrote:
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.
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?

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?
Actually, I think Tez is right, as Godel and Cohen each used rigorous proofs and got opposite results.

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

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

Post by xouper » Tue Jun 22, 2004 2:50 pm

shanek wrote:inifnity + infinity = infinity
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.

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.

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

Re: More Fun With Infinity

Post by xouper » Tue Jun 22, 2004 3:16 pm

Cool Hand wrote:Actually, I think Tez is right, as Godel and Cohen each used rigorous proofs and got opposite results.
For example:
http://www.faqs.org/faqs/sci-math-faq/AC/ContinuumHyp/
Perhaps you could expound on your dissatisfaction with Cantor's diagonal method and others could critique it.
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.
I have no idea what your second question means. ... what does p-adics mean?
See for example:
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.

User avatar
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez » Tue Jun 22, 2004 3:19 pm

Cool Hand wrote:[Actually, I think Tez is right, as Godel and Cohen each used rigorous proofs and got opposite results.
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....

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

Re: More Fun With Infinity

Post by xouper » Tue Jun 22, 2004 3:29 pm

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....
This is one direction I need to study more.

For example, what happens if C = Aleph-null?

User avatar
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez » Tue Jun 22, 2004 3:40 pm

xouper wrote:
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....
This is one direction I need to study more.

For example, what happens if C = Aleph-null?
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....

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

Re: More Fun With Infinity

Post by xouper » Tue Jun 22, 2004 4:02 pm

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....
Right. Got all that. We are on the same page. :)

My question is what if it turns out that C = aleph_0?

User avatar
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez » Tue Jun 22, 2004 4:22 pm

xouper wrote:
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....
Right. Got all that. :)

My question is what if it turns out that C = aleph_0?
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!".

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 ;) ]

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

Re: More Fun With Infinity

Post by xouper » Tue Jun 22, 2004 4:37 pm

Tez wrote:
xouper wrote:My question is what if it turns out that C = aleph_0?
Its provably not (e.g. one can prove that there is no isomorphism between the reals and the rationals...),
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.
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.
We're on the same page here.
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...)
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?

User avatar
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez » Tue Jun 22, 2004 4:43 pm

xouper wrote:
Tez wrote:
xouper wrote:My question is what if it turns out that C = aleph_0?
Its provably not (e.g. one can prove that there is no isomorphism between the reals and the rationals...),
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.
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.
We're on the same page here.
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...)
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?
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...

Sorry.