[lisper]

> Without the decimal point these real numbers just become natural numbers.

No, they don't, because the vast majority of them have an infinite number of digits to the right of the decimal point. That's the key: there are more numbers with an infinite number of non-zero digits (the reals) than there are numbers with a finite number of non-zero digits (the naturals).

> The problem with Cantor's argument comes down to the fact that the procedure he uses to find a number not in the set is essentially the same as the procedure he uses for creating the infinite set in the first place.

Again, no. Cantor doesn't create the set, you do. The proof is like a game. It says: give me any procedure for (putatively) making a list of all of the real numbers, and I will give you back a number that is not in the list.

[chriswarbo]

> The proof is like a game. It says: give me any procedure for (putatively) making a list of all of the real numbers, and I will give you back a number that is not in the list.

The game isn't fair though; we have to write down our complete solution (e.g. in the form of a never-halting, co-recursive computer program), then Cantor can take as much time as he likes (any finite number of steps) to analyse the source code and find a Real it'll never output.

Yet we can turn the tables to play a different game: whatever counter-example-finder Cantor chooses, if we make him write it down (as a computer program), we can always (eventually) find a program which will trick it: outputting only a countable number of Reals, but always a superset of those checked for by Cantor's program.

Of course, if we're representing the players of the game using computer programs, then we can go one step further and show that only the Computable numbers (a subset of the Reals) can ever be generated, and the computables are countable! (We can count them by pairing off all programs with all runtimes)

[lisper]

> if we make him write it down (as a computer program)

He did. Diagonalization is an algorithm. It's a non-halting algorithm (because it operates on infinite input and produces infinite output) but it is nonetheless a perfectly well defined algorithm that can be implemented by a Turing Machine.

> we can always (eventually) find a program which will trick it

No, you can't.

[chriswarbo]

You're right about diagonalization when it's given our choices as input. When I said 'writing down' I meant 'in a self-contained way', i.e. without taking any input (such as our choices).

This rules out diagonalization, since that can't be run until it has a list of numbers to diagonalize. In the 'reverse' game, we're first running the counter-example-outputting program that Cantor provides, and then using its output to pick our numbers. If Cantor gives us a diagonalization program, we'll get a deadlock. In fact, the strategy to beat Cantor in this reverse game is simply the identity function: if Cantor's program claims that "X" isn't in our list, we can refute it by outputting "X".

The way I think about it is this: if we give Cantor our program up-front, he can run it to see what we're going to choose, then pick his 'move' accordingly (e.g. via diagonalization); if Cantor gives us his (self-contained) program up-front, we can run it to see what 'move' he's going to choose, and pick ours accordingly (e.g. via the identity function).

Both games are a win for whoever goes second.

Alternatives to the 'up-front' approach include:

- Interleaving or concurrent outputs, in which case there would be no winner: each time a number is added to the list, diagonalization extends its counter-example with another digit; each time the counter-example is extended, a number with matching prefix is added to the list.

- Interleaving or concurrent programs, with access to each others' source. I think the winner would be whoever has the most computing power (and can hence simulate their opponent further into the future).

[lisper]

> if Cantor gives us his (self-contained) program up-front,

Which he did. Diagonalization is an algorithm (and a trivial one at that).

> we can run it to see what 'move' he's going to choose

No, you can't, because one of the inputs to his algorithm is your algorithm. So you can't run his algorithm until you've committed to yours.

> Both games are a win for whoever goes second.

That's right. But Cantor has to go second. That's why his proof is correct.

[chriswarbo]

Sorry if I wasn't making myself clear: I'm not at all trying to refute Cantor's proof by diagonalization of the uncountability of the reals. There seem to be others in this thread who do take issue with it, but I don't.

It looks like my point's been misunderstood. I'm pointing out that the whole reason that Cantor's proof works (and it does work) is because we're forced to provide our complete list up-front. Or, for those who don't like the idea of 'writing down' something infinite, we must provide a 'description' or 'program' which uniquely defines/generates our list.

You say as much here:

> you can't run his algorithm until you've committed to yours.

Exactly. In Cantor's 'game', his counter-example (a real number not in our list) is generated with full knowledge of our list. Our list is generated with no knowledge of his counter-example.

That's Cantor's proof, and it is not what I'm talking about.

I'm talking about a different 'game', where the dependency is reversed: the "counter-example" is generated with no knowledge of the list; the list is generated with full knowledge of the "counter-example", and hence is able to refute it (by including the "counter-example" in the list).

This 'inverted' setup has two important differences from Cantor's setup:

1) We must replace the program/description of 'a list of reals' with a program/description of 'a function from a real to a list of reals'.

2) We must replace the program/description of 'a function from a list of reals to a real' with a program/description of 'a real number'

In particular, point (2) means that diagonalization is irrelevant in this setup (which I repeat is not Cantor's setup!). It is irrelevant because it doesn't have the right type: it is a function from a list of real numbers to a real number but there is no place for such a function in this alternative setup; instead, we need a plain old real number. This is what I was trying to get across by saying it must be 'written down up-front' (i.e. not after waiting for us to think of a list), or being 'self-contained' (i.e. not requiring an input/reference to our list).

I hope that makes it clear why the following refutations aren't applicable:

> > if Cantor gives us his (self-contained) program up-front,

> Which he did. Diagonalization is an algorithm (and a trivial one at that).

Given what I've said above, we see that diagonalization is not self-contained/provided-up-front/fully-written-down or any of the other phrases I've tried to use to get my point across. Yes, we can write a program for diagonalization, but such a program encodes a function, which has no place in this scenario (which is not the one in Cantor's proof!).

> one of the inputs to his algorithm is your algorithm

Again, the algorithm cannot take my/your/anyone's algorithm as an input, since it cannot take anything as an input, since it is not a function, since I am not talking about Cantor's proof by diagonalization of the uncountability of the real numbers. I am talking about a different situation, in which the "counter-example" is just a number, and hence cannot be provided with any inputs, whether they be algorithms or unicorns.

> > Both games are a win for whoever goes second.

> That's right. But Cantor has to go second.

By "both games" I mean Cantor's proof and this different situation. Cantor doesn't have to go second; that's my point! Cantor wins because he chooses to go second. If we choose to go second, then we will win, by constructing a list which includes the supposed "counter-example".

> That's why his proof is correct.

I know it is; but I've never claimed otherwise, and that is completely beside the point.

The point is that Cantor's proof isn't actually about the real numbers! Instead, it's about how some infinite structures (like "all numbers") are too rich to be completely captured by any particular finite representation (there will always be missing numbers). It suffices to use a countable infinity, like the computable numbers.

Alternatively, we can think of Cantor's proof as talking about computational resources: diagonalization is trivial to state, as you say, but it is computationally difficult to run. This is because it runs the list-generator as a subroutine (to find the digits), which can be made arbitrarily hard by generating the list in an arbitrarily complex way. Since diagonalization then adds 1 mod 10, it always ends up doing slightly more work than it takes to generate the list. Hence we can see Cantor's proof as statement that more powerful computers can always beat less powerful computers, assuming the code is all globally known, because the faster computers can simulate the slower ones to see what they'll do. That the essence of the second player always winning.

[lisper]

> Sorry if I wasn't making myself clear

You still aren't.

> diagonalization is not self-contained/provided-up-front/fully-written-down or any of the other phrases I've tried to use to get my point across

But it is. The fact that one of its inputs happens to be a function doesn't make it any less self-contined.

> The point is that Cantor's proof isn't actually about the real numbers!

It isn't just about the reals, but it is definitely about the reals. The claim is: there exist well-defined mathematical structures that cannot be put into a one-to-one correspondence with the naturals. The proof is constructive, with the reals as the canonical example. Cantor's proof is about the real numbers in the exact same sense that Turing's proof of the non-computability of the halting problem is about Turing machines.

[zelah]

I will just diagonalize forever before I give the set to Cantor. If he claims that he can diagonalize the set to generate a new number not in the set then I will say "Oh, yeah - I missed one. I wasn't really done after all. Give it back to me and I will add some more to it before you get your hands on it!". As you can see, Cantor will never get a list because I will never really be done generating it.

I could just give him the list and say that whatever he adds is precisely what I would have added had I continued. This is like an infinite lazy list in programming.

[lisper]

> Cantor will never get a list because I will never really be done generating it.

That would be true even if you weren't diagonalizing because the list is infinite. In fact, just a single item in the list is potentially infinite. So you can't generate the whole list regardless.

What you have to do is to produce an algorithm that takes any two natural numbers i and j as input and produces as output in finite time the j'th digit of the i'th number in the list. Because you have to produce your digit in finite time you can only diagonalize a finite number of times, so Cantor can always do you one better and produce a number not on your list.

[zelah]

Why is it that Cantor can do an infinite procedure of diagonalization but I can't? If he can diagonalize then I can too. Is it possible that Cantor's "algorithm" is not really an algorithm? Knuth says an algorithm must be correct and must also terminate.

Regardless, I have a lot to ponder.

[lisper]

Cantor is playing by the exact same rules that you are. His burden is: given an integer i, produce in finite time the i'th digit of a real not in your list. (He can't produce the whole thing in finite time because it's infinite, obviously.) He does this by using your algorithm to produce the i'th digit of the i'th row and adds one to it (mod 10).

[yongjik]

Okay, let me try to write these "algorithms" in a concrete term.

Assume that you have a way of generating a sequence R_1, R_2, R_3, ... of real numbers in [0, 1]. (For simplicity, let's just consider [0, 1], because it still has the same cardinalityas R.) You have your "algorithm":

    generate_digit(i, j):
        Somehow compute the j'th digit of R_i.
        return the digit

You are allowed to spend infinitely long time to return each digit. (That is, you can use constructions that are not even computable in finite time, as long as you can prove that given i and j, there is exactly one digit that satisfies your criterion.)

Cantor's objective is to defeat your algorithm by generating a real number not in the list. Similarly as above, it can be written as a function that returns the j'th digit, given j. Behold it in its full glory:

    defeat_indexing(j):
        digit = generate_digit(j, j)
        return (digit + 1) % 10

That's it.

[mcguire]

"the vast majority of them have an infinite number of digits to the right of the decimal point."

Technically, I believe all of the real numbers have an infinite number of digits to the right of the decimal point.

A vanishingly small portion of them have a repeating series of digits, such as 0. :-)

[logfromblammo]

Start with zero. Add an infinitesimal epsilon an infinite number of times. Now go back to zero and subtract the same epsilon an infinite number of times. You have now traversed all the real numbers.

The decimal representation of the epsilon has an infinite number of zeroes after the decimal point and before the last digit, which is '1'. So if you were to just chop off the leading zero and decimal point to make an equivalence with natural numbers, the epsilon is as much a representation of the natural number 1 as 0.1 or 0.01 or 0.001 or 0.0001 . Infinite real number equivalents to one natural number.

[kmill]

That infinitesimal is not a real number. To simplify a little, a real number is something which is the limit of a sequence of rational numbers. Or, given an error bound 1/n, you can write down a rational number within 1/n of the real number. Two real numbers are the same if the difference between their approximations converges to 0 as n gets arbitrarily large.

A number with infinitely many zeros after the decimal point is within 1/n of zero no matter the n. Therefore the number is zero.

This is like how 0.9999... is 1. The reason is that 1-0.999... is within 1/n of 0 no matter the n.

Suppose you had an infinitesimal epsilon (outside the real numbers --- this is fine, and people do this). How many times are you planning on adding it to itself? To get any actual real number, you are going to have to add it to itself well more than countably many times, though I'm not sure this makes much sense.

[logfromblammo]

Fine, then. Just use the smallest positive nonzero real number, instead.

Edit: I really hope I'm not the only one laughing.

[mturmon]

"...only one laughing..."

You are illustrating the reason that mathematicians generally disparage the concept of an "infinitesimal", when it's used as proof rather than conceptual aid. (Yes, I know about https://en.wikipedia.org/wiki/Non-standard_analysis)

Not only do you get wrong conclusions, you get tedious, hard-to-adjudicate arguments.

[jtc1983]

I agree with your thought, and that of the majority of mathematicians for many years, that infinitesimals are better construed heuristically than literally.

You mention that you know of non-standard analysis and indicate that it's irrelevant. Though I don't know why you think this, I agree with you. I just wanted to plug non-standard analysis as both mathematically interesting and also very useful. One can jettison the philosophical thought that NSA "vindicates" the historical use of infinitesimals (as I think we should), while still seeing NSA as the wonderful and deep piece of math that it in fact is.

[logfromblammo]

Thanks for your support, but I never said anything about non-standard analysis. I made one post in support of its parent, and people jumped on it to say how wrong I am, as apparently I accidentally stumbled over a sore spot in mathematics. I don't know why infinitesimals apparently aren't allowed, but the tone around here has convinced me to not care.

And now every post I have made in this thread tree is getting downvoted. So I'm out. Y'all can argue about nothing--and nearly-nothing--by yourselves.

[kmill]

What would that be?

If c>0 were smallest, then c/2 would be smaller and still positive!

[lisper]

> before the last digit, which is '1'

No. There is no last digit. That's the whole point. If there were a last digit your argument would be correct, but there isn't, so it's not.

[logfromblammo]

I don't see the problem with having a first digit and a last digit and an infinite number of digits in between.

Edit: Infinitesimal divided by two is infinitesimal, in the same way that infinity multiplied by two is infinity. So 0.000...0001 / 2 = 0.000...0001 . Infinitesimal multiplied by any finite number is infinitesimal. Infinitesimal multiplied by infinity is every number in the interval from infinitesimal to infinity. Or none of them. Or just one. Or all of them except one. Infinity just throws common sense out the window, then catches it as it tries to sneak back in through the chimney and sets it on fire. I'm not convinced that any sane person can adequately grasp the concept.

Don't confuse the limitations on mathematical notation with a limitation on imagination. 0.9 repeating is not exactly the same as the infinite sequence of ( 0.9 + 0.09 + 0.009 + ... ). The repeating notation indicates to use nine's complement for that portion of the fraction instead of ten's complement. 0.9 repeating is literally equal to one, by notation convention, but the infinite sequence of 9 digits is one minus infinitesimal, which is equal to one in every calculation that does not involve an infinity.

You have to have an infinite number of infinitesimals to make any number that isn't zero, but when you do that, you can get all of them.

[kmill]

> Don't confuse the limitations on mathematical notation with a limitation on imagination

Good luck proving or calculating anything.

You can define "infinitesimal/2 == infinitesimal", but nothing good will come out of it. A definition is no good unless it lets you do something.

Letting e=infinitesimal, you have e/2==e, so e==2e so 0==2e-e so 0==e. This definition is inconsistent with being able divide by non-zero integers and subtraction.

[logfromblammo]

That's not the definition, that's just what it does.

The definition of infinitesimal is "the smallest-magnitude number that is greater than zero". If you divide a finite number by infinity, infinitesimal is what you get, but don't go thinking that if you multiply it by infinity again that you will get the same number back, because you won't.

The floating point standard does not include a representation for infinitesimal, but an underflow now hints at its existence, instead of just going to zero.

It's probably easier to think of quantities like zero, one, infinity, and infinitesimal as the base vectors in mutually orthogonal dimensions. Their behaviors can be defined separately, such that whatever rules you choose for them can produce different types of math, perhaps useful for different purposes (or none beyond cranking out the dissertation), in the same way that slightly changing the Euclidian parallel lines property can produce elliptic and hyperbolic geometries.

[kmill]

> The definition of infinitesimal is "the smallest-magnitude number that is greater than zero"

That is hardly a definition. The real numbers are defined either as Dedekind cuts or as equivalence classes of Cauchy sequences of rationals. If you say "e is defined to be a real number such that e>0 and for all c>0, c>e", you would get a contradiction purely from the definition of the reals since "for all c>0, c>e" implies "e <= 0".

The only consistent scenario I can think is that you are actually extending the real numbers with a new element called "infinitesimal." Go ahead, but don't pretend that it is an element of the set of real numbers. Also, don't get the idea that there is some "true" set of numbers that we are trying to approximate with better accuracy. Modern mathematics has blown this idea wide open by introducing a wide array of mutually-inconsistent number systems.

> If you divide a finite number by infinity, infinitesimal is what you get

So you say. This would need to be part of the definition, or at least provable from it. Quoting Timothy Gowers, a mathematical object is what it does. How was I supposed to know that twice infinitesimal is equal to infinitesimal?

Elaborating extension: there is a way to add ("adjoin") an infinitesimal element to the real numbers. Let R(e) be the set of rational functions in e, a formal constant. For instance, 2+3e or 5e^2. I think there is a way to give R(e) a total order by saying 0<e<c for all positive real c. You also have things like 1/e=e^{-1} ("infinity") is greater than all real numbers. Don't make the mistake that R(e) is the real numbers, however.

> It's probably easier to think of quantities like zero, one, infinity, and infinitesimal as the base vectors in mutually orthogonal dimensions

In what way? In a vector space, I can divide by two, and I am apparently not able to divide infinitesimal by two (in the sense that e/2=e implies e=0).

> in the same way that slightly changing the Euclidian parallel lines property can produce elliptic and hyperbolic geometries

At least right now, there is a rather large difference: many interesting theorems follow from hyperbolic geometry.

What interesting things follow from asserting that there is a smallest-magnitude real number greater than zero? (If you say "I never said the number was real," then there has been no point to this discussion, because it started when you claimed the real numbers were countable by multiplying "infinitesimal" by other numbers.)

[lisper]

You can do that, but then the "last digit" doesn't behave the way you intuitively expect it to. For example, 0.0...1 is exactly equal to 0 for the same reason that 0.999... is exactly equal to 1. So you can't add them up to get a non-zero number.

The reason that adding numbers with a finite number of zeros before the first non-zero digit works to give you any number is that that carries go off to the left. But if there are an infinite number of zeros before the first non-zero digit then there will remain an infinite number of zeros after every addition. The carries can only "overcome" a finite number of zeros.

[kmill]

There's not a problem if you can answer this: What is 0.000...1 + 0.000...9? (The 1 and 9 are digits after infinitely many zeros.)

You are not allowed to say "undefined" if these are real numbers, because you are supposed to be able to add any two real numbers.

You are also not allowed to say 0.000...10 since that changes the place values.

Well, you are allowed to say 0.000...10 if you are imagining a real number is a pair (normal real number, natural number). If this is what you are imagining, then there's not a problem if you can answer this: What is the value of 0.000...1 divided by two?

[dragonius]

He's already answered you:

If you are going to allow this kind of notation, then

0.000...1 = 0 is equivalent to 0

0.000...9 = 9 x 0 = 0

0.000...1 + 0.000...9 = 0 + 0 = 10 x 0 = 0.000...10

(0.000...10) / 2 = 0/2 = 0

You're getting hung up on notation and missing the concept.

[kmill]

Neither has logfromblammo answered me nor am I hung up on notation. The notation is only incidental.

They are claiming that it is a well-defined number system with numbers "having a first digit and a last digit and an infinite number of digits in between." I say show that it works.

You are saying the way this works is to disregard the digits after the infinitely many digits. Sure, that would make a consistent system.

They seem to be saying something distinct from your interpretation. It's possible they mean to take the real numbers and adjoin a new "infinitesimal" element, for instance.

[yorwba]

> Now go back to zero and ...

You can't ever finish adding epsilon infinitely often, so everything after that is dead code. There is no "now" to speak of.

The same thing comes into play when you speak about an infinite number of zeroes after the decimal point and before the last digit. There is no last digit. You could have numbers with two "ends", but the so-called real numbers are different. They stretch infintely to the right, without end in sight.

There are also p-adic numbers, which stretch infinitely to the left, but they behave very different from real numbers. https://en.wikipedia.org/wiki/P-adic_number