Could my infinity be bigger than your infinity?

Factual Questions
61

Yeah, Achernar, that’s pretty much the idea, just a few clarifying points:

I’ve seen a fair number of books/websites that get the continuum hypothesis wrong. We do know that the power set of the natural numbers (or integers) has the same cardinality as the set of reals; this cardinality is 2^aleph-null, or what we commonly call c. What we don’t know is whether this is aleph-one, or aleph-two, or whatever.

Yeah, Aleph-1 can be shown to exist. Take the ordinals; Aleph-1 is the smallest ordinal with uncountably many predecessors (it is the supremum of all the countable ordinals).

Similar to the above, Aleph-2 is the smallest ordinal with more than Aleph-1 predecessors (aleph-2 is the suprememum of all ordinals with cardinality Aleph-1). Or, in other words, take a set of cardinality aleph-1. How many ways can you well order this set (up to order isomorphism)? Aleph-2 ways. (This last comment requires the well-ordering principle (axiom of choice); however, the axiom of choice is not necessary for the existence of aleph-1, aleph-2,…, since we can construct the ordinals without the axiom of choice).

Similarly (going back to aleph-1), aleph-1 is the number of ways a countably infinite set can be well ordered (up to order isomorphism).

Right. There is a subset of the reals with cardinality aleph-1 no matter what (if we’re assuming axiom of choice). If CH is true, we can actually construct such a subset (the set of reals themselves would be a subset of the reals with cardinality aleph-1). If CH is false, the cardinality of the reals is greater than aleph-1, and (by the axiom of choice) we can get a subset of the reals with cardinality aleph-1, but we can’t construct such a subset.

Actually, this isn’t true, and DrMatrix’s correction isn’t quite correct, either. It should be:

If we assume that CH is false, then C = Aleph-alpha for some ordinal alpha > 1. In fact, we can assume that alpha = any ordinal and still be consistent, provided that Aleph-alpha has cofinality greater than Aleph-Null.

I don’t know if you know the definition of cofinality of a cardinal, so I’ll try to explain it here. Take some cardinal (call it beta), beta can be identified with some set of ordinals–namely, the set of ordinals with cardinality beta; in fact, the modern definition of the cardinal in question would be the smallest ordinal in this set, so let’s consider the smallest ordinal in this set and identify it, specifically, with our cardinal in question (so we can think beta=the cardinal we began with=the smallest ordinal with cardinality beta). The question now is, what is the smallest possible cardinality of an unbounded subset of beta (thinking of beta as an ordinal). This cardinality is the cofinality of beta.

For example, in Aleph-1, every countable set is bounded; the smallest unbounded set must have cardinality aleph-1, so the cofinality of aleph-1 is aleph-1.

Or, for a simpler example, in aleph-0, every finite set is bounded; the smallest unbounded set must have cardinality aleph-0, so the cofinality of aleph-0 is aleph-0.

On the other hand, take the cardinal aleph-omega (the first transfinite cardinal with infinitely many transfinite cardinals before it). This cardinal has a countable unbounded set inside it; namely, the set {aleph-0, aleph-1, aleph-2, aleph-3,…} (aleph-omega is the supremum of this set). Therefore, the cofinality of aleph-omega is just aleph-0 (or omega, whichever you want to call it).

Since c (the cardinality of the continuum) must have cofinality greater than aleph-0, by the above we see that c can be aleph-1, but c can’t be aleph-omega. However, c could be aleph-(omega+1), aleph-(omega+2), or any cardinal with cofinality greater than aleph-0.

I hope this makes sense, though I’m not sure it does. The modern trend is to do away with the “aleph” notation and just stick with the ordinal “omega” notation, and treat cardinals as simply being specific types of ordinals, and I’m afraid I may have screwed something up somewhere trying to translate everything back into the “aleph” cardinal notation.

62

Thanks for the clarifications, DrMatrix and Cabbage. I think one critical obstacle at this point is the fact that I’d never even heard of ordinals until this thread. Some more reading on MathWorld is in order. I’ll come back to this…

63

I think I’ve asked something like this before, and I think it was answered, but I didn’t understand the answer, so I’ll try again.

Let’s assume CH is false, and call some “subset of the reals with cardinality Aleph-1” S. S as a subset of the reals must exist, even if CH is true, and even if we can’t say what S is. With CH false, the cardinality of S is greater than that of the integers, and less than that of the reals. With CH true, the cardinality of S must equal that of the integers, or that of the reals. But doesn’t the cardinality of S being equal to, say, the cardinality of the reals, mean it can be put in a one-to-one correspondance with the reals? How is it that making a choice for CH changes whether S (even if we can’t say what S is) can be put into one-to-one correspondance with the reals?

[sub]imagine aleph-1 of these little guys → :confused: [/sub]

64

ZenBeam: I think the statement “S as a subset of the reals must exist, even if CH is true” is where the problem lies.

Since the CH is a proposition of set theory, and since the real numbers are constructed in terms of sets, the object we call “the set of real numbers” has two different definitions. There are the real numbers that we get when we assume CH is true, and there are the real numbers which exist when we assume CH is false. And those two definitions do not agree. In particular, in the second definition there exists a subset S whose cardinality lies strictly between the cardinality of the integers and the cardinality of the reals, and in the first definition no such S exists.

So in fact it’s not always possible to “translate” a subset of real numbers from the “CH-false” universe to the “CH-true” universe. (Clearly it’s possible for some subsets, like {1, 3.5} or the rationals, just not for all subsets.)

Or at least I think that’s what’s happening. There are lots of people on this thread who know more about set theory than I do; feel free to correct me if I’ve goofed, folks.

65

Math Geek’s analysis is correct, IMHO.

66

How is this possible? The reals can be represented using, say, decimal notation. Every real can be represented that way (right?). Can’t both the CHtrue and CHfalse real numbers be put in a one-ot-one correspondance with this representation? (You’ve got to remove the representations ending in repeating 9’s, but that shouldn’t be a problem. There’s only a countably infinite number of them.) So now you have a one-to-one relation between CHtrue reals and CHfalse reals.

67

I gotta admit, ZenBeam, this one’s a poser. You have, I think, successfully exposed the difference between formal mathematics and our common sense notions of mathematincs.

You’re correct that there does appear to be a correspondance between CHtrue-reals and CHfalse-reals. However, this correspondance is not a bijection between sets. A bijection is only defined in the context of set theory…remember, functions are defined in terms of sets too…and we’re talking about two different set theories here. Hence even though we have a perfectly sensible notion of a “map” between CHtrue-reals and CHfalse-reals this map does not and cannot satisfy any mathematical definition of a “function”.

It’s not a very satisfying answer, but the fact is there’s just no way to describe, mathematically, the situation you described perfectly well in a handful of English sentences in your last post.

68

I read an article in Scientific American that described the construction of a model of set theory with CH false (which they called non-Cantorian) from set theory that assumed CH true (called Cantorian). I didn’t understand everything, but I remember they compared the construction of the non-Cantorian model to the construction of a model of non-Euclidian geometry - a sphere - using (3D) Euclidian geometry. In geometry, “lines” and “points” are undefined. The only thing we know about them is that they satisfy the axioms. The lines and points in a plane serve as lines and points in Euclidian geometry. Great circles and polar pairs of points on the surface of a sphere serve as lines and points in non-Euclidian geometry. The lines and points in Euclidian geometry are not the same things as lines and points in non-Euclidian geometry. In set theory, your undefined objects are sets and the relation “is an element of”. The sets and element-of relation of Cantorian set theory are not the same things as the sets and elements-of relation non-Cantorian set theory.

Cabbage, Thanks for the correction. I understood your definition and examples, I think. Would the cofinality of 5 be 1? And would cofinality of 0 be 0?

69

Taking it one step farther, I think that exposes the difference between a formal understanding, and an actual understanding of the problem.

70

DrMatrix:

That’s right. If you’re used to thinking of the cardinals as a “subclass” of the ordinals, and to thinking of each cardinal (and ordinal) as the set of all smaller ordinals, then cofinality is easier to define (I don’t know if that’s the definition people reading this thread are used to, which is why my earlier definition was kind of verbose).

The cofinality of a cardinal x is the smallest ordinal which can be mapped unboundedly into x, or, in other words, the smallest possible cardinality of an unbounded subset of x.

Since 0=the empty set, the cofinality of 0 would be 0. Since 5={0,1,2,3,4}, and {4} is an unbounded subset of this, cofinality of 5 is just 1.

Also, omega = {0,1,2,3,…} has cofinality omega (since any finite subset of omega is bounded), but the cofinality of omega+1 = {0,1,2,3,…,omega} is one, since the singleton set {omega} is unbounded in omega+1.

In general, if x is a transfinite cardinal, it can be shown that cofinality(2[sup]x[/sup]) > x. In particular, cofinality©=cofinality(2[sup]omega[/sup]) > omega. That’s the only restriction on c, though; it’s consistent for c to be any cardinal greater than omega as long as this condition is met.

71

Sorry to backtrack to such a long-dead part of the conversation, but I’ve been thinking about this for about the last week, and I don’t get it.

It seems obvious to me (though I’m not a mathematician…) that there are exactly [symbol]À[/symbol][sub]0[/sub] points between any two integers (and therefore I guess also between any two finite segments) on the number line:

Any integer can be represented by exactly one nonrepeating decimal expansion between 0 and 1 (using the decimal point as a mirror, in a sense, and filling with all trailing zeroes):
1 -> 0.1
2 -> 0.2
…
10 -> 0.10
11 -> 0.11
…
100 -> 0.001
…
2568194232 -> 0.2324918652

and so on. So there are the same number of reals between integers as there are integers. So since there are [symbol]À[/symbol][sub]0[/sub] Integers, and [symbol]À[/symbol][sub]0[/sub] reals to each integer, why aren’t there [symbol]À[/symbol][sub]0[/sub][sup][symbol]À[/symbol][sub]0[/sub][/sup] reals? Why 2[sup][symbol]À[/symbol][sub]0[/sub][/sup]?

I read your binary explanation, but this method appears to give the same result independent of the base.

I’m confused.

72

Every integer can be mapped to a number in the set [0,1), but not every number in the set [0,1) can be mapped to an integer. What this means is that the cardinality of the set of numbers between 0 and 1 is strictly greater than the number of integers.

Using your mirror mapping, for instance: I can map 1/2 to 5, and I can map 1/4 to 52. But what does 1/3 map to? An infininite progression of 3s to the left of the decimal point. OK, so maybe that’s [symbol]À[/symbol][sub]0[/sub]. But then, what’s 1/9? If we try to say that that’s [symbol]À[/symbol][sub]0[/sub], too, then our mapping isn’t 1-to-1.

That’s just a counterexample to show that that particular mapping won’t take you from the reals to the integers. Cantor’s diagonalization proof, however, can be used to show that no matter what your attempted mapping, you’ll always be able to find a real number that won’t be mapped to an integer. I don’t think that anybody has tried to present the proof yet here, so I’ll give it a whirl.

Suppose that you have some mapping between the integers and the numbers in [0,1). This is equivalent to saying that we have a list of all the reals in [0,1). We’ll represent those numbers by ordinary base ten decimals. Let’s say that the mapping starts off something like this:


1 | 0.356786156...
2 | 0.476347642...
3 | 0.863314796...
4 | 0.731684764...
5 | 0.743188731...
6 | 0.931873215...
7 | 0.123584467...
8 | 0.567713847...
9 | 0.246647865...

Now, construct a new number, by going down the diagonal of this grid: In this case, that would be 0.373683445…

Now, take that number, and do the following to each digit: If the digit is from 0 to 4, increase it by one. If the digit is from 5 to 9, decrease it by one. This turns our number into 0.464572334… Now, we know that this number is not equal to the first number in our list, because it differs in the first digit. We know it is not equal to the second number in our list, because it differs in the second digit. We know that this number is not equal to the nth number in our list, because it differs in the nth digit. In short, this number we have constructed is not equal to any number in our list, so we must have left off some numbers when we made our list. But we said nothing about how we made that list, so it must be that no matter how one makes a list of real numbers, one cannot include them all. Therefore, there are more real numbers in [0,1) than there are integers.

73

Joe_Cool, what you’ve done is count the number of terminating decimals between zero and one. So you havn’t even counted all the rationals, since some repeat forever. (Also, even though there are [symbol]À[/symbol][sub]0[/sub] integers, and there are [symbol]À[/symbol][sub]0[/sub] rationals between each integer and its successor, this works out to there being [symbol]À[/symbol][sub]0[/sub][sup]2[/sup] rationals. Which, due to the oddities of transfinite arithmetic, works out to be [symbol]À[/symbol][sub]0[/sub] anyway).

74

Joe_Cool, what you’ve done is count the number of terminating decimals between zero and one. So you havn’t even counted all the rationals, since some repeat forever. (Also, even though there are [symbol]À[/symbol][sub]0[/sub] integers, and there are [symbol]À[/symbol][sub]0[/sub] rationals between each integer and its successor, this works out to there being [symbol]À[/symbol][sub]0[/sub][sup]2[/sup] rationals. Which, due to the oddities of transfinite arithmetic, works out to be [symbol]À[/symbol][sub]0[/sub] anyway).

75

Ok, I’ll buy that. Obviously I left out a large number of, er, numbers.

But that makes my point even more so. If there are an uncountably infinite number of reals for each one of [symbol]À[/symbol][sub]0[/sub] integers, then how can the number of reals be 2[sup][symbol]À[/symbol][sub]0[/sub][/sup], as in the earlier post by Chronos?

Anyway, isn’t 2[sup][symbol]À[/symbol][sub]0[/sub][/sup] also countable?

76

We haven’t shown that there’s any particular number of reals for each integer. All we’ve shown is that there are more reals.

Above and beyond that, transfinite arithmetic is weird.

No. The power set of any set S is larger than S, and 2[sup]aleph-0[/sup] is the size of a powerset of a countable set. So it can’t be countable.