User talk:Flabdablet

Welcome to my talk page.

I started this page because I wanted a better understanding of Cantor's diagonal argument than I could get from the Wikipedia article.

I first saw the diagonal argument many years ago in Gödel, Escher, Bach, was pleased by its elegance and swallowed it whole. Just the other day, though, it occurred to me that it should be possible to run the diagonal argument equally well on the natural numbers, just by padding them on the left with zeroes and running the diagonal downward to the left instead of downward to the right; which would seem to imply that the natural numbers themselves were not countably infinite i.e. could not be put in one-to-one correspondence with themselves!

This seemed to me a clear demonstration that the diagonal argument was flawed. Having very little formal mathematical training, I immediately consulted Wikipedia and found that Frank Guerin had posted the same idea in April.

Mormegil and William M. Connolley then pointed out that the object built by diagonal construction on the list of natural numbers has an infinite number of nonzero digits, is therefore not a natural number, and is therefore not a missing member of the list.

When I objected that the number of digits in a given number N is roughly log(N) and that log(N) has no upper bound, William replied "Each natural number is of finite length, individualy. But (as you note) there is no upper bound to the number of digits in a natural number. But the two ideas are distinct."

This argument smells fishy to me, and I am currently doing more reading about infinity to see if I can dissipate the smell.

My current sticking point is this:

Consider a list of natural numbers. Just to make things a little less cloudy, let's write it down using standard base-10 notation, in ascending order from 1, with no redundant digits. If there are N numbers in the list, the length (number of rows) will clearly be N, and the width (number of columns) will be floor(log10(N)) + 1.

This length and width remain the same if we choose to pad each number in the list with enough zeroes to give all the list entries the same number of digits, so let's do that now.

Neither floor() nor log10() has an upper bound on domain or range, so it's clear that if we now make N infinite, both the length and width of our list also become infinite. We have a firm grasp of the top right corner, but now our list has digits all the way down and digits all the way to the left.

But if the width of the list is infinite, and there is nothing in the list but natural numbers, how can possession of a finite number of digits be a required attribute of a natural number when considered in the context of an infinite list?

Replies are cordially invited from people who have clear explanations, or can provide links to same.

(Mormegil 08:57, 24 Nov 2004 (UTC)) It seems to me that the problem is in your understanding of infinity. The fact that there is an infinite number of naturals means only that I can say "give me a natural number and I'll give you a bigger one". But still, each natural number that you or I would say, would have a finite number of digits. (I would even say that it is by definition of naturals.) On the other hand, with reals, you can say π and that number does not have a finite number of digits, even though you are able to "simply" define the number.

You could look at it from a pure mathematical point of view and prove that each natural number has a finite number of nonzero digits, simply by mathematical induction.

Well, I am afraid I cannot offer any clear explanation, maybe except an explanation that infinities really are strange, see e.g. Hilbert's paradox of the Grand Hotel.

(Flabdablet 12:17, 24 Nov 2004 (UTC)) You're right about my failure to grok infinity; that's what I'm here to fix.

I'm cool with induction. Induction clearly shows that any individual entry pulled from such an infinite list of natural numbers will be a finite number of rows from the top of the list, and have a finite number of nonzero digits on its right hand side. No problem there.

The fact remains, though, that the logarithmic relationship between list length and list width holds true with no upper bound; so if the list is infinitely long (downwards) it must be infinitely wide (leftwards).

But the list contains only natural numbers, each of which (by induction) has a finite width, and the list's width is determined solely by the width of its widest member(s); so it can't be infinitely wide.

Therefore, we appear to be looking at a reductio ad absurdum for the constructibility of an infinite list of natural numbers.

Cantor's diagonal argument has long been accepted as a proof that you can't count the real numbers in [0,1] because you can't construct an exhaustive list. Doesn't the argument above prove that you can't count the natural numbers either?

Simply saying that infinities are strange doesn't really cut the mustard for me. Neither does the Grand Hotel red herring, which is simply a piquant illustration that if x is infinite, so is f(x) for a wide variety of functions f().

We demand rigidly defined areas of doubt and uncertainty! :-)

(Mormegil 15:51, 24 Nov 2004 (UTC)) Now I understand (I hope, at least). I think the problem with your proof is in the list's width is determined solely by the width of its widest member(s): If there was a thing like its widest member, it would mean that such member is the largest number in the list. Which would mean the list is finite (remember, these are naturals). Then your reasoning goes like "if the list is finite, the list cannot be infinite". True.

But, the list is infinite, there is no such thing as the widest member. The list is of an infinite width in the same way it is of an infinite height.

But, definitely, 42 is on the list. :-) (I am afraid that you cannot expect any enlightment from me, I am not a mathematician...)

Frank Guerin 02:24, 21 Feb 2005 (UTC) I like the bit about the log relationship between list length and width, it captures the idea very clearly. I think with mathematics we have to drop our intuitions and follow whatever axioms there are logically. I guess the log function is only defined for finite inputs, so it holds for any length of list, with no upper bound. However, I guess it doesn't work on infinity, log(infinity) must be undefined, although intuitively we feel it should be infinity because the list width is heading that way. This is part of the same problem I had with infinity, like if you consider the set S defined as the set of the first n Natural numbers. Now consider the relationship between the size of the set S and the largest element in S. For size 4 the largest element is 4, for size 5 it's 5, etc. However it breaks down at infinity (as do our intuitions). For size infinity (S=N) the largest element is not infinity, because infinity is not a natural number. The largest element can be as big as you like, but not infinity.

An attempt to enumerate [0,1]

Discussion continued from here.

OK, I don't get this either.

It seems to me that if one is willing to allow the construction 0.99999... to represent exactly 1, there should be no objection to allowing the output of any procedure that emits a sequence of digits that converges on x as the sequence length grows to be a representation of exactly x.

Further, it seems to me that the output of any procedure that emits an infinite list of digit-patterns approaching ever more closely complete coverage of [0,1] should be acceptable as an enumeration of that range. The suggested reversed-binary-integer pattern is clearly one such.

Army1987 objects to this on the grounds that all members of that list have the form n/2^m for n and m both integers, and can therefore not possibly equal any irrational number. A parallel line of reasoning applied to the list

0.00000000 ...
0.90000000 ...
0.99000000 ...
0.99900000 ...
0.99990000 ...
.
.
.

shows that all the members of this list have the form (10ⁿ-1)/10ⁿ for n integer, and therefore no member can possibly equal 1.

Clearly, though, something strange happens to lists that are allowed to grow infinitely long. Once you realize that the list above is not changed by removal of all the trailing zeroes, 0.99999... clearly belongs on it, and 0.99999... does equal 1.

(SFT 17:11, August 29, 2005 (UTC)) I don't know where to stick this in the thread, so I'll stick it here. The following list is exactly equivalent to your previous list.

0.00000000 ...
0.89999999 ...
0.98999999 ...
0.99899999 ...
0.99989999 ...
0.99998999 ...
.
.
.

So maybe that will help you see why 0.999..... is not a member of that list.  :) The 8 will keep moving down the line, but never disappear.

The whole basis of the Diagonal argument is that every number on (0,1) has a decimal representation that neither 1) terminates nor 2) ends in zeroes.

Don't ask me what to do with zero itself, I'm not a mathematician.  ;)

(Army1987 14:23, 27 Nov 2004 (UTC)) No. It DOESN'T belong to it. The number of nine-digits in it is infinity (more precisely, aleph-zero), and infinity is NOT a natural number.

(Flabdablet 12:32, 30 Nov 2004 (UTC)) I understand and accept that infinity is not a natural number. I'm making the (possibly subtle? possibly bone-headed?) point that list above is infinitely long. If it is legitimate to speak of aleph-zero as "the number of nine-digits in" 0.99999..., it's presumably just as legitimate to say that aleph-zero is also the number of entries in that list; and since the list construction method makes the number of nines in any list entry equal to the number of entries preceding it, that puts 0.99999... on the list - doesn't it? If not, why not?

(Army1987 15:04, 2 Dec 2004 (UTC)) You can have any arbitrarily large FINITE number of nines, but you can NOT have infinitely many nines. The number with aleph-zero nines would be the last number on that list, but it's quite clear that it does not have any last element.

(Flabdablet 07:49, 3 Dec 2004 (UTC)) This is the burning question: if you can't have infinitely many nines, what exactly does the ellipsis at the end of "0.99999..." mean?

I agree that the list does not have a last element; that's what makes it an infinite list. What you can do, it seems to me, is use the same kind of "and so on" idea needed to make 0.99999... make sense, to make certain kinds of infinite list make sense. It's obvious to me (though I'm willing to be persuaded else) that the physical construction of an infinite list of anything - be it digits, or numbers, or whatever - cannot actually be a supertask - you can't actually, physically, build one, so it doesn't surprise me that reasoning on the basis that you have built one runs into controversy.

It seems to me that the meaning of such a construction, if it has one, must be determined by the nature of the construction method. In the case of the infinite list of identical digits represented by "0.99999...", that meaning is the number 1; I can't think of a good reason for not defining the meaning of the list below (the infinite binary thingy) as the range [0,1].

What would be the real-world consequences of deleting the entire notion of transfinites from respectable mathematics? Are they actually good for something other than starting arguments with non-mathematicians? :-)

We're not speaking of our physical world. It has been even postulated that in it real numbers don't make any sense (digital physics). However, binary 0.11111...=1 does not belong to the set {1-2^-n: n∈ℕ}.

Similarly, it seems to me that the infinite list of binary fractions

0.0
0.1
0.01
0.11
0.001
0.101
0.011
0.111
.
.
.

can quite reasonably be held to include 0.11111... (which, incidentally, equals 1).

I dont think that is reasonable at all. It is an infinate list. Therefore, by definition, every entry has a successor. What, with your enumeration is the successor of 0.1111... in the list? It doesnt have one, therefore, it aint there! 81.105.70.72 (talk) —Preceding comment was added at 01:15, 13 June 2008 (UTC)

The argument for both inclusions is the same as the argument for the validity of the sums of infinite converging sequences. Just as 1 is the limiting sum that the series represented by 0.11111... approaches, 0.11111... is itself a limiting pattern that the list above approaches.

The really interesting thing about extending that list to infinite length, though, is that the consequence of doing so is to generate all possible arrangements of binary digits including those of infinite length. The reasoning here is the same as that in the previous section: the number of columns in this list is simply floor(log2(n)), where n is the number of rows, and neither floor() nor log2() has an upper bound on domain or range; as n goes to infinity, so does the number of columns.

Which really does seem to kick the Diagonal Argument square in the nuts. Not only do we have a method for enumerating [0,1]; but the Diagonal Argument's countercase actually does appear in the enumeration, by implication - not explicitly!

If this reasoning has run off the rails, I would appreciate being shown which careless assumption is false and why.

I'm too sleepy at the moment to check this list against Cantor's first uncountability proof, but I'm sure the result of doing so will be illuminating one way or another.

Let's see if you understand this:

(Army1987 14:20, 27 Nov 2004 (UTC)) The set of natural numbers is infinite, but NO GIVEN NATURAL NUMBER IS INFINITE.

(Flabdablet 23:48, 29 Nov 2004 (UTC)) Please, there's no need to shout; speaking Tourist fails just as badly for mathematicians as for anybody else :)

It's quite clear to me that any given natural number is finite; no problem there. It's also clear that if you give me any natural number, I can give you a bigger one; therefore, no finite size will suffice for the set of natural numbers, or for the size of any other set whose members are defined by an open-ended scheme.

The diagonal argument and issues arising have been running around in the back of my head for several days now, and what I'm currently most unhappy about is the propriety of considering an object built using the properties of the whole list as a candidate for list membership. It seems to me that if this operation is disallowed for adding a diagonally-constructed item to the list of natural numbers, there is a prima facie case for suspecting that it should also be disallowed for adding a diagonally-constructed item to the list of reals in [0,1].

Various people have pointed out that the key difference between the two lists is that the list of reals is already of infinite width by virtue of the infinite decimal expansions of numbers other than k/2^m5ⁿ; therefore it should easily accommodate the infinite string of digits constructed by the diagonal method. Personally I am still uneasy about this.

It seems to me that the essence of the idea of infinity is captured in the phrase "and so on"; an infinite list is a list generated according to a pattern that could be extended without limit, and an infinite decimal expansion is an expansion that could be written down without limit. The only way I can actually make the Diagonal Argument's method of constructing the "missing" number meaningful is to think of it as a demonstration that for any list of length k, there is a number x of length k that doesn't appear on that list.

(Army1987 15:14, 2 Dec 2004 (UTC)) There's a difference between "potential" infinity and "actual" infinity.

(Flabdablet 07:49, 3 Dec 2004 (UTC)) I'm coming around to the view that the fundamental difference is that potential infinity is a meaningful concept whereas actual infinity is not. I'll bet you a dollar that I can find a way to demonstrate that any alleged example of an "actual" infinity (complete with scare quotes) is just a misunderstood potential infinity.

I say that the power set of the set of natural numbers is actually infinite.

Find a way to demostrate that it is just a misunderstood potential infinity.

(Army1987 15:14, 2 Dec 2004 (UTC)) You could have a natural number with as many digits as you want, but it will always be a finite number of digits. Instead, given a number such as 1/3, it must have an infinitely long expansion, because any finite expansion (0.3, 0.33, 0.333, etc.), no matter how long, is less than 1/3 and therefore wrong.

(Flabdablet 07:49, 3 Dec 2004 (UTC)) Exactly! Any actual expansion misses the mark; only the potentially infinite expansion represented by "0.33333..." hits it, and then only because the value of an infinite series has been defined to be the limit that the values of series of increasing length approach.

You're implying that 0.3333...(infinitely many times) is not 'really existing' or something like that, but you don't explain why.

By the way: thanks for this conversation. It's lovely to find somebody else who can be bothered thinking about this stuff.

Let's create a sequence R₁, R₂, R₃, ... by some rule, and apply the Diagonal Argument's method to it every time we add a member R_i. What we end up with is another sequence D₁, D₂, D₃, ... where the method guarantees that D_i is never present in R₁ .. R_n for i <= n.

Depending on the R-sequence construction method, though, we may well be able to show that any D_i must be present in R₁ .. R_n for a suitably large value of n; which, given the fact that n is unbounded, must mean that all D_i are in fact members of R. Which is a contradiction. Which, it seems to me, makes any conclusions drawn on the basis of Diagonal Method arguments wobbly.

That's where I'm at right now. Comments and clarifications welcome.

(Army1987 15:14, 2 Dec 2004 (UTC)) 0.0101010101010101010101010101...(infinitely many times) is a real number.

...1010101010101010101010101010101010(infinitely many times) is not a natural number.

Can you see that?--

(Flabdablet 07:49, 3 Dec 2004 (UTC)) Readily.

(Army1987 15:14, 2 Dec 2004 (UTC)) For example, in the enumeration of yours, which natural number does 1/5 (binary 0.01) correspond to?

(Flabdablet 07:49, 3 Dec 2004 (UTC)) Depends which one you assign to 0.0; personally I like 0 for that, which would make 0.01 list item #2. But I suspect you're actually talking about binary 0.01010101..., which given that it is of infinite length clearly has an infinite list index.

Yes, I refer to it.

Therefore it's not paired with a natural number.

And that's the key to the whole thing, right there. The idea of countability is not, despite first appearances, an idea about ways to generate every possible member of a set, infinite or otherwise, systematically; it's an idea about ways to put any given member of a given set into one-to-one correspondence with a well defined natural number.

Clearly, it is easily possible to match up any member of the set of natural numbers with a well defined natural number (matching each number with itself is the obvious way; matching each number with twice itself works too, and gets you free entry to Hilbert's Hotel).

The real numbers are much less clear, though. Can somebody point me to a proof that the object produced via the diagonal construction step of Cantor's procedure is guaranteed to be eligible for membership in the set of reals, regardless of the method employed in the list construction step?

Cantor was wrong

The diagonal argument isn´t very good.

It exist two books in Norwegian that is much of the same as the counterproof in this discussion.

The author is Jon Einbu (master in mathematics, but no PhD i think).

His bijection is:

1 = 0,1

2 = 0,2

3= 0,3

...

10 = 0,01

11 = 0,11

...

1234 = 0,4321

then he argues that (...) can be applied to natural numbers as well. You can write ...333 = 333...

you will have irrational numbers as well PI/10 is ...951413 =0,314159....

Now you can apply Cantor´s diagonal "proof" on the natural numbers, so all can see where it goes wrong. Just write the numbers like ...0001, ...0002, ...0003, etc

Cantor would say that the natural number ...9999999999999 isn´t in the list. Since also the natural numbers can´t be ordered, the diagonal proof doesn´t prove that there is not a 1:1 correspndance between the natural and real numbers

But ...999999 isnt a natural number, or indeed a number of any sort. Whereas 0.99999.... is —Preceding unsigned comment added by 81.105.70.72 (talk) 01:09, 13 June 2008 (UTC)

The best proof that Cantor´s project isn´t very good is that no new discoveries comes in this field of mathematics. All the books in this field are quite old.

The only way to understand infinity better is with a discrete understanding of sequences. You have to know how fast a number grows.

0,666... is only twice as big as 0,333... if it has the same growth rate. if 0,6 = 0,33, 0,66 = 0,3333, 0,666 = 0,333333 and 0,666... = 0,333333... then 0,666... is not twice as big as 0,333333...

With this discrete understanding, you can say that there are twice as many positive and negative numbers as positive numbers if the series grows like this:

1 = -1 and 1, 2 = -2 and 2, etc

Or you can say that there are just as many with this growth rate: 1 = 1, 2 = -1, 3 = 2, 4 = -2 etc

But then 2N always corresponds to N, and you can say that the positive numbers grows twice as fast as the positive and negative numbers. This is a start to a commen-sense understanding of infinity. You can define oo (infinity) / 0 = 1, and you can divide numbers on 0.

Åsmund Børsum, Norway

More Cantor

Is 0,9999... = 1?

With the discrete understanding i presented above, they are not. At any time, you can stop the growth of the series to examine 1,000 is not 0,999, and 1,0000000 is not 0,9999999.

Some says that 1 can be represented in two ways like above, but 1/3 can only be expressed in one way. That´s wrong, and it is just because we use the 10 digit systems for representations of real numbers.

In the 3 digit system 1/3 can be representet in two ways: 0,0222... and 0,10000... Åsmund Børsum

But the point is, time isnt involved. "0.999..." is DEFINED as the LIMIT of this sequence, not where it gets to in any finite time - which is... 1 78.151.107.66 (talk) 12:34, 23 June 2008 (UTC)