What's up with the Continuum?

Factual Questions
21

There’s a reason category theory is often referred to being “abstract nonsense.”
This is the kind of stuff that graduate students of Mathematics have to deal with on a continual basis, even without having to talk about actual functors (it doesn’t surprise me Firefox doesn’t think that’s a word) and such. I’m greatly amused by seeing someone write this kind of thick abstraction in what amounts to “plain English” when even use the word “function” in this case might not be fully understood by the OP.

To the OP:

I think you have a misunderstanding of some very basic concepts in real analysis and mathematical logic. You clearly are interested in the subject matter, but it appears you have not taken any college mathematics outside of calculus and linear algebra; usually the first class one takes beyond those deals with the logical foundation of mathematics and (where I took it at least) the basics of advanced analysis and algebra, the two basic lines of pure mathematics scholarship. “A little knowledge is a dangerous thing”, and you seem to have been told bits and pieces of the result and only a tiny bit of the logic behind those results.

Godel, Escher, Bach by Douglas Hofstadter, of which I have only read extracts in a HS class and have always wanted to read more, probably provides a great wealth of information in this sort of mathematics that is aimed at a reader who does not have the scholastic experience that grounds most students that encounter these things and contains a great deal more. The parts of the book surrounding Godel and his famous incompleteness theorem probably contain a low level argument about the portion of Cantor’s work that interests you.

I had thought this thread might have been about the Continuum Hypothesis: “There is no set whose cardinality is strictly between that of the integers and that of the real numbers.” That statement has been proven to be independent of the rest of the standard (Zermelo–Fraenkel) axioms of set theory. The whole business of what can and can’t be proven in this field of mathematics is quite intriguing.

22

@Thudlow
How is that different for the counters as they approach Aleph-nought? Always room to generate one more. So how to imagine the table?

23

Here’s one “mistranslation”: The “continuum,” as mathematicians use the term, does not refer to Cantor’s hierarchy of infinities, but to the cardinality of the set of real numbers.

(And as glowacks said, the Continuum Hypothesis is the hypothesis that this cardinality is the “next-largest infinity” after Aleph-nought. I too thought the thread was going to have something to do with that.)

24

You may (or may not) find this article enlightening. It’s a good layman’s description of Cantor’s diagonal argument and related topics that I found and linked to the last time this sort of thing came up here.

As for “how to imagine the table,” it may be that you are being led astray by relying too much on imagination. From the standpoint of mathematical “existence” (which should not be confused with existence in the “real world”!), if you can prove logically that something does (or cannot) exist, it doesn’t matter whether or not you can imagine it.

25

As others have said, the imaginary table is just a visual aid. It helps us think in more immediate terms about some of the properties of the abstraction, but it isn’t the abstraction itself. Why introduce this idea of “counters?” Cantor supposes a bijection from the naturals to the reals in order to prove that one can’t exist; you don’t have to “iterate” over the members of the hypothetical bijection in order for the proof to be valid.

For example, suppose I hypothesize a bijection from the integers to the integers. It would have to be infinite, right? I could never construct a list of the members of the bijection – it would take infinite time! But not only can we use such an idea as the foundation of a proof, in this case it’s easy to come up with a real, concrete example of such a bijection, such as f(x) = x + 1 for any integer x.

26

@glowacks

Well you’re right on about my education and understanding. My apologies those posters I’ve “ignored”. It’s merely my ignorance;) of mathematics that makes me so.

How come Cantor’s list is presented in random order?

27

There’s no requirement for “random order”. The diagonalization proof constructs, from any (countably long) list of (countably long) digit-sequences, a digit-sequence which isn’t in the list.

28

The point is that you can’t imagine such a table that includes all the reals. If you could, then the reals would be countable (since the first member of the table would map to 1, the second to 2 and so on). So if you can convince yourself you can’t imagine such a table, then I’d say you agree with Cantor.

29

If they were in ascending order, as I said in my initial post, no matter how big you made the list, you’d see nothing but 0’s in the upper left hand corner (in any base) and if in descending order you’d see nothing but 9’s in base 10.

As you worked down the diagonal you could of course change the 0’s to other digits and produce a new number as you go but you’ll never get beyond 0’s. What would that say.

I think it makes clear why the list must be shuffled.

30

@simplico

Cantor starts by assuming such a table is imaginable and then proves that it is not. To that extent I do agree with him. I just can’t get on board with his assumption.

31

I don’t think that’s clear at all. Sure, if you arranged the imaginary list that way, you’d see nothing but zeroes starting from the top left. Why is that a problem? What makes a random assortment of digits any more meaningful than zeroes?

With respect to the diagonalization argument, it makes no difference what digits you see, as long as you can see that it’s possible to construct a countably long sequence that isn’t in the table.
ETA:

No! He does not assume that such a table is “imaginable.” Whether or not it’s imaginable depends on the individual imagination, but it’s completely irrelevant to the proof. Cantor assumes that the bijection exists, and then goes on to show that this very assumption contradicts itself. That’s the whole idea behind a proof by contradiction.

32

What you’re saying is “Obviously, a ‘non-shuffled’ list can’t possibly contain all the possible digit-sequences. It could only contain the sequence of all 0s, repeated forever.”

Alright, sure. But no matter; Cantor’s proof goes even further and shows “Actually, no matter what, ‘shuffled’, ‘non-shuffled’, whatever, we can produce from the list some digit-sequence not in it.”. So there’s no problem in applying the diagonalization method even starting with a ‘non-shuffled’ list; you get the same result in this case as you would get if you started with a ‘shuffled’ list (whatever that would mean): either way, you get a digit-sequence not in the list.

Anyway, though, it may be best not to think of these as “lists” at all, which may bring about misguided intuitions. It may be best to think in terms of functions (aka, operations, mappings, procedures, morphisms, whatever you want to call them) instead. That is, you don’t have to think of it as “A list which exists all at once” if that’s somehow tripping you up; the argument still works even if you think of it as “A procedure for generating these things bit by bit”.

33

@stealth

Suppose we extended the number of decimal places toward infinity. For each decimal place we add in (base 10) we increase the necessary counters by a factor of ten. As we add decimal places, this table becomes a ribbon then a string and then? How do you draw a diagonal without somehow “squaring things up”?

34

You persist in trying to visualize the proof completely in terms of this table, which (as I mentioned earlier) is what is tripping you up. Take the next step and picture no table, but instead a bijection between the naturals and reals.

And you still persist in visualizing the process as a dynamic and growing thing. It’s not; it’s just a bijection that’s already there, by assumption–an assumption which necessarily leads to contradiction.

You won’t get anywhere in understanding if you ignore this advice that people are trying to give you.

35

We agree that between any two naturals there exists an infinity of reals and therefore there is no bijection between the naturals and the reals. This does not prove to me that there is something beyond Aleph-nought.

36

This does not, in itself, establish that there is no bijection between the naturals and the reals. For example, it’s also true that between any two naturals there exist infinitely many rational numbers. However, there is a bijection between the naturals and the rational numbers.

The way the natural numbers are conventionally ordered within the reals or whatever else is entirely irrelevant to the question as to whether a bijection exists. Bijections have nothing to do with order structure.

What does “there is something beyond Aleph-nought” mean to you? You apparently agree that there is some collection which contains all the natural numbers and more, but which cannot be put in bijection with the natural numbers. In standard mathematical language, this is all “there is something byeond Aleph-nought” means.

37

Sure.

This does not follow at all. For example, between any two naturals there exists an infinity of rationals…however, there IS a bijection between the naturals and the rationals.

38

@everyone: focusing too much on some dynamic vs. static distinction is a red herring. It’s perfectly well plausible to understand the diagonalization argument even while “visualizing the process as a dynamic and growing thing” (see below).

@adhay: you said it’s your ignorance of mathematics which causes you to ignore some posts. But I think the best way to clear up your ignorance is to read some of those posts you’ve ignored, and I don’t think there are any posts in this thread which are beyond a novice layman’s ability to read. Could you please read and respond to this post, at least?

Let us put the argument like this: Bob comes up to you and says “Let’s play a game”. The idea behind the game is that Bob will win if he can craft a certain surjection, but you can win by showing that Bob hasn’t actually made a surjection.

The way it works is that there are four turns:

On turn 1, Bob gets to make up a square of colors. That is, Bob writes down some rules for how to answer questions of the form ‘What color (black or white) should go in Bob’s square at column #X and row #Y?’. Whenever someone asks a question like that, Bob’s rules should tell us a specific color to draw at the corresponding column and row of his square. In this way, if we liked, we could fill in the square bit by bit with colors, though, of course, it may be impossible to ever actually finish filling all of it in.

On turn 2, you get to make up a sequence of colors. That is, you write down some rules for how to answer questions of the form ‘What color should go in adhay’s line at column #X?’. Whenever someone asks a question like that, your rules should tell us a specific color to draw at the corresponding point in your sequence. In this way, if we liked, we could write out your sequence bit by bit, though, of course, it may be impossible to ever actually finish writing out the whole thing.

On turn 3, Bob tries to show that your sequence is actually one of the rows of his square. Bob does this by picking some row number and announcing “Bob’s row is #such-and-such”.

On turn 4, you try to show that Bob has failed. You do this by picking some column number and announcing “adhay’s’s column is #such-and-such”.

After turn 4, all that’s left to do is figure out the winner: we’ll follow Bob’s rules to figure out which color goes in Bob’s square at Bob’s row and adhay’s column. We’ll also follow adhay’s rules to figure out which color goes in adhay’s sequence at adhay’s column. If these two colors come out the same, then Bob wins. If they come out different, then adhay wins.

Would you be willing to play such a game, even if there was a thousand dollars riding on it?

Of course you would; that’s easy money! You can guarantee a win: on turn #2, just use the rules “The color in adhay’s sequence at column #X is the ‘opposite’ of the color in Bob’s square at column #X and row #X”. And on turn #4, pick adhay’s column number to be the same as Bob’s row number. The color that comes from adhay’s sequence here will be the opposite of the one that comes from Bob’s square here, and so you’ll win the thousand bucks.

Cantor’s theorem is nothing more than the assertion that you can guarantee a win at this game, and the diagonalization proof is nothing more than the above strategy for doing so.

Does that all make sense? Do you have any questions about or qualms with it?

[I know I haven’t mentioned real numbers anywhere above. That’s ok; like I said, you should forget about real numbers for now, they’re just a distraction and aren’t what the diagonalization proof is directly about]

39

Aleph-nought is defined as the smallest infinite integer. I suppose this implies there are larger infinities but I just don’t get it. To my naive thinking, infinity is infinity.

I suppose this is off topic but what do think of this?

http://homepage.mac.com/ardeshir/ArgumentAgainstCantor.html

40

I’ll assume you meant to say “cardinality” instead of “integer”. Aleph-nought is not an integer; integers are (by standard definition) finite in magnitude.

You can say that if you like. But that just means you’re using the language of “infinity”, “larger”, etc., in a different way than the way we are discussing. When mathematicians say “There are larger infinities than aleph-nought”, all they mean by this is “There are collections which are infinite but which contain infinite subcollections with which they cannot be put in bijection”. If you agree with this latter statement (and you’ve indicated that you do, since you’ve said, for example, that the naturals and the real numbers cannot be put in bijection), then you don’t actually disagree with mathematicians who say “There are larger infinities than aleph-nought”, except to the extent that you perhaps wish they would not word it that way.