There are a potential infinity of ideas about infinity.
I well remember a mathematics professor who told a student who was carrying on about infinity in a calculus class, “You know very little about infinity, and I know even less than that, so let’s get on with the class, shall we.”
And I’m not too swift with grammar either.
Now now, just because mathematicians wear funny clothes and don’t get any action, doesn’t mean they’re priests.
Could one of the esteemed mathemeticians in this thread please remind me what the definition of [symbol]À[/symbol][sub]1[/sub] is, independently of the A of C? I know that, given the A of C, it’s the cardinality of the power set of the integers (which is also the cardinality of the reals), but I’ve never seen a definition of what it is without the A of C.
And Cabbage, one must ask what concept of “probability” Mr. Cohen is applying to the Axiom of Choice. What does it mean to ask whether an axiom is true, if the axiom and its negation are both equally consistent with the other standard axioms?
I think you probably meant “continuum hypothesis (CH)” instead of “axiom of choice”. Anyway, to put it simply, [symbol]À[/symbol][sub]1[/sub] is the next highest infinity after [symbol]À[/symbol][sub]0[/sub]. CH says that this is actually the size of the real numbers, but it is also consistent that the reals could be much larger than [symbol]À[/symbol][sub]1[/sub].
Here’s another way of thinking of it: Take the set of natural numbers; how many different (non-isomorphic) ways can you well order them?
(I’m only considering the overall order structure of the set, not really paying attention to which element is bigger than which. For example, the usual order 0 < 1 < 2 < 3 < … is the same as 1 < 0 < 3 < 2 < 5 < 4 < 7 < 6 < …, because both have the same order type (they both have order type [symbol]w[/symbol]))
However, I could order them
1 < 2 < 3 < 4 < 5 < … < 0 (zero is bigger than everything else)
which would be order type [symbol]w[/symbol]+1. Or
2 < 3 < 4 < 5 < 6 < … < 0 < 1
which would be order type [symbol]w[/symbol]+2.
I could also have
1 < 3 < 5 < 7 < … < 0 < 2 < 4 < 6 < …
([symbol]w[/symbol]+[symbol]w[/symbol] = 2 [symbol]w[/symbol])
or even
1 < 3 < 5 < 7 < 9 < 11 < …
2 < 6 < 10 < 14 < 18 < 22 < …
4 < 12 < 20 < 28 < 36 < 44 < …
8 < 24 < 40 < 56 < 72 < 88 < …
.
.
.
< 0
which would be order type [symbol]w[/symbol]*[symbol]w[/symbol]+1 = [symbol]w[/symbol][sup]2[/sup]+1.
So how many different order types (of well orderings) of a countable set do we get? [symbol]À[/symbol][sub]1[/sub]. This is true regardless of whether CH is true or not.
In fact, in general [symbol]À[/symbol][sub]n+1[/sub] is the number of different order types of a set of cardinality [symbol]À[/symbol][sub]n[/sub].
Again, I’m sure you meant CH instead of AC. Anyhow, certainly there’s a lot of vagueness in Cohen’s statement. While it’s true that you can safely take either CH or it’s negation as an axiom, ideally one would hope that somewhere off in the future a natural, intuitive axiom might be found which would resolve CH. Or maybe just some axiom where the mathematics works out in particularly interesting and pleasing ways (and without which the mathematics is not nearly as rich); such an axiom might eventually gain wide acceptance and resolve CH. Of course, these are all vague, intuitive notions and arguments, but my feeling is that as math progresses, new axioms may come to be added to the current standard axioms, as our intuitions become more refined on just what, exactly, set theory is and how it works.
I think I’m missing something here (but maybe not). So if CH is true, À1 = C, but if CH is false, À1 < C. How is it that it’s not possible to compare the “different order types of a countable set” with the continuum, and determine whether they’re the same size or not?
You mean, of course, different well order types. And in order to prove that any set can be well-ordered, you need the Axiom of Choice. Chronos did confuse the A of C with CH, but I just want to point out that your definition of [symbol]À[/symbol][sub]n+1[/sub] does depend upon A of C, though not CH.
If I’m not mistaken, you need A of C to have [symbol]À[/symbol]'s > [symbol]À[/symbol][sub]0[/sub]
DrMatrix:
Yeah, that’s right, I did mean different well order types; however, I disagree that what I wrote above depends on AC (though I probably could have been clearer about that).
True, AC is needed in order for every set to have a well order, however, without AC we certainly still have well ordered sets. In particular, the ordinals (and cardinals) can be constructed without using AC; then we can define aleph-one to be the smallest cardinal larger than aleph-naught (again, without AC). Aleph-one is the set of all finite/countably infinite ordinals.
Without AC, we won’t be able to assign an arbitrary set a cardinality (to do so, in general, would require us to well order the set), but even without AC, we are able to assign any set with a well ordering a cardinality.
ZenBeam:
I guess that’s the million dollar question; you don’t seem to be missing anything that I can tell. It’s surprising that such a seemingly simple question runs so deep.
Cabbage,
Thank you. I stand corrected.
But, but, but, but, but, …
It can be shown that a line segment has as many points as a line, or a line as many points as a plane, by establishing a one-to-one correspondance between the two sets.
If CH is true, then doesn’t that mean there is a one-to-one correspondance between the “different [well] order types of a countable set” (DWOTOACS) and the continuum? If not, why not? If CH is instead assumed not true, how does that make this correspondance no longer hold? Is this what that exchange between you and DrMatrix, that I can’t really follow very well, involve? Is this correspondance something you can’t even explicitly write down, even though it must exist if CH is true?
CH says this correspondance must exist, but it doesn’t tell us what the correspondance will be.
When you ask if the “correspondance can be written down” (assuming CH) you’re really asking something equivalent to “is there a ‘definable’ well ordering of R?” The answer to this depends on what you mean by ‘definable’.
If you mean “definable without using anything set-theoretically suspicious” (say, only using integers) then the answer is no.
If you want to be more liberal and allow real number quantifiers then it’s consistent that there’s a definable well ordering of the form (there exists x)(for all y)(blah,blah,blah) where x and y are real number variables and (blah,blah,blah) is something in the simple form mentioned above. (only quantifying over integers) I think most people would agree that a definition like this can be “explicitly written down”.
However, it’s also consistent that there is no definition at all using only real parameters. I think most people would agree that if you could write down a definition of a well ordering of R, then it should only use at most real parameters.
We know that the cardinality of C is greater than [symbol]À[/symbol][sub]0[/sub]. We know that the least cardinal greater than [symbol]À[/symbol][sub]0[/sub] is [symbol]À[/symbol][sub]1[/sub] So we know that C >= [symbol]À[/symbol][sub]1[/sub]. Godel showed that CH is independent of the axioms of set theory. It cannot be proven nor dis-proven from them. If set theory is consistent, we can add CH as an axiom and the result will be consistent. We can also add an axiom that says CH is false and the result will be consistent. CH does not give us the correspondence, it just asserts that it exists. Since we cannot even prove the correspondence exists within set theory, it is impossible with just set theory to find it.
It is rather like the parallel postulate. It is independent of the other axioms of geometry. We can assume that given a line and a point not on the line, there is exactly one line that does not intersect the line. Or we can assume that any two lines intersect. Or that there are multiple lines through the given point. All three geometries are equally valid. None is the correct geometry.
I may have misunderstood, but I think ZenBeam was trying to ask something a bit more subtle. I think the question was something like:
“Can we write down an explicit definition of a function such that if CH is true then this defines a 1-1 correspondence between the countable ordinals and the continuum?”
Like I said, the answer is no, but it’s not because CH is independent of set theory. There are other axioms, like V=L, for which we could write down such an explicit definition and if V=L is true then they always give the desired correspondence.
The definition takes the form “(there exists x)(for all y)(blah)”.
Of course, I may have misunderstood the question.
I did, of course, mean Continuum Hypothesis, not Axiom of Choice. Mea culpa. But another question comes up: How do we know that the cardinality of the integers is the smallest of the transfinite cardinals? I have a difficult time conceiveing of one smaller, but then, intuition isn’t too reliable when dealing with set theory. Could there exist, for instance, a set whose power set has cardinality [symbol]À[/symbol][sub]0[/sub]?
No. It basically follows from the fact that any infinite subset of the naturals can be placed in 1-1 correspondence with the naturals. You don’t even need the axiom of choice–you just need that the naturals are well-ordered, which follows from the definition of ‘<’ on the naturals. Is it clear how to do this, or should I explain more?
The set of natural numbers is defined to be the smallest ordinal larger than all the integers. Since all the cardinals are ordinals, that means that there also is no smaller cardinal. So, in other words, the answer to your question is “because they are defined that way.”
A more intuitively satisfying argument can be made, though. (I’m not sure if this proof is totally rigorous. It’s been a while since I’ve studied the Zermelo-Frankel axioms, so this “proof” may be assuming the conclusion in some subtle way). Let N be the set of natural numbers. Suppose that M[sub]1[/sub] is an infinite subset of N. The natural numbers are well-ordered, which is to say, each subset has a least element. In particular M[sub]1[/sub] has a least element m[sub]1[/sub]. Map m[sub]1[/sub] to 1 in N. Now M[sub]1[/sub]{m[sub]1[/sub]} (the set M[sub]1[/sub] with the element m[sub]1[/sub] removed) has a least element. Call this set M[sub]2[/sub], and let its least element be m[sub]2[/sub]. Map m[sub]2[/sub] to two.
In general, let M[sub]i+1[/sub] = M[sub]i[/sub]{m[sub]i[/sub]}, and let m[sub]i+1[/sub] be the least element of M[sub]i+1[/sub]. Map m[sub]i+i[/sub] to i+1 in N. Since M is infinite, we will never reach a last m[sub]i[/sub], so eventually each integer will get some m[sub]i[/sub] mapped to, so this map is onto. Also, clearly no two elements of M[sub]1[/sub] get mapped to the same element of N, so the map is one-to-one. Hence M[sub]1[/sub] is in bijective correspondence with N. Therefore, no smaller infinite cardinal can exist.