Question 2 on infinity - Cantor's alephs

Factual Questions
1

I have some questions following my reading of The Mystery of Infinity by Amir D. Aczel. My first question is posted here. This is the second question.

What exactly are the alephs?
I understand that aleph0 is the cardinality of the whole numbers.
I also understand the concept of a superset – a set containing all the subsets of another given set.
I understand that the cardinality of the superset is 2^cardinality of the given set
I understand that the cardinality of the contimuium is 2^aleph0 and that this is also equal to the cardinality of the superset of the whole numbers.
And I know that the continuium hypothesis is the statement that aleph1 is equal to the cardinality of the contimuium.
I know too that the proof of the continuium hypothesis depends on the axiom of choice (cue question three) and that it has been proven quite surprisingly that the proof or disproof of the continuium hypothesis will have no effect on the foundations of mathematics.

So, what then are aleph1, aleph2 aleph3 etc, and what is the big deal?

2

That’s the power set, not superset.

The axiom of choice isn’t strong enough to prove or disprove the continuum hypothesis (CH). CH is completely independent of Zermelo-Fraenkel-Choice (ZFC) set theory…CH could be true, but CH could also be false. There is no proof of CH (nor the negation of CH) within ZFC.

If a proof of CH (or its negation) is ever accepted, it must depend on an additional axiom added to ZFC. This would have a large effect on the foundations of mathematics.

That might be a bit much for me to explain with the time I have, but aleph1 is the cardinality of the set of unique ways (up to order isomorphism) to well order a countable set. Aleph2 is the cardinality of the set of unique ways to well order a set of cardinality aleph1. And so on.

I’m really not sure if that paints a clear picture of the alephs at all. If it’s not clear, I (or someone else) can help to clarify it further.

3

oops, power set, super set. I never did this stuff at university so … hence the questions.

Nope still clear as mud on the alephs. Care to define well-ordering?

4

A set B being well ordered means that any nonempty subset of B has a smallest element.

For example, the natural numbers are well ordered: Take any non empty subset C of the natural numbers. Now, in order, check whether 0 or 1 or 2 or 3 or… is in C. The first one you come to that is actually in C is the smallest element of C.

The real numbers are not well ordered–There is no smallest positive real number.

Now think of the different ways to well order the natural numbers. One is the natural ordering:

0,1,2,3,…

Here’s another one:

1,0,3,2,5,4,7,6,…

But these two examples are order isomorphic. They both have the same order structure, albeit with different labelings.

This next one, however, is distinct:

1,2,3,4,…,0

It’s distinct because it has one element (0) that is preceded by infinitely many numbers (all of the positive integers, in fact).

Here’s another one distinct from the previous ones:

2,3,4,5,…,0,1

This well ordering has two elements preceded by infinitely many, not just one.

Another one:

0,2,4,6,8,…1,3,5,7,9,…

(All of the evens in the usual order, followed by all the odds).

What I was saying earlier is that if D is the cardinality of the set of distinct ways to well order the natural numbers, then D has cardinality aleph1.

5

I see Cabbage has gone off line, but thanks for that anyway.
I think I’ve got the well-ordering thing. Well perhaps a thin grasp of the fundamental idea.

Next question, open to anyone.
If the CH was proved true, that is c=aleph1, and the set of reals is not well ordered, then, doesn’t this imply that there is no aleph2?
Rephrasing, if we define aleph2 as the number of distinct ways of well-ordering a set with cardinality aleph1, and the reals (with cardinality aleph1, assuming the CH) are not well ordered, then how is it that any set with cardinality aleph1 can be well ordered?

Or perhaps I have just stumbled on the crux of the problem?

6

[QUOTE=Cabbage]
A set B being well ordered means that any nonempty subset of B has a smallest element.

For example, the natural numbers are well ordered: Take any non empty subset C of the natural numbers. Now, in order, check whether 0 or 1 or 2 or 3 or… is in C. The first one you come to that is actually in C is the smallest element of C.

The real numbers are not well ordered–There is no smallest positive real number.
[/QUOTE]
Just so I understand, the key for real numbers being not well ordered is that the subset doesn’t have to be finite? Because, while there is no smallest positive real number, any finite non-empty subset of the positive real numbers will have an element that is smaller than all the other elements, right?
And is what about sets that don’t have a smallest element, but do have a largest element, are they well-ordered?

7

The real numbers aren’t well ordered under the usual ordering, but that doesn’t mean that they can’t be well ordered. If you accept the axiom of choice, then you also accept that a well ordering exists for any set, including the real numbers.

8

This is proving to be subtle and perplexing. IIUC, Cabbage’s statement “The real numbers are not well ordered–There is no smallest positive real number.” is a bit of a simplification.

9

[QUOTE=j_sum1]
This is proving to be subtle and perplexing. IIUC, Cabbage’s statement “The real numbers are not well ordered–There is no smallest positive real number.” is a bit of a simplification.
[/QUOTE]

As ultrafilter noted, Cabbage’s statement is perfectly accurate, since it means that the real numbers, taken as a structure with the conventional fixed ordering, aren’t well-ordered. However, the possibility still exists that one could devise another ordering for the same entities under which they are well-ordered.

As an example, the integers, taken as a structure with the conventional fixed ordering, aren’t well-ordered, of course, since there’s the infinite descending sequence 0, -1, -2, etc. However, one can easily well-order those same entities by using a different ordering: for example, order them as 0 < -1 < 1 < -2 < 2 < -3 < 3 < …; with this different ordering, there aren’t any infinite descending sequences.

10

In reply to the OP, if you assume that cardinalities are linearly ordered (i.e., that out of any two distinct cardinalities, one is smaller than the other; this statement is equivalent to the axiom of choice), then the easiest way to understand the alephs is just in terms of the ordering of the infinite cardinalities.

aleph_0 is the smallest infinite cardinality, aleph_1 is the second smallest infinite cardinality, aleph_2 is the third smallest infinite cardinality, etc. Then aleph_omega is the smallest cardinality larger than all of those, aleph_{omega+1} is the smallest cardinality larger larger than that, aleph_{omega+2} the smallest one larger than that, etc. And then after all of those comes aleph_{omega*2}, and the whole process continues in the same way.

For every set of cardinalities, there’s a least cardinality larger than all of those; the series of (infinite) cardinalities ordered by size is the aleph series, the indices of which are the ordinal numbers.

11

[QUOTE=Quercus]
Just so I understand, the key for real numbers being not well ordered is that the subset doesn’t have to be finite? Because, while there is no smallest positive real number, any finite non-empty subset of the positive real numbers will have an element that is smaller than all the other elements, right?
[/QUOTE]

Yeah. In any linear ordering (like, for example, the ordered structure of the reals), all finite sets have a least element, but well-ordering is a much stronger condition with no finitude restriction.

No; by definition, if there is any set from your ordered structure without a smallest element, then your ordering isn’t a well-order. But, if every set from your ordering has a largest element, then, of course, by taking the dual order with everything flipped, you get a well-ordering, and so the underlying set is well-orderable, even if not well-ordered under the particular ordering you’re currently looking at.

12

Let me try to explain the alephs. First are the finite ordinals. Then omega, the order type of the natural numbers. The cardinality of that set is aleph_0. Add an element at the beginning, you have exactly the same order type, so 1 + omega = omega. Add an element at the end you get a new order type–it has an element whose predecessors are a set of type omega. It is called omega + 1. You can continue to get omega + 2, omega + 3, …, omega + omega, usually denoted omega2 (or omega*2, if you prefer). Go on and get omega3, omega4, …, omega omega, usually denoted omega^2. Go on, get all the powers of omega, in fact all polynomials. The set of all such order types is a new ordinal, called epsilon_0. Epsilon_0 is still countable, since every element can be named in a finite way and there are only finitely many such labels. It is, however, an important order type since it is enough to do all questions in elementary arithmetic. But you can continue to epsilon_0 + 1 and so on. Eventually you run out names, but the set of all these countable order types (or ordinals, as they are usually called) is not countable and is, in fact, aleph_1. There is no reason this has to be c. Anyway, you do it again, and again,…, eventually running out of order types of size aleph_2 (which Goedel actually believed was c, but this was just his intuition). You get aleph_3 and aleph_4 and eventually aleph_omega. But there is no reason to stop there. Somewhere in this so-called cumulative hierarchy there is c, but where? Ah, that is the question. There are not very many restrictions, although IIRC it cannot be aleph_theta, where theta is itself a limit ordinal (a limit ordinal is one that, like omega and omega2, does not have an immediate predecessor).

13

[QUOTE=Hari Seldon]
Go on, get all the powers of omega, in fact all polynomials. The set of all such order types is a new ordinal, called epsilon_0. Epsilon_0 is still countable, since every element can be named in a finite way and there are only finitely many such labels. It is, however, an important order type since it is enough to do all questions in elementary arithmetic.
[/QUOTE]

If I may nitpick, epsilon_0 isn’t the order type of all polynomials of omega, as I would understand the term (i.e., finite sums of finite powers of omega); that would actually be omega^omega. Rather, epsilon_0 is the order type of all ordinals which can be finitely constructed from omega with +, , and ^ (i.e., ordinals with finite Cantor normal form); thus, after all the polynomials of omega comes omega^omega, then omega^omega + 1, …, omega^omega + omega^32 + 5, …, then omega^omega * 2, …, then omega^omega * omega (= omega^(omega+1)), …, then omega^(omega^2), …, then eventually omega^(omega^omega), …, eventually omega^(omega^(omega^omega))), …, and only after all that sort of stuff do we finally reach epsilon_0.

From this, it should be clear that epsilon_0 is the supremum of 0, 1, omega, omega^omega, omega^(omega^omega), omega^(omega^(omega^omega)), etc. [although that series itself has order type omega, of course; because of this, we say that epsilon_0 has cofinality omega, since it can be written as the supremum of an omega-chain of smaller ordinals]. Indeed, epsilon_0 is the least ordinal x such that x = omega^x.

The basic importance of epsilon_0 in metamathematics results from the fact that one can prove the consistency of Peano Arithmetic from a very weak basis theory (much weaker than PA) augmented with a principle for transfinite induction up to epsilon_0, as was shown by Gentzen. In fact, it is the least ordinal for which such can be done (PA itself already essentially contains transfinite induction principles for every lesser ordinal, from which it follows, by Goedel’s second incompleteness theorem, that such lesser transfinite inductions cannot establish PA’s consistency), and thus, in proof theoretical terms, it represents the consistency strength of PA. A particular fascinating related result is that Goodstein’s theorem is essentially equivalent to epsilon_0 induction, and therefore cannot be proved from PA.

14

In amendment to the last paragraph of the previous post, let me add that the importance of Peano Arithmetic for metamathematics, especially in this context, stems largely from the fact that it is essentially equivalent to the most natural first-order theory of finite sets [one equivalent to ZFC with the Axiom of Infinity replaced by its negation, though it can be much more cleanly formulated than that (e.g., with extensionality, null set, and “cons” axioms, along with the appropriate axiom scheme of induction)].

15

I might as well mention: just as the aleph numbers form a series indexed by ordinals (the series of infinite cardinalities, equipped with the natural ordering), so, too, do the epsilon numbers (the series of ordinals x satisfying x = omega^x, equipped with the natural ordering). This explains the “0” part of epsilon_0, since it’s the least such ordinal. There’s a series of “omega numbers” as well, according to which omega_k is the least ordinal of cardinality aleph_k (though many would just identify/conflate the two altogether); thus, omega itself is also known as omega_0, the order type of all countable ordinals is omega_1, etc.

16

[QUOTE=j_sum1]
Care to define well-ordering?
[/QUOTE]

Sorry I’m late, but I’ve been moving to N’awlins. I’d define a well ordering, but I already did. And you might find a bunch of other stuff in the “fundamentals” section useful too.

17

Just popping in to say, that’s a rather nice blog, Mathochist. I’ve recently been getting really into category theory (something I’ve known I should do for a while but kept putting off till a recent epiphany that I’d come almost wholly to the categorical perspective anyway, without quite realizing it), and your posts on the subject are very nice; really helpful to a semi-beginner like me. (My interests are by way of categorical logic while you seem to be more of a pure algebraist, but in my current state of ignorance, any knowledge is good knowledge).

So, uh, thanks, and keep up the good work.