More Fun With Infinity

We are the Borg.
xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building

Re: More Fun With Infinity

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

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

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

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.
xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building
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
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: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building
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.
Sorgoth
Posts: 95
Joined: Sun Jun 13, 2004 10:13 pm

Re: More Fun With Infinity

xouper wrote:
I have no idea what your second question means. ... what does p-adics mean?
See for example:

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

Re: More Fun With Infinity

Sorgoth wrote:
xouper wrote:
I have no idea what your second question means. ... what does p-adics mean?
See for example:

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

Re: More Fun With Infinity

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

Re: More Fun With Infinity

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

Re: More Fun With Infinity

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.
xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building
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
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.
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]
Cool Hand
Posts: 9999
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain
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
....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