What's up with the Continuum?

[adhay]

Spoiler: If You’re not into math this is not for you.

Still with me? I assume that you’re familiar with Cantor’s Diagonal Proof that the real numbers outnumber the counting numbers which establishes the “reality” of a hierarchy of infinities known as the Continuum.

The canonical start is with a “complete” table of of “all” the real numbers, for obvious reasons randomly shuffled. Were they not shuffled, it would be zeroes forever up there in the nw corner of the table. That and the fact that the known universe couldn’t contain a “complete” representation in nanotype of a single real number, much all of them, makes me seriously doubt the proof. The table is beyond imagination.

So this yet another attempt at disproof:

Cantor moves the counting numbers toward Aleph-nought and when he impossibly reaches it finds that there is infinity of reals between each counting number. Of course.

I think it all gets down to representation.

In any list of real numbers taken to b decimal places where b is the number just smaller than Aleph-nought, all reals are represented to b places. What happens at Aleph-nought is anybody’s fantasy.

Cheers.

[Indistinguishable]

There is no requirement that that you start with a randomly shuffled list or any such thing.

Forget the continuum and lists for a moment, and let’s just talk about Cantor’s diagonalization proof in a slightly more transparent form instead:

Theorem: For any function L which takes in natural numbers as input and produces natural number-indexed sequences of decimal digits as output, there is some such sequence which is not in the range of L.
Proof: Consider, say, the sequence whose k-th digit is 0 if L(k) is odd and 9 if L(k) is even. Clearly, for each k, the k-th digit of this sequence differs from the k-th digit of L(k); thus, for each k, this sequence is different from L(k); thus, this sequence cannot be equal to any sequence in the range of L.

Do you see anything wrong with this theorem and proof?

[Indistinguishable]

Ack, I miswrote the above. Let me rewrite it, and change some wording while I’m at it:

Theorem: For any function L which takes in natural numbers as input and produces natural number-indexed sequences of decimal digits as output, there is some such sequence which is not in the range of L.
Proof: Consider, say, the sequence whose k-th digit is 0 if the k-th digit of L(k) is odd and 9 if the k-th digit of L(k) is instead even. Let’s call this sequence S(L). Clearly, for each k, the k-th digit of S(L) differs from the k-th digit of L(k); thus, for each k, S(L) is different from L(k); thus, S(L) cannot be equal to any sequence in the range of L.

Do you see anything wrong with this theorem and proof?

[Saint_Cad]

@Indistinguishable

Ack, I miswrote the above. Let me rewrite it, and change some wording while I’m at it:

Theorem: For any function L which takes in natural numbers as input and produces natural number-indexed sequences of decimal digits as output, there is some such sequence which is not in the range of L.
Proof: Consider, say, the sequence whose k-th digit is 0 if the k-th digit of L(k) is odd and 9 if the k-th digit of L(k) is instead even. Let’s call this sequence S(L). Clearly, for each k, the k-th digit of S(L) differs from the k-th digit of L(k); thus, for each k, S(L) is different from L(k); thus, S(L) cannot be equal to any sequence in the range of L.

Do you see anything wrong with this theorem and proof?

Yes.

Don’t use 0s and 9s otherwise your proof can fail since 1.00000… = 0.999999. Thats why the proof is taught with digits other than 0 and 1.

[Indistinguishable]

My proof of the theorem I stated won’t fail, because I talked about “natural number-indexed sequences of decimal digits” rather than “real numbers”.

That having been said, even if one does want to relate such sequences of digits to real numbers (say, as decimal expansions giving a number in the interval [0, 1]), it’s worth noting that no two distinct decimal digit-sequences composed solely of 0s and 9s both represent the same number.

[Indistinguishable]

But, hell, since I really don’t care about talking about real numbers, and they’re probably just confusing things anyway (and, re-reading the OP, it seems to be suffering from a bit more misinformation and confusion around than I realized), let’s kick things up a bit in abstraction, which may or may not help the OP see things better:

Forget, for a moment, everything you’ve ever heard about Cantor, hierarchies of the infinite, aleph-nought, whatever. I mean it. Think of the following as entirely unrelated to such things, and approach it from scratch.

Suppose F is a function from As to (functions from As to Bs), while D is a function from Bs to Bs. Suppose also that D(x) is never equal to x [that is, D’s output is always different from its input].

[For example, maybe As are cities, Bs are distances, F(x) is the function which sends input y to the distance from x to y, and D(x) is x + 5 miles. Or maybe As are positive integers, Bs are rational numbers, F(x) is the function which sends input y to the output x/y, and D(x) = 2/x. Or whatever; the particular situation doesn’t matter, we’re just speaking abstractly].

I am going to prove, just from this abstract setup, that there is some function from As to Bs which is not in the range of F.

Proof:

From F and D we can define a new function G, using the definition G(x) = D(F(x)(x)).
[In case it’s not clear what that means, it means "G is the function from As to Bs which sends an input x to the output determined as follows: First, apply F to x to obtain a function from As to Bs; then apply, that function to x to obtain a B. Then, apply D to that value to obtain the final output.]

Great. But so what? Is there anything special about G?

Yes, there is: note that G(x) is always different from F(x)(x) [since the output of D is always different from its input]. But this means G itself must always be different from F(x) [since these two functions give different results on the input x]. And so, since G cannot equal F(x) for any x, we’ve shown that G cannot be in the range of F.

Thus, we’ve exhibited an example of a function from As to Bs which is not in the range of F. Q.E.D.

Just considered in isolation, not as any kind of statement about sizes or what have you, does the above make sense?

[Exapno_Mapcase]

Remember what I said in the other thread about the horrors translators face with every word?

You’re trying to translate math into words without an adequate understanding of the math. You can’t sling around words alone and say that math is disproved. It never works.

You need a better translation. There are any number of superb books on Cantor and his infinities that will try to walk you through their complexities in layman’s terms. You should find at the end that the table is not beyond imagination. It makes perfect sense when approached correctly. If it doesn’t now, then you need to increase your understanding of the basics.

[Capt.Ridley_s_Shooting_Party]

@adhay

That and the fact that the known universe couldn’t contain a “complete” representation in nanotype of a single real number, much all of them, makes me seriously doubt the proof.

This is a rather strange objection. If you accept the existence of real numbers, and accept the ability to multiply them (which, from a computational viewpoint, surely requires inspecting every digit of each number—possibly infinitely many of them!), why would you object to being able to enumerate the set of real numbers?

[adhay]

Thanks for showing up guys. Here’s another quick shot at it.
Cantor essentially presents a snapshot of an ever expanding table, presumably taken when the counter has (impossibly) just reached Aleph=nought. Using a clever diagonal proof, he shows that in fact that the counter had not reached Aleph-nought. Convinced that it had, however, Cantor had no choice but to posit an infinity greater than and containing Aleph-nought. Once he started in this direction, the Continuum was a foregone conclusion.

[adhay]

@Capt
You can only multiply reals taken to a finite number of decimal places. Try a “full” decimal representation of Pi X 2.

[ultrafilter]

@adhay

@Capt
You can only multiply reals taken to a finite number of decimal places. Try a “full” decimal representation of Pi X 2.

Do you agree that it’s possible to multiply 1/2 by 1/4?

[Indistinguishable]

@adhay

@Capt
You can only multiply reals taken to a finite number of decimal places. Try a “full” decimal representation of Pi X 2.

It isn’t any harder than a full decimal representation of Pi.

[Exapno_Mapcase]

@adhay

Cantor essentially presents a snapshot of an ever expanding table, presumably taken when the counter has (impossibly) just reached Aleph=nought. Using a clever diagonal proof, he shows that in fact that the counter had not reached Aleph-nought. Convinced that it had, however, Cantor had no choice but to posit an infinity greater than and containing Aleph-nought. Once he started in this direction, the Continuum was a foregone conclusion.

Not in our reality.

Cantor's diagonal argument

The diagonal argument was not Cantor’s first proof of the uncountability of the real numbers; it was actually published much later than his first proof, which appeared in 1874.

Even that Wiki page should reveal how bad your description of the diagonal argument is. It may be too condensed to explain to you why that is so. So I go back to my earlier suggestion.

[adhay]

@Ultra

You can multiply reals that expand to only 0’s after some finite number of decimal places.

1/4 = .250000000000 …

[Cabbage]

@adhay

Thanks for showing up guys. Here’s another quick shot at it.
Cantor essentially presents a snapshot of an ever expanding table, presumably taken when the counter has (impossibly) just reached Aleph=nought. Using a clever diagonal proof, he shows that in fact that the counter had not reached Aleph-nought. Convinced that it had, however, Cantor had no choice but to posit an infinity greater than and containing Aleph-nought. Once he started in this direction, the Continuum was a foregone conclusion.

I think part of your confusion lies in perceiving the idea behind the proof as being a dynamically growing table. It’s not. For that matter, the table is simply a tool to help in the visualization; it’s not an essential component of the proof.

The idea behind the proof is that you hypothesize a static bijection from the natural numbers to the reals, and by “static” I simply mean it is already a well-defined and well-constructed function. It’s not simply a matter of waiting around for some period of “time” until you see, for example, which real number one googol gets mapped to. That’s all “instantaneous”, simply based on the assumption that such a bijection exists in the first place.

The power of the proof is that this assumption (that there’s a bijection between the naturals and the reals) always leads to contradiction–the diagonalization always produces a real number that is excluded from the function, hence such a bijection could never have existed in the first place.

[ultrafilter]

@adhay

@Ultra

You can multiply reals that expand to only 0’s after some finite number of decimal places.

1/4 = .250000000000 …

What’s so special about base ten? Why not work in, say, base 7, where 1/7 is represented by .1 and 1/4 doesn’t terminate?

ETA: I’m going to go ahead and spoil the punchline. A real number is not the same thing as its representation, and I am perfectly capable of multiplying any two real numbers as specified here.

[adhay]

@Ultra
Obviously a real number is not the same thing as its representation which is my point. In base 7, the best you can do for 1/4 is to take it to some number of septimal? places.

[Indistinguishable]

ultrafilter’s point is that it sounds like you’re saying that the question of whether 1/7 * 2 is well-defined or not depends on some choice of a notation system for how to represent these numbers. So that this is well-defined if we use base 7 notation, but not well-defined if we use base 10 notation. But that is not in keeping with what mathematicians generally mean when they say things like “1/7 * 2”.

That having been said, if you want to distinguish between “Can carry the calculation out to as finitely many decimal places as you like” and “Can carry the calculation out in toto”, fine, knock yourself out; doesn’t matter to me, or, really, to Cantor’s proof, either. What would your response be to posts #3 or #6?

[Thudlow_Boink]

@adhay

The canonical start is with a “complete” table of of “all” the real numbers, for obvious reasons randomly shuffled.

No: quite the opposite. Cantor says that you can’t have a complete table of all the real numbers. Because if you could, it would always be possible to generate a real number that wasn’t on the “list.”

[Kimmy_Gibbler]

@Exapno_Mapcase

Not in our reality.

Cantor's diagonal argument - Wikipedia

Even that Wiki page should reveal how bad your description of the diagonal argument is. It may be too condensed to explain to you why that is so. So I go back to my earlier suggestion.

No. The point is, like Indistinguishable, I was going to give the set-theoretic proof of the cantor theorem (the impossibility of mapping from set S onto its power set P(S)). But then I realized, “Either adhay will ignore it or come up with some cockamamie objection originating in a gross misunderstanding.” So, after typing up the proof, I just hit my back button and let it go.

As it happens, Indistinguishable outlined the set-theoretic proof and adhay has promptly ignored it.

You’re on a fool’s errand.