More Fun With Infinity

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

More Fun With Infinity

Post by Cool Hand »

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
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez »

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

;)
rwald
Posts: 145
Joined: Sun Jun 13, 2004 11:43 am
Location: Caltech

Re: More Fun With Infinity

Post by rwald »

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?
shanek
Posts: 804
Joined: Fri Jun 04, 2004 11:11 pm
Location: Starbug 1

Post by shanek »

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)
Cool Hand
Posts: 10000
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain

Re: More Fun With Infinity

Post by Cool Hand »

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
Pyrrho
Posts: 33840
Joined: Sat Jun 05, 2004 2:17 am
Title: Man in Black
Location: Division 6

Post by Pyrrho »

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?
rwald
Posts: 145
Joined: Sun Jun 13, 2004 11:43 am
Location: Caltech

Post by rwald »

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.
shanek
Posts: 804
Joined: Fri Jun 04, 2004 11:11 pm
Location: Starbug 1

Post by shanek »

rwald wrote:Wasn't that Hilbert's Hotel?
Could be...I read it many many years ago and pulled it out from memory.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

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?
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Post by xouper »

rwald wrote:Wasn't that Hilbert's Hotel?
Yep.
Cool Hand
Posts: 10000
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain

Re: More Fun With Infinity

Post by Cool Hand »

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
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Post by xouper »

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.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

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.
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez »

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....
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

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?
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez »

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....
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

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?
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez »

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 ;) ]
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

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?
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez »

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.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

Cool Hand wrote:Perhaps you could expound on your dissatisfaction with Cantor's diagonal method and others could critique it.
Another question I have is about isomorphisms of enumerations.

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.
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 . . .
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 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?
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Re: More Fun With Infinity

Post by Tez »

xouper wrote:
Cool Hand wrote:Perhaps you could expound on your dissatisfaction with Cantor's diagonal method and others could critique it.
Another question I have is about isomorphisms of enumerations.

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.
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 . . .
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 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?
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
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Post by xouper »

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.
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Post by Tez »

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
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Post by Tez »

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.
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Post by Tez »

Huh - sometimes recurring 9's came back to bite Cantor in the ass too!

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! ).
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Post by xouper »

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
Thanks for the link. That will keep me busy for a few minutes. :shock:

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.
Skeptoid
Posts: 1296
Joined: Fri Jun 04, 2004 5:28 am
Location: Wisconsin

Post by Skeptoid »

xouper wrote:
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
Thanks for the link. That will keep me busy for a few minutes. :shock:

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.
This article may be of interest to you: Cantor's Diagonal Proof
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Post by xouper »

Skeptoid wrote:This article may be of interest to you: Cantor's Diagonal Proof
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.
Tez
Posts: 29
Joined: Mon Jun 07, 2004 11:11 pm

Post by Tez »

xouper wrote:
Skeptoid wrote:This article may be of interest to you: Cantor's Diagonal Proof
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.
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
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Post by xouper »

Tez wrote:
xouper wrote:
Skeptoid wrote:This article may be of interest to you: Cantor's Diagonal Proof
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.
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....
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.

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
Sorgoth
Posts: 95
Joined: Sun Jun 13, 2004 10:13 pm

Re: More Fun With Infinity

Post by Sorgoth »

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

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.
Skeptoid
Posts: 1296
Joined: Fri Jun 04, 2004 5:28 am
Location: Wisconsin

Re: More Fun With Infinity

Post by Skeptoid »

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

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.
This wikipedia article is somewhat more accessible to the layman: p-adic number

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... .
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

Sorgoth wrote:
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.
Please enlighten this savage to the intricacies of ...that. I just don't get it.
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:

<--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
rwald
Posts: 145
Joined: Sun Jun 13, 2004 11:43 am
Location: Caltech

Post by rwald »

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?
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

Skeptoid wrote:This wikipedia article is somewhat more accessible to the layman: p-adic number
The article also mentions this:
wikipedia wrote:The set of p-adic integers is uncountable.
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.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Re: More Fun With Infinity

Post by xouper »

wikipedia wrote:The set of p-adic integers is uncountable.
Does anyone know where I can find a proof of this for the 2-adics?

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:
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Post by xouper »

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?
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
Posts: 145
Joined: Sun Jun 13, 2004 11:43 am
Location: Caltech

Post by rwald »

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.
Cool Hand
Posts: 10000
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain

Post by Cool Hand »

rwald wrote: 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.
I don't either rwald. I think I'm going to sue my math profs.

Cool Hand