## 580 -Some choiceless results (5)

[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). ${\rm CH}({\mathfrak m})$ and ${\rm CH}(2^{\mathfrak m})$ imply $2^{\mathfrak m}=\aleph({\mathfrak m})$.

It follows immediately from the theorem that ${\sf GCH}$ implies ${\sf AC}$, since the result gives that any (infinite) ${\mathfrak m}$ embeds into $\aleph({\mathfrak m})$.

Proof. The argument depends on 2 lemmas.

Lemma 1. ${\rm CH}({\mathfrak m})$ implies that ${\mathfrak m}+{\mathfrak m}={\mathfrak m}^2={\mathfrak m}$.

Proof. a) ${\mathfrak m}\le {\mathfrak m}+1 <2^{\mathfrak m}$, where the strict inequality is Specker’s lemma, shown on lecture 3, section 5. By ${\rm CH}({\mathfrak m})$, we have ${\mathfrak m}={\mathfrak m}+1$. (In particular, ${\mathfrak m}$ is Dedekind-infinite.)

b)  ${\mathfrak m}\le {\mathfrak m}+{\mathfrak m}\le 2^{\mathfrak m}+2^{\mathfrak m}=2^{{\mathfrak m}+1}=2^{\mathfrak m}$, by a). By ${\rm CH}({\mathfrak m})$, we have ${\mathfrak m}+{\mathfrak m}={\mathfrak m}$ or ${\mathfrak m}+{\mathfrak m}=2^{\mathfrak m}$.

c) If ${\mathfrak m}+{\mathfrak m}=2^{\mathfrak m}$, we can inject ${\mathcal P}(X)$ into the set ${\rm Seq}(X)$ of finite sequences of elements of $X$. For example, if ${\mathcal P}(X)$ is the disjoint union of $A$ and $B$, both of size ${\mathfrak m}$, there are bijections $\pi:A\to X$ and $\rho:B\to X$, and we can use them to define an injection $j:{\mathcal P}(X)\to {\rm Seq}(X)$ as follows: Fix $a\in X$. Define $j\upharpoonright A:A\to X^1$ by $j(r)=(\pi(r))$, and $j\upharpoonright B:B\to X^2$ by $j(r)=(a, \rho(r))$.

d) But there is no such injection, by the Halbeisen-Shelah theorem, shown on lecture 3, section 6. The theorem has the hypothesis that $X$ is Dedekind-infinite, that we showed in a).

e) So ${\mathfrak m}+{\mathfrak m}={\mathfrak m}$.

f) Finally, ${\mathfrak m}\le {\mathfrak m}\times {\mathfrak m}\le 2^{\mathfrak m}\times 2^{\mathfrak m}=2^{{\mathfrak m}+{\mathfrak m}}=2^{\mathfrak m},$ by e). By ${\rm CH}({\mathfrak m}),$ it follows that ${\mathfrak m}\times {\mathfrak m}={\mathfrak m}$, or ${\mathfrak m}\times {\mathfrak m}=2^{\mathfrak m}$.

g) But ${\mathfrak m}\times {\mathfrak m}=2^{\mathfrak m}$ immediately contradicts the Halbeisen-Shelah theorem.

h) So ${\mathfrak m}\times {\mathfrak m}={\mathfrak m}$. ${\sf QED}$

Lemma 2. ${\rm CH}({\mathfrak m})$ implies that either $2^{\mathfrak m}$ is well-orderable (and equal to $\aleph({\mathfrak m})$), or else $\aleph({\mathfrak m})$ does not inject into $2^{\mathfrak m}$.

Proof. Assume ${\rm CH}({\mathfrak m})$. Suppose $\aleph({\mathfrak m})$ injects into $2^{\mathfrak m}$. Note that ${\mathfrak m}<{\mathfrak m}+\aleph({\mathfrak m}),$ since $\aleph({\mathfrak m})$ does not inject into ${\mathfrak m}$. Thus,
${\mathfrak m}<{\mathfrak m}+\aleph({\mathfrak m})\le 2^{\mathfrak m} +2^{\mathfrak m}=2^{{\mathfrak m}+1}=2^{\mathfrak m}$ since ${\rm CH}({\mathfrak m})$ implies ${\mathfrak m}+1={\mathfrak m}$, as shown in Lemma 1. By ${\rm CH}({\mathfrak m})$ again, ${\mathfrak m}+\aleph({\mathfrak m})=2^{\mathfrak m}$.

By ${\rm CH}({\mathfrak m})$, ${\mathfrak m}+{\mathfrak m}={\mathfrak m}$ so, if $X$ has size ${\mathfrak m}$, then $Q(X)=X\times {\mathcal P}(X)$ is equipotent with ${\mathcal P}(X)$, 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 $Q(X)$ injects into $X+\kappa$ for some ordinal $\kappa$, then $X$ is well-orderable. It follows that in our situation $X$ is well-orderable, so ${\mathfrak m}$ is an ordinal. But then ${\mathfrak m}+\aleph({\mathfrak m})$ is an ordinal and in fact, it equals $\aleph({\mathfrak m}.$ Since it also equals $2^{\mathfrak m}$, we are done. ${\sf QED}$

Using these lemmas, we prove Specker’s result as follows:

• Assuming ${\rm CH}({\mathfrak n})$ but $2^{\mathfrak n}$ not well-orderable, from Lemma 2 it follows that $\aleph({\mathfrak n})=\aleph(2^{\mathfrak n})$.
• Hence, if ${\rm CH}({\mathfrak m})$, ${\rm CH}(2^{\mathfrak m})$, and $2^{\mathfrak m}$ is not well-orderable, then neither is $2^{2^{\mathfrak m}}$, so $\aleph(2^{\mathfrak m})=\aleph(2^{2^{\mathfrak m}})$ and $\aleph({\mathfrak m})=\aleph(2^{\mathfrak m})$.
• Hence, if $X$ has size ${\mathfrak m}$, then $\aleph(X)=\aleph({\mathcal P}({\mathcal P}(X)))$. But $X$ and $X^2$ have the same size by Lemma 1, so $\aleph(X)=\aleph({\mathcal P}({\mathcal P}(X^2)))$.
• But this contradicts that $\aleph(X)$ injects into ${\mathcal P}({\mathcal P}(X^2))$, as shown on lecture 3, proof of the Lemma in section 7. This completes the proof of Specker’s theorem. ${\sf QED}$

Open question. (${\sf ZF}$). Does ${\rm CH}({\mathfrak m})$ imply that ${\mathfrak m}$ is well-orderable?

Remark. ${\rm CH}({\mathfrak m})$ does not imply that $2^{\mathfrak m}$ is well-orderable. For example, under determinacy, every set of reals has the perfect set property, so ${\rm CH}$ holds. But ${\mathbb R}$ is not well-orderable.

Homework problem 4. Suppose that ${\mathfrak m}+{\mathfrak m}={\mathfrak m}$ and ${\mathfrak m}+{\mathfrak n}=2^{\mathfrak m}.$ Then ${\mathfrak n}=2^{\mathfrak m}$.

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 $X$ with ${\mathcal P}(X)$ also Dedekind-finite. (On the other hand, ${\mathcal P}^2(X)$ is necessarily Dedekind-infinite.)  However, if $2^{\mathfrak m}$ is Dedekind-finite and ${\mathfrak p}+{\mathfrak n}=2^{\mathfrak m}$ for nonzero cardinals ${\mathfrak p},{\mathfrak n}$, then obviously ${\mathfrak n}<2^{\mathfrak m}$

I am not sure who first proved the following. Maybe Kanamori-Pincus?

Theorem. Assume ${\rm CH}({\mathfrak m})$, ${\rm CH}({\mathfrak n})$ and ${\mathfrak m}<{\mathfrak n}.$ Then $2^{\mathfrak m}\le {\mathfrak n}.$ In particular, there is at most one initial ordinal $\kappa$ such that ${\rm CH}(\kappa)$ but $2^\kappa$ is not well-orderable.

Proof. If ${\mathfrak m}<{\mathfrak n}$ then ${\mathfrak n}\le 2^{\mathfrak m} +{\mathfrak n}\le 2^{\mathfrak n}+2^{\mathfrak n}=2^{{\mathfrak n}+1}=2^{\mathfrak n}$ since ${\mathfrak n}+1={\mathfrak n}$ by ${\rm CH}({\mathfrak n})$.

Again by ${\rm CH}({\mathfrak n}),$ either $2^{\mathfrak m} +{\mathfrak n}={\mathfrak n}$ or $2^{\mathfrak m} +{\mathfrak n}=2^{\mathfrak n}.$

If $2^{\mathfrak m} +{\mathfrak n}=2^{\mathfrak n},$ then Homework problem 4 implies that $2^{\mathfrak m}=2^{\mathfrak n},$ so ${\mathfrak m}<{\mathfrak n}<2^{\mathfrak m}$ and ${\rm CH}({\mathfrak m})$ fails.

Hence, $2^{\mathfrak m} +{\mathfrak n}={\mathfrak n},$ so $2^{\mathfrak m} \le {\mathfrak n}$.

The `in particular’ clause follows immediately. ${\sf QED}$

Corollary. ${\sf GCH}$ for initial ordinals implies ${\sf AC}$.

Proof. As shown below, ${\sf AC}$ is equivalent to ${\mathcal P}(\alpha)$ being well-orderable for all ordinals $\alpha.$ This follows immediately from ${\sf GCH}$ for initial ordinals, by the last theorem. ${\sf QED}$

It remains to show:

Theorem. The axiom of choice is equivalent to the statement that ${\mathcal P}(\alpha)$ is well-orderable for all ordinals $\alpha$.

Proof. Assume in ${\sf ZF}$ 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 $V_\alpha$ is well-orderable: Clearly, if the result is true, each $V_\alpha$ would be well-orderable. But also, given any set $x$, it belongs to some $V_\alpha$ and, since the latter is transitive, in fact $x\subseteq V_\alpha$ and therefore $x$ is well-orderable as well. The strategy is suggested by the fact that for all $\alpha$, $V_{\alpha+1}={\mathcal P}(V_\alpha)$, so a well-ordering of $V_\alpha$ gives us a well-ordering of $V_{\alpha+1}$ thanks to our initial assumption.

We argue by induction: Clearly $V_0$ is well-ordered by the well-ordering $<_0=\emptyset$. Given a well-ordering $<$ of $V_\alpha$, there is a unique ordinal $\beta$ and a unique order isomorphism $\pi : (V_\alpha , <)$ $\to (\beta, \in)$. By assumption, ${\mathcal P}(\beta)$ is well-orderable, and any well-ordering of it induces (via $\pi^{-1}$) a well-ordering of $V_{\alpha+1}$.

We are left with the task of showing that $V_\alpha$ is well-orderable for $\alpha$ limit. The natural approach is to patch together the well-orderings of the previous $V_\beta$ into a well-ordering of $V_\alpha$. This approach meets two obstacles.

The first, and not too serious, one, is that the well-orderings of different $V_\beta$ 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 $V_\alpha$. More precisely, define $x for $x,y\in V_\alpha$, iff

• Either ${\rm rk}(x)<{\rm rk}(y)$, or else
• ${\rm rk}(x)={\rm rk}(y)=\beta$, say, and if $<_{\beta+1}$ is the well-ordering of $V_{\beta+1}$, then $x<_{\beta+1}y$.

It is easy to see that this is indeed a well-ordering of $V_\alpha$: Given a non-empty $A\subseteq V_\alpha$, let $\gamma$ be least so that $A$ has an element of rank $\gamma$. Then the $<_{\gamma+1}$-first among these elements would be the $<$-least element of $A$.

The second obstacle is more serious. Namely, the assumption is simply that there is a well-ordering of each ${\mathcal P}(\delta)$, not that there is any canonical way of choosing one. In order for the argument above to work, we need not just that each $V_\beta$ for $\beta<\alpha$ is well-orderable, but in fact we need to have selected a sequence $(<_{\beta+1}:\beta<\alpha)$ of well-orderings of the $V_{\beta+1}$, with respect to which we proceeded to define the well-ordering $<$ of $V_\alpha$.

The way we began the proof suggests a solution: When we argued that it suffices to well-order each $V_\gamma$, we considered an arbitrary set $x$ and noticed that if $x\subseteq V_\beta$, then a well-ordering of $V_\beta$ gives us a well-ordering of $x$. Similarly, given $\alpha$ limit, if we can find $\delta$ large enough so each $|V_\beta|$ for $\beta<\alpha$ is below $\delta$, then we can use a well-ordering of ${\mathcal P}(\delta)$ to induce the required well-ordering $<_\beta$.

We now proceed to implement this idea: Let $\delta=\sup_{\beta<\alpha}|V_\beta|^+$. (Notice that this makes sense since, inductively, each $V_\beta$ with $\beta<\alpha$ is well-orderable and therefore isomorphic to a unique cardinal.) Let $<^*$ be a well-ordering of ${\mathcal P}(\delta)$. We use $<^*$ to define a sequence $(<_\beta:\beta<\alpha)$ so that $<_\beta$ well-orders $V_\beta$ for all $\beta<\alpha$. We use recursion on $\beta<\alpha$ to define this sequence. Again, $<_0=\emptyset$. At limit stages $\gamma<\alpha$ we copy the strategy with which we tried to well-order $V_\alpha$ to define $<_\gamma$: For $x,y\in V_\gamma$, set $x<_\gamma y$ iff

• Either ${\rm rk}(x)<{\rm rk}(y)$, or else
• ${\rm rk}(x)={\rm rk}(y)=\beta$, say, and $x<_{\beta+1}y$.

Finally, given $<_\beta$, we describe how to define $<_{\beta+1}$: Let $\xi=\xi_\beta$ be the unique ordinal such that there is an order isomorphism

$\pi : (V_\beta,<_\beta)$ $\to (\xi,\in)$.

Since $|\xi|=|V_\beta|$, then $\xi<\delta$, so $\xi\subset\delta$ and the well-ordering $<^*$ of ${\mathcal P}(\delta)$ also well-orders ${\mathcal P}(\xi)$. Via $\pi^{-1}$, this induces the well-ordering $<_{\beta+1}$ of $V_{\beta+1}$ we were looking for. ${\sf QED}$

Remark. By Specker’s result, if ${\rm CH}({\mathfrak m})$ but $2^{\mathfrak m}$ is not well-orderable, then ${\rm CH}(2^{\mathfrak m})$ must fail. Kanamori and Pincus proved that in this case in fact there is an increasing sequence of cardinals of length ${\rm cf}(\aleph({\mathfrak m}))$ between $2^{\mathfrak m}$ and $2^{2^{\mathfrak m}}.$

Here is a rough idea of their argument: Recall from lecture 2 that ${\mathcal O}(X)$ denotes the set of well-orderings of subsets of $X,$ so ${\mathcal O}(X)\subseteq{\mathcal P}(X\times X)$. Define ${\mathcal O}^\xi(X)$ for ordinals $\xi$ by iterating ${\mathcal O}$ transfinitely, taking unions at limit stages and setting ${\mathcal O}^0(X)=X.$ By induction, one shows the following three facts:

• For any set $X$ and ordinal $\xi$,  $\xi\preceq{\mathcal O}^\xi(X).$
• For any infinite $X$ and any $\xi$, ${\mathcal O}^\xi(X)\preceq{\mathcal P}(X\times\aleph({\mathcal O}^\xi(X))).$
• For any ordinals $\alpha<\beta$ and any set $X$, $|{\mathcal O}^\alpha(X)|<|{\mathcal O}^\beta(X)|.$

Also, one easily verifies:

• $\aleph(X)\le\aleph(Y)$ implies $\aleph({\mathcal O}(X))\le\aleph({\mathcal O}(Y)).$ In particular, if $\aleph(X)=\aleph(Y),$ then $\aleph({\mathcal O}(X))=\aleph({\mathcal O}(Y)).$

Assume now that ${\rm CH}({\mathfrak m})$ holds but $2^{\mathfrak m}$ is not well-orderable. Write ${\mathcal O}^\xi({\mathfrak m})$ for the cardinality of ${\mathcal O}^\xi(X)$ for any set $X$ of cardinality ${\mathfrak m}.$ Notice:

• $2^{\mathfrak m}={\mathcal O}({\mathfrak m})$ and so $\aleph({\mathfrak m})=\aleph({\mathcal O}({\mathfrak m})).$

Since $\aleph({\mathcal O}^\xi(X))\ge|\xi|^+,$ there must be a least ordinal $\gamma$ such that $\aleph({\mathfrak m})<\aleph({\mathcal O}^\gamma({\mathfrak m})).$ This $\gamma$ is necessarily an infinite  limit ordinal. One concludes the proof by showing:

• For any $\xi$ with $1<\xi<\gamma,$ one has $2^{\mathfrak m}<{\mathcal O}^\xi({\mathfrak m})\le 2^{2^{\mathfrak m}}.$
• $\gamma\ge{\rm cf}(\aleph({\mathfrak m})).$

A. Appendix.

I would like to review the results relating $\aleph(X)$ and ${\mathcal P}^2(X)$ in a way that gives some additional information.

Definition. For an infinite set $X$, set $\aleph^*(X)=\{\alpha:\exists f:X\to\alpha$ surjective$\}$ and $\aleph_*(X)=\aleph^*(X)\cup\{0\}$.

Fact. $\aleph^*(X)$ is a set and $\aleph_*(X)$ is an initial ordinal.

Proof. Suppose that $\pi:X\to Y$ is a surjection. Define $E_\pi\subseteq X^2$ by $xE_\pi y$ iff $\pi(x)=\pi(y)$. Clearly, $E_\pi$ is an equivalence relation on $X$, and there is an obvious bijection ${}[x]_{E_\pi}\mapsto\pi(x)$ between the quotient $X/E_\pi$ and $Y$. 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 $\alpha$ is the surjective image of $X$ iff there is an equivalence relation on $X$ whose quotient is well-orderable and has size $|\alpha|$. This shows that $\aleph^*(X)$ is a set and that if $\aleph_*(X)$ is an ordinal, then it is an initial ordinal. But this follows from noticing that if $0<\beta<\alpha$ and $\pi:X\to \alpha$ is surjective, then $\pi^*:X\to\beta$ is surjective, where $\pi^*(x)=\pi(x)$ if $\pi(x)<\beta$, and $\pi^*(x)=0$ otherwise. ${\sf QED}$

Fact. $\aleph(X)\le\aleph_*(X)$.

Proof. If $g:\alpha\to X$ is injective and $0<\alpha$, let $f:X\to\alpha$ be the function $f(x)=\beta$ if $x=g(\beta)$ and $f(x)=0$ otherwise. Then $f$ is surjective. ${\sf QED}$.

It is possible that $\aleph(X)=\aleph_*(X)$. For example, this holds if $X$ is well-orderable. It is also possible that $\aleph(X)<\aleph_*(X)$. For example, under determinacy $\aleph({\mathbb R})=\omega_1$ but $\Theta=\aleph_*({\mathbb R})$ is much larger.

Fact. If $\pi:X\to Y$ is surjective, then $\pi^{-1}={\mathcal P}(Y)\to{\mathcal P}(X)$ is injective. $\Box$

Corollary. ${\mathcal P}(\aleph(X))\preceq{\mathcal P}^2(X\times X)$.

Proof. Define a map $\pi:{\mathcal P}(X\times X)\to\aleph(X)$ by setting $\pi(R)=0$ for a relation $R\subseteq X\times X$ unless $R$ is a well-ordering of its field in order type $\alpha$, in which case $\pi(R)=\alpha$. This is a surjection. ${\sf QED}$

Corollary. ${\mathcal P}(\alpha^+)\preceq{\mathcal P}^2(\alpha)$ for all ordinals $\alpha$.

Proof. This is clear by induction if $\alpha$ is finite. Otherwise, $\alpha\sim\alpha\times\alpha$. ${\sf QED}$

Corollary. ${\mathcal P}(\aleph(X))\preceq{\mathcal P}^2(X)$ if $X\sim Y^2$ for some $Y$.

Proof. Again, it suffices to consider infinite $X$. In this case, $\aleph(X)=\aleph(Y)$ by Homework problem 3. ${\sf QED}$

Corollary. $\aleph({\mathcal P}^2(X))\ge\sup\{\aleph({\mathcal P}^2(\alpha)):\alpha\in\aleph_*(X)\}$ $\ge\sup\{\aleph({\mathcal P}(\alpha^+)):\alpha\in\aleph_*(X)\}.$

Proof. If $\alpha<\aleph_*(X)$ then there is a surjection from ${\mathcal P}(X)$ onto ${\mathcal P}(\alpha)$. This is clear if $\alpha=0$. Otherwise, if $\pi:X\to\alpha$ is onto, consider $\hat\pi:{\mathcal P}(X)\to{\mathcal P}(\alpha)$ given by $\hat\pi(A)=\pi[A]$

Hence, there is an injection of ${\mathcal P}^2(\alpha)$ into ${\mathcal P}^2(X)$. The result follows. ${\sf QED}$

Corollary. ${\mathcal P}(\aleph(X))\preceq{\mathcal P}^2(X)$ if $\aleph(X)$ is a successor cardinal. $\Box$

Corollary. Suppose that $\kappa>0$ is the $\kappa$-th initial ordinal. If $\kappa=\aleph(X)$, then ${\mathcal P}(\aleph(X))\preceq{\mathcal P}^2(X)$

Proof. Let $\tau$ be a bijection between the set of initial ordinals below $\kappa$ and $\kappa$. The map $\pi:{\mathcal P}(X)\to\kappa$ given by $\pi(A)=\tau(|A|)$ if $A$ is well-orderable, and $\pi(A)=0$ otherwise, is a surjection. ${\sf QED}$

Corollary. If $X$ is infinite and Dedekind-finite, then ${\mathcal P}(\omega)\preceq{\mathcal P}^2(X)$.

Proof. $\aleph(X)=\omega$ is the $\omega$-th initial ordinal. ${\sf QED}$

Corollary. Suppose that $\aleph(X)=\aleph({\mathcal P}^2(X))$. Then $X$ is not equipotent to a square and $\aleph(X)=\aleph_*(X)=\aleph_\lambda$ for some (infinite) limit ordinal $\lambda<\aleph_\lambda$. $\Box$

Notice that, under choice, $\aleph(X)$ is always a successor cardinal; I do not know if the conclusion of the corollary is consistent.

### 7 Responses to 580 -Some choiceless results (5)

1. […] 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 […]

2. […] 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 […]

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

4. […] 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 […]

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

6. […] 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 […]

7. […] 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 […]