[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

A. Appendix.

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.

**Fact.** .

**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. *

**Corollary. ***.*

**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.

**Corollary. **

**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.

[…] is equivalent to the statement: For all ordinals , is well-orderable; a proof can be found on lecture 5. Hence, if choice fails, some is not well-orderable, and by the above, . In Section 10 we will […]

[…] see that there is such a coding, simply notice (as in the appendix in lecture I.5) that there is a definable bijection between and that the map from a well-ordering of to its […]

[…] the last Corollary of the Appendix to lecture I.5, I indicate that in we have […]

[…] follows, in view of the following theorem which I have included previously in the blog. For the sake of completeness, I reproduce here the argument: Theorem 9 (Rubin) If is […]

[…] the last Corollary of the Appendix to lecture I.5, I indicate that in we have […]

[…] is equivalent to the statement: For all ordinals , is well-orderable; a proof can be found on lecture 5. Hence, if choice fails, some is not well-orderable, and by the above, . In Section 10 we will […]

[…] see that there is such a coding, simply notice (as in the appendix in lecture I.5) that there is a definable bijection between and that the map from a well-ordering of to its […]