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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: