[zelah]

I find Cantor's diagonal argument unconvincing.

The claim is that there are more real numbers in the range from zero to one than there are natural numbers. To see that this is false simply realize that you don't actually have to write a decimal point to specify the real numbers in this range. Without the decimal point these real numbers just become natural numbers. Can a rational person believe that there are infinite sequences of digits in the form of real numbers but not infinite sequences of digits in the form of natural numbers? The natural numbers are just an infinite sequence of finite numbers. If you believe n is a natural number then you must also believe that n*10 is a natural number. One more digit! There is always one more digit (that is what infinity implies). If there really are an infinite number of natural numbers then some of them must be of a transfinite number of digits or else you would be including numbers in the list more than once.

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. The only difference is our understanding of randomness. His procedure for finding a number not in the set may not seem very random but it might be as random as any other. A truly random coin could theoretically come up heads every time. The important part of his argument is that the infinite list of real numbers has no repeats. The diagonalization procedure similarly ensures that there are no repeats. On the one hand he claims the infinite set of real numbers exists. On the other hand he argues that the diagonalization that yields a number not in the set has not already been done. He takes away infinity and then gives it back!

There is only one infinity. It means "repeat". It is simply the interplay of finite state with process. You can think of it as an "infinite loop" in programming. To say that one infinity is smaller than another is to deny that the smaller is infinite. Infinite means without bound.

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

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

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

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

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

[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

[ColinWright]

So if I understand you correctly, you find it unconvincing, and therefore generations of mathematicians who study these things must all be wrong.

Perhaps you simply don't understand the argument in detail, and are relying on your intuition. And perhaps your intuition is faulty.

Which seems more likely?

So let me try to provide a better insight for you. Consider the collection of natural numbers, including 0. Call it N. We all agree that N, also described as the set of non-negative integers, is infinite.

Now imagine flipping a coin at time t_0, t_1, t_2, etc. If you're worried that this will take infinite amounts of time, we can suppose that each flip - because we are practised - takes half the time of the previous flip, so all the flips can be done in finite time. However, we're in the realm of Pure Mathematics now, chasing the puzzle for its own sake, and not worrying about practicalities.

So what might the result be? Well, you might get all heads, you might get all tails, you might get alternating heads and tail, in practice, of course, you'll get something that looks random.

Let's think about all the possible results of flipping the coin. All possible results. Let's let F be the set of all possible results obtained from flipping the coin are each of t_0, t_1, t_2, and so on. We can think of F as functions from N to {H,T}.

So we have F and N. Let's wonder if it's possible to have a function from N to F that hits every element of F. Suppose we can.

So we have m:N -> F, and for every f in F, there is an n in N such that m(n)=f.

Do you think that's possible? Because hundreds of thousands of mathematicians say that it's not possible.

[zelah]

It is possible. The inverse of m is called q. The function q takes an infinite sequence of coin flips and one by one changes every heads to 1 and every tails to 0. The infinite string of zeros and ones is then prepended with a 1 and interpreted as a transfinite natural number in binary notation. This will not take forever because each change will only take half as long as the previous one. A transfinite natural number can exist since there are an infinite number of natural numbers. If we stop at 1-bit numbers then the natural numbers are not an infinite set. Likewise, if we stop at 2-bit numbers then the natural numbers are not an infinite set. Our only option is to concede that transfinite natural numbers do actually exist and that they can be put into correspondence with all sequences of coin flips.

Hundreds of thousands of mathematicians are wrong.

[ColinWright]

So I asked: is it possible to have m:N -> F such that for every f in F, there is an n in N such that m(n)=f?

Your reply says yes, but then your construction does not do it. In particular you said:

> The infinite string of zeros and ones is then prepended with a 1 and interpreted as a transfinite natural number in binary notation.

But the set N does not have transfinite natural numbers, so q does not map F to N, it maps F to something else.

So I ask again, is it possible to have m:N -> F, such that for every f in F, there is an n in N such that m(n)=f?

[zelah]

>But the set N does not have transfinite natural numbers, so q does not map F to N, it maps F to something else.

How many natural numbers are there? How many bits does it take to represent the average natural number? If you believe the natural numbers do not include transfinite numbers then how do you pick a successor when counting? There are infinite picks to be made so some of the picks must be transfinite. What I am calling a transfinite natural number must exist in N because N is an infinite set.

Assume that N has only finite numbers in it but is itself an infinite set. Would you care to tell me which number (or numbers) are listed twice? But then it is not really a set!

[ColinWright]

> How many natural numbers are there?

Infinitely many, more than any finite number.

> If you believe the natural numbers do not include transfinite numbers then how do you pick a successor when counting?

Just add one.

> There are infinite picks to be made so some of the picks must be transfinite.

No, adding one to a finite number does not result in a transfinite number.

> What I am calling a transfinite natural number must exist in N because N is an infinite set.

The definition is that N is the smallest set that contains 0, and every successor of something already in N. Every finite non-negative integer is there, and nothing else - they are all finite.

> Assume that N has only finite numbers in it but is itself an infinite set. Would you care to tell me which number (or numbers) are listed twice?

No number has to be listed twice - just because each thing in the the set is finite, that does not mean that the set has to be finite. There is no contradiction in N being infinite, but all its elements being finite.

You appear to be using words in a non-standard manner. As such, quite simply, you need to be amazingly careful, or you will not be understood.

Certainly I don't understand you.

[gus_massa]

I think you are confusing "arbitrary long" with "infinite".

The leading/trailing zeros are confusing. So many digits are confusing. Let's pick an easy model: The "naïve roman numbers" (This is a made up name, not a technical name.)

Let's consider the set that has

I

II

III

IIII

IIIII

IIIIII

...

IIIIIIIIIIIIIIIIIIIIIIII

IIIIIIIIIIIIIIIIIIIIIIIII

IIIIIIIIIIIIIIIIIIIIIIIIII

...

...

i.e. all the strings that have a bunch of "I" characters.

Each element has a finite amount of "I". If you delete one of them you get a shorter string/number.

The set has strings that are as long as you want. If you print them in a 8pt times new roman font, you can pick one of them that will be long enough to wrap around the Earth, one of the is long enough to reach the Moon, ...

This is an infinite set, where each element has a finite amount of "I".

[dogecoinbase]

Hundreds of thousands of mathematicians are wrong.

No. No natural number has an infinite number of digits, and you are wrong.

If you weren't, of course, it would be easy to prove me wrong -- simply name the natural number to which the successor function is applied that results in a "transfinite" number, whatever that is.

[ColinWright]

Be careful, there are such things as transfinite numbers, and they are well-founded. They let us do wonderful things like transfinite induction, and to prove, for example, that Goodstein's Theorem is true, even though it's unproveable in Peano Arithmetic.

But transfinite numbers are not "natural numbers", they are not in the set N, they don't have infinitely many digits, and in the context of this thread, they are a red herring.

[dogecoinbase]

I'm fine with nonstandard models; my scare quotes on "transfinite" were more to emphasize that the term was being used without basis or definition.

[iamlucaswolf]

Phew, you have some courage, questioning the foundations of modern Mathematics in a place like this. But I can relate to your concerns about Cantor's argument. When I first heard it, it also felt artificial and unconvincing to me.

What helped me (as with many proofs and concepts in Math) was an image, a visual metaphor if you like.

Imagine a very, very large paper on which you place infinitely many dots in a grid. That's the infinity you were referring to, the infinity of a for-loop, discrete infinity. Here's the trick: you can always add more dots, say by making the distance between grid points half as small, which would quadruple the number of dots in your grid. But no matter how many dots you place on the paper, ho matter how fine your grid, there will always be holes (imagine "zooming in" on a square of four grid points). In fact, most of the paper will be empty!

The other kind of infinity, continuous infinity, does not have any holes. Every spot is covered. You could not add any grid point, because the whole paper itself is painted.

I'm not a "full-time Mathematician", so this view may be entirely wrong. But it helped me understand and appreciate Cantor. Perhaps it did the same for you.

Cheers!

[yorwba]

That's a very nice intuition, but for the wrong concept. What you have been describing is the difference between a dense set (almost no holes) and a nowhere-dense set (holes everywhere).

It turns out that there is a nowhere-dense set that is still uncountably infinite: https://en.wikipedia.org/wiki/Cantor_set

[waqf]

No, iamlucaswolf is correct, describing a countable dense set (the dyadic rational points) and an uncountable dense set.

[empath75]

> To see that this is false simply realize that you don't actually have to write a decimal point to specify the real numbers in this range. Without the decimal point these real numbers just become natural numbers.

There are no natural numbers with infinite digits, so this is not correct.

[mturmon]

Your answer is buried, which is too bad, because it is the one-sentence rebuttal to the construction above.

[Zaak]

> There are no natural numbers with infinite digits, so this is not correct.

Exactly. If you allow an infinite number of digits you wind up with the p-adic numbers, which are uncountable just like the reals.

[v64]

That's not how infinity works, which is why many results involving infinity are counterintuitive.

For instance, consider the natural numbers and just the even natural numbers. Intuition says these two sets must differ in size, because I took one set and removed half of its elements. But the mapping f(x) = 2x is a trivial bijection from the natural numbers to the even natural numbers, showing the two sets are of equal size.

Do you agree with the statement that two infinite sets are of different cardinality if it can be shown that no bijection exists between them? Let's consider an uncountable set that's simpler to imagine than the real numbers: the power set of the natural numbers, that is, the set of all subsets of N. It can be shown that no bijection exists between any set and its power set (Cantor's theorem [1]). Do you agree with that theorem? It can also be shown that a bijection does exist between the power set of N and R [2], implying they are of the same cardinality, and are both of a larger cardinality than N.

> There is only one infinity. It means "repeat".

Then what does it mean to you that infinite sets can be constructed that can be shown to have no bijection between them?

[1] https://en.wikipedia.org/wiki/Cantor%27s_theorem

[2] https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstei...

[deadmetheny]

The hubris in this thread is spectacular. Multiple people are demonstrating that your grasp of the math here is wrong, yet you keep arguing that no, the mathematicians must be wrong because you haven't grasped the idea. You could argue that only one infinity exists/actually matters in devland, but in mathematics it's absolutely not the case.

[moyix]

Based on your other replies, I suspect it's not worth engaging, but for anyone else reading, here's a great article by a math journal editor writing about all of the different attempts to disprove Cantor's diagonal argument he received and tracing out some common mistakes he saw:

http://www.logic.univie.ac.at/~ykhomski/ST2013/Hodges.pdf

[zelah]

Thank you - I have read this and do realize I am out of my depth.

[gus_massa]

[I'll try a non technical argument to convince you. It's also not a complete argument, so you must think about this for a while.]

> If you believe n is a natural number then you must also believe that n x 10 is a natural number. One more digit!

If you interpret the natural number in this way, the important property is that they have only a finite amount of "interesting" digits. Almost all their digits are zero.

You can define the set of number that have a finite amount of non zero digits. Let's call them the "Very Boring" numbers.

The set of the "Very Boring" numbers is infinite, but it's the same infinite that the Natural numbers.

You can extend this set to include the periodic numbers, for example 46.2222222222222... and 462.2222222222222... and 4622.2222222222222... ... Let's call them the "Boring" numbers. You still get the same infinity.

You can also 71.3535353535... and 713.5353535353... and 7135.3535353535... and all the periodic numbers. Now you have the "rational" numbers. You still get the same infinity.

The Cantor's diagonal argument fails with Very Boring, Boring and Rational numbers. Because the number you get after taking the diagonal digits and changing them may not be Very Boring, Boring or Rational.

--

A somewhat unrelated technical detail that may be useful:

Most of the times you don't prove that the cardinal of real numbers between 0 and 1 is a bigger infinity than the cardinal of the natural numbers.

I's much easier to consider the infinite strings of digits like "0.765653625367523765..." or "0.5265362556..." or "0.000073468763478..." and also the one with repetitions like "0.0006767000000..." or "0.0072257822222222...". This is essentially a copy of the real number, but in this copy "0.2999999999999..." is different from "0.300000000000000..."

This trick makes much easier to prove that the diagonal ´+1 in each one digit is not in the list. Then it's possible to fix the details and use the real numbers instead of the infinite strings of digits.

[zelah]

>I's much easier to consider the infinite strings of digits like "0.765653625367523765..." or "0.5265362556..." or "0.000073468763478..." and also the one with repetitions like "0.0006767000000..." or "0.0072257822222222...". This is essentially a copy of the real number, but in this copy "0.2999999999999..." is different from "0.300000000000000..." This trick makes much easier to prove that the diagonal ´+1 in each one digit is not in the list. Then it's possible to fix the details and use the real numbers instead of the infinite strings of digits.

What am I missing?

"0.765653625367523765..." could be assigned the transfinite natural number beginning "1765653625367523765..."

"0.000073468763478..." could be assigned the transfinite natural number beginning "1000073468763478..."

Transfinite natural numbers must exist otherwise you do not have an infinite set.

[zardo]

>Transfinite natural numbers must exist otherwise you do not have an infinite set

Transfinite

This word does not mean what you think it means. I'm not entirely sure what you think it means, but it's definitely not what it means to everyone else.

[relate]

Suppose I have the set F = { all integers x where x can be written with a finite number of digits }

Are you saying the set F is finite?

Or are you saying that the set F contains transfinite numbers?

[pitaj]

The difference is that `0.7656536...` is smaller than 0.7656537, whereas a similar number with every digit moved left of the decimal point has no bound.

[Cyph0n]

Yes they could, but note that these real numbers are all between 0 and 1. So the "infiniteness" of R is "higher" than that of N.

[throwawayjava]

It's OK not to be convinced by an argument, even a mathematical proof, and especially an informal proof.

But Cantor's argument is correct.

If you don't find a mathematical proof convincing even though all the trained mathematicians seem to believe the proof is correct, here's my advice. You should FIRST convert the proof into a sequence of valid deductions in a fixed logic. (If you cannot do this, you don't understand the proof/theorem; perhaps (re-)take a few mathematics courses.) If you can find a mistake in the completely formal proof, then you can convert that mistake into an informal explanation. If your disagreement boils down to a disagreement with a axiom in the formal system even though most mathematicians accept it as an adequate foundations, realize you're getting close to philosophy.

This advice is meant for people at the first phase in Terry Tao's hierarchy of mathematical maturity. So not great advice if you're a genius or a trained mathematician (read: people call you doctor).

> There is only one infinity. It means "repeat". It is simply the interplay of finite state with process. You can think of it as an "infinite loop" in programming. To say that one infinity is smaller than another is to deny that the smaller is infinite. Infinite means without bound.

But "modeling non-terminating loops in a computer program" is NOT the motivation for real numbers, so this foundational criticism of completing the rationals makes absolutely no sense.

[mmarx]

> But "modeling non-terminating loops in a computer program" is NOT the motivation for real numbers

Indeed Turing himself proved that there are non-computable real numbers.

[peteretep]

What a shame you're getting downvoted, simply because you're wrong.

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

If your argument is true, presumably you could write a simple program that would generate all the real numbers with a single, infinite loop?

I wonder how you'd manage to generate 0.1 and 1.0 with your scheme.

[andrewla]

I agree that the downvoting is unfortunate. I guess the assumption is that the post is simply a troll, which seems to be backed up by some of the down-thread replies. Even so, the original post just seems like a list of common misunderstandings about Cantor's notion of infinity and how it corresponds to the way that we use the word in colloquial use.

In defense of the GP, I think they were simply thinking of numbers in [0,1). If you write them backwards, it almost seems like it would work:

    1    ->  .1
    2    ->  .2
    ...
    9    ->  .9
    10   ->  .01
    11   ->  .11
    12   ->  .21
    ...
    3124 ->  .4213
    ...

Done!

Unfortunately, you are either stuck with the fact that some numbers (even simple rational ones) do not have a finite decimal expansion. In most formal proofs of the diagonal theorem, we use the infinite representation without trailing 0s (using trailing 9's instead) to force uniqueness, which makes it even trickier.

Or you're stuck trying to assume that there are natural numbers with an infinite representation, so the decimal representation of the rational number 1/3 would correspond to an actual natural number.

[jerf]

"What a shame you're getting downvoted, simply because you're wrong."

It's not simply because of being wrong. Being wrong is a hazard to your karma, yes, even sometimes just asking questions can be a hazard (which I dislike and do what little I can to fight, but it's still obviously true). But there's a much bigger hazard being invoked here.

[bllguo]

That is extremely disingenuous of you. He's being downvoted for his massive arrogance.

[weichi]

You need to write down the 1-1 correspondence you are proposing. Don't describe it in words, actually start writing the natural numbers in one column and the corresponding reals in the other. When you do this, you will find either that the 1-1 correspondence that you are envisioning doesn't actually work (i.e., it isn't 1-1), or that it does work ... but in that case, Cantor's diagonalization argument can be applied to it.

[0xBABAD00C]

I find that people who question Cantor's (obviously correct) theorems and concepts seem to share commonalities with people questioning Einstein's (obviously correct) theories and concepts. Let's just say if Cantor's last name was Rasmussen and the infinities weren't indexed Alephs, I wouldn't expect people to get their panties in a bunch over abstract math, and care so much about proving him wrong, a fraud, a lunatic, etc (without even a basic understanding of the subject).

It hits the subconscious strings of jealousy and mistrust of the majority towards the more successful almost-the-same-but-not-quite minority so very perfectly, especially when the subject matter put forward by the minority is cryptic or unintuitive at the first glance...

Just a theory :)

[jakef]

The natural numbers are each finite. In set theory, the standard way they are defined is that they can be constructed by assuming the existence of the empty set (or 0) and assuming that if you "insert a set into itself" the result will be a set. (So they can be thought of as {} = 0, {{}} = 1, {{}, {{}}} = 2, etc.).

The natural numbers are simply the (smallest) set that contains the empty set and is closed under this "insert a set into itself" operation (successor). It only contains finite sets since the successor operation will never turn an finite set into an infinite set.

The existence of this set of ALL natural numbers (an infinite object) relies on an axiom, the axiom of infinity.

There is no transfinite natural number.

[bmh_ca]

> There is only one infinity.

Fractions are countable. Real numbers are not.

In other words, fractions, integers, positive integers all belong to the set of countable infinities, meaning there is an isomorphic function that bidirectionally maps each positive integer (the count) to every item in the target, countable infinity.

There is no isomorphism between real numbers and any countable set. If you create one before you are 40, you will get a Field Medal.

The isomorphism and the distinction between sets that have them and sets that do not has proven useful.

You could think of infinity as one concept, but it is usefully divided into countable and uncountable versions.

[littlestymaar]

The error in your reasoning lies here :

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

This is wrong because irrational numbers have an infinite number of digit, if you remove the «dot» you end up with a number infinitely long, which is not a natural number. □

Edit: the set of natural numbers is infinite, which means it can contain arbitrarily big numbers, yet it doesn't contain «numbers» with an infinite amount of digits.

[myren]

"If there really are an infinite number of natural numbers then some of them must be of a transfinite number of digits or else you would be including numbers in the list more than once."

Theorem: There are no infinite natural numbers.

Proof: By Induction:

Induction Start: 0 is finite.

Induction Step: If n is finite then n+1 is finite.

The principle of induction then tells us: All natural numbers are finite.

If all natural numbers are finite, then there are no infinite natural numbers.

End of proof.

[cjslep]

There is one English definition of infinity, but when applied to ordinals ("degrees of freedoms"), you get different mathematical concepts of infinity.

Vsauce's explanation is approachable: https://youtu.be/SrU9YDoXE88

[zelah]

Thanks - that was very fun!

[haddy6235]

Why do mathematicians normally not distinguish between numbers for counting and numbers for measuring (length, volume, etc)? They are fundamentally different, and conflation makes many arguments hard to grasp.

[kmill]

I think I figured it out: you must be one of the aliens predicted by the downward Löwenheim–Skolem theorem!

If we could have a model of set theory (a set1 of all set2s, where a set1 is a set in our set theory and a set2 a modeled set, like an interpreter), which is necessarily infinitely large, then the downward Löwenheim–Skolem theorem implies there is a model that is only countably infinite. There is a model of the real numbers in there, so from our point of view, the real numbers are countable! Though from the model's point of view, Cantor's diagonal argument still works, and they are not countable!

My theory is that you are looking at our real numbers and thinking they are countable because you have a much more powerful set of natural numbers than the rest of us. Unfortunately for you, your bijection between our reals and your naturals does not carry over to our set theory. You should find, however, that you do not have a bijection between your reals and your naturals.

One problem with this is that Gödel's incompleteness theorem implies that if we ever had a model and could prove it was a model, then set theory would be inconsistent.

More seriously, Cantor's argument as usually given is not Cantor's original argument. He originally did something involving nested closed intervals, but it was simplified to listing out the digit expansions of a list of real numbers.

I am partial to the following argument: suppose there were an invertible function f between N and infinite sequences of 0's and 1's. The type of f is written N -> (N -> Bool) since an infinite sequence of 0's and 1's is a function from N to {0,1}. Let g(n)=not f(n)(n). This is a function N -> Bool. Since f is invertible, let finv be the inverse f : (N -> Bool) -> N. Then finv(g) is a natural number. Plug this into g:

    g(finv(g)) = not f(finv(g))(finv(g))
               = not g(finv(g))

Uh oh, the value of g at finv(g) is not whatever its value is. Something must be wrong: it could be there is no set of natural numbers or booleans (unlikely), that g is not definable (but it is a simple expression of f, and not even recursive; unlikely), or that there is no such function f (this is the only assumption remaining, so there must not have been an f that is a bijection).

Notice there was nothing special about N in this argument. It could have been a finite set, an infinite set, or even the real numbers, and we still would have concluded there is some value at which g is not its own value!

It is possible to prove that there are at least as many real numbers as there are sequences N -> Bool using infinite series. It is also possible to prove there are no more real numbers than there are such sequences.

[myren]

I don´t think this is an alien that applied downwards Löwenheim-Skolem to the reals. Rather I think this is an alien which applied upwards Löwenheim-Skolem to peano arithmetic. I think this because the alien talks about infinite natural numbers, aka non-standard natural numbers. It has used upwards Löwenheim-Skolem to get a model of peano arithmetic that has the cardinality of the continuum, and then there is of course a bijection between our reals and the thing that it calls the natural numbers. I see no sign that it´s using a non-standard model of the reals, but lots of signs that it´s using a non-standard model of the naturals.

[kmill]

The power of modern logic is that we can make predictions like this!

I wasn't sure whether the Löwenheim–Skolem alien was just translating things into our set theory for our sake, but I think your proposal is more likely.

[SubiculumCode]

Congratulations. You hijacked a thread.