[This lecture was covered by Marion Scheepers. Many thanks! The notes below also cover lecture 6.]
We want to prove the following result and a few related facts.
Theorem. (Specker). and imply .
It follows immediately from the theorem that implies , since the result gives that any (infinite) embeds into .
Proof. The argument depends on 2 lemmas.
Lemma 1. implies that .
Proof. a) , where the strict inequality is Specker’s lemma, shown on lecture 3, section 5. By , we have . (In particular, is Dedekind-infinite.)
b) , by a). By , we have or .
c) If , we can inject into the set of finite sequences of elements of . For example, if is the disjoint union of and , both of size , there are bijections and , and we can use them to define an injection as follows: Fix . Define by , and by .
d) But there is no such injection, by the Halbeisen-Shelah theorem, shown on lecture 3, section 6. The theorem has the hypothesis that is Dedekind-infinite, that we showed in a).
e) So .
f) Finally, by e). By it follows that , or .
g) But immediately contradicts the Halbeisen-Shelah theorem.
h) So .
Lemma 2. implies that either is well-orderable (and equal to ), or else does not inject into .
Proof. Assume . Suppose injects into . Note that since does not inject into . Thus,
since implies , as shown in Lemma 1. By again, .
By , so, if has size , then is equipotent with , as shown on lecture 4, section 9 (remark after the proof of the first lemma).
As shown on lecture 4, first lemma in section 9, if injects into for some ordinal , then is well-orderable. It follows that in our situation is well-orderable, so is an ordinal. But then is an ordinal and in fact, it equals Since it also equals , we are done.
Using these lemmas, we prove Specker’s result as follows:
- Assuming but not well-orderable, from Lemma 2 it follows that .
- Hence, if , , and is not well-orderable, then neither is , so and .
- Hence, if has size , then . But and have the same size by Lemma 1, so .
- But this contradicts that injects into , as shown on lecture 3, proof of the Lemma in section 7. This completes the proof of Specker’s theorem.
Open question. (). Does imply that is well-orderable?
Remark. does not imply that is well-orderable. For example, under determinacy, every set of reals has the perfect set property, so holds. But is not well-orderable.
Homework problem 4. Suppose that and Then .
Some hypothesis is necessary for the result of Homework problem 4 to hold. For example, it is consistent that there is an infinite Dedekind finite set with also Dedekind-finite. (On the other hand, is necessarily Dedekind-infinite.) However, if is Dedekind-finite and for nonzero cardinals , then obviously .
I am not sure who first proved the following. Maybe Kanamori-Pincus?
Theorem. Assume , and Then In particular, there is at most one initial ordinal such that but is not well-orderable.
Proof. If then since by .
Again by either or
If then Homework problem 4 implies that so and fails.
Hence, so .
The `in particular’ clause follows immediately.
Corollary. for initial ordinals implies .
Proof. As shown below, is equivalent to being well-orderable for all ordinals This follows immediately from for initial ordinals, by the last theorem.
It remains to show:
Theorem. The axiom of choice is equivalent to the statement that is well-orderable for all ordinals .
Proof. Assume in that the power set of any ordinal is well-orderable. We want to conclude that choice holds, i.e., that every set is well-orderable. A natural strategy is to proceed inductively, showing that each is well-orderable: Clearly, if the result is true, each would be well-orderable. But also, given any set , it belongs to some and, since the latter is transitive, in fact and therefore is well-orderable as well. The strategy is suggested by the fact that for all , , so a well-ordering of gives us a well-ordering of thanks to our initial assumption.
We argue by induction: Clearly is well-ordered by the well-ordering . Given a well-ordering of , there is a unique ordinal and a unique order isomorphism . By assumption, is well-orderable, and any well-ordering of it induces (via ) a well-ordering of .
We are left with the task of showing that is well-orderable for limit. The natural approach is to patch together the well-orderings of the previous into a well-ordering of . This approach meets two obstacles.
The first, and not too serious, one, is that the well-orderings of different are not necessarily compatible, so we need to be careful on how we “patch them together. ” The natural solution to this obstacle is to simply order the sets as they appear inside . More precisely, define for , iff
- Either , or else
- , say, and if is the well-ordering of , then .
It is easy to see that this is indeed a well-ordering of : Given a non-empty , let be least so that has an element of rank . Then the -first among these elements would be the -least element of .
The second obstacle is more serious. Namely, the assumption is simply that there is a well-ordering of each , not that there is any canonical way of choosing one. In order for the argument above to work, we need not just that each for is well-orderable, but in fact we need to have selected a sequence of well-orderings of the , with respect to which we proceeded to define the well-ordering of .
The way we began the proof suggests a solution: When we argued that it suffices to well-order each , we considered an arbitrary set and noticed that if , then a well-ordering of gives us a well-ordering of . Similarly, given limit, if we can find large enough so each for is below , then we can use a well-ordering of to induce the required well-ordering .
We now proceed to implement this idea: Let . (Notice that this makes sense since, inductively, each with is well-orderable and therefore isomorphic to a unique cardinal.) Let be a well-ordering of . We use to define a sequence so that well-orders for all . We use recursion on to define this sequence. Again, . At limit stages we copy the strategy with which we tried to well-order to define : For , set iff
- Either , or else
- , say, and .
Finally, given , we describe how to define : Let be the unique ordinal such that there is an order isomorphism
Since , then , so and the well-ordering of also well-orders . Via , this induces the well-ordering of we were looking for.
Remark. By Specker’s result, if but is not well-orderable, then must fail. Kanamori and Pincus proved that in this case in fact there is an increasing sequence of cardinals of length between and
Here is a rough idea of their argument: Recall from lecture 2 that denotes the set of well-orderings of subsets of so . Define for ordinals by iterating transfinitely, taking unions at limit stages and setting By induction, one shows the following three facts:
- For any set and ordinal ,
- For any infinite and any ,
- For any ordinals and any set ,
Also, one easily verifies:
- implies In particular, if then
Assume now that holds but is not well-orderable. Write for the cardinality of for any set of cardinality Notice:
- and so
Since there must be a least ordinal such that This is necessarily an infinite limit ordinal. One concludes the proof by showing:
- For any with one has
I would like to review the results relating and in a way that gives some additional information.
Definition. For an infinite set , set surjective and .
Fact. is a set and is an initial ordinal.
Proof. Suppose that is a surjection. Define by iff . Clearly, is an equivalence relation on , and there is an obvious bijection between the quotient and . The collection of quotients is in bijection with the collection of equivalence relations, that is clearly a set.
From the above it follows that an ordinal is the surjective image of iff there is an equivalence relation on whose quotient is well-orderable and has size . This shows that is a set and that if is an ordinal, then it is an initial ordinal. But this follows from noticing that if and is surjective, then is surjective, where if , and otherwise.
Proof. If is injective and , let be the function if and otherwise. Then is surjective. .
It is possible that . For example, this holds if is well-orderable. It is also possible that . For example, under determinacy but is much larger.
Fact. If is surjective, then is injective.
Proof. Define a map by setting for a relation unless is a well-ordering of its field in order type , in which case . This is a surjection.
Corollary. for all ordinals .
Proof. This is clear by induction if is finite. Otherwise, .
Corollary. if for some .
Proof. Again, it suffices to consider infinite . In this case, by Homework problem 3.
Proof. If then there is a surjection from onto . This is clear if . Otherwise, if is onto, consider given by .
Hence, there is an injection of into . The result follows.
Corollary. if is a successor cardinal.
Corollary. Suppose that is the -th initial ordinal. If , then .
Proof. Let be a bijection between the set of initial ordinals below and . The map given by if is well-orderable, and otherwise, is a surjection.
Corollary. If is infinite and Dedekind-finite, then .
Proof. is the -th initial ordinal.
Corollary. Suppose that . Then is not equipotent to a square and for some (infinite) limit ordinal .
Notice that, under choice, is always a successor cardinal; I do not know if the conclusion of the corollary is consistent.