## 116c- Lecture 7

April 22, 2008

We presented the proof that “$k$-trichotomy” implies choice. The following is still open:

Question. (${\sf ZF}$) Assume that $X$ is non-well-orderable. Is there a countably infinite family of pairwise size-incomparable sets?

We mentioned a few (familiar) statements that fail in the absence of choice, like the existence of bases for any vector space, Tychonoff’s theorem, or the “surjective” version of the Schröder-Bernstein theorem.

We defined addition, multiplication and exponentiation of cardinals, and verified that addition and multiplication are trivial. We stated the continuum hypothesis ${\sf CH}$, and the generalized continuum hypothesis ${\sf GCH}$.

We want to prove (in subsequent lectures) a few non-trivial results about the behavior of exponentiation. In order to do this, we need the key notion of cofinality. We proved a few basic facts about cofinality and defined regular cardinals.

## 116c- Homework 3

April 22, 2008

Update. Now due Wednesday, April 30 at 2:30 pm.

Corrections. (Thanks to Fedor Manin for noticing these.)

• On Exercise 2.(c), assume in addition that $(\lambda,\alpha)$ satisfies the conditions of $(\alpha,\beta)$ in item 2.(a); this should really be all that is needed of 2.(c) for later parts of the exercise.
• On Exercise 2.(f), we also need $n>0$.

Update. Here is a quick sketch of the proof of the Milner-Rado paradox.

First notice that the result is clear if $\kappa=\omega$, since we can write any $\alpha<\omega_1$ as a countable union of singletons. So we may assume that $\kappa$ is uncountable.

Notice that $|\kappa^{\cdot\rho}|=\kappa$. This can be checked either by induction on $\rho<\kappa^+$, or by using the characterization of ordinal exponentiation in terms of functions of finite support.

Notice that the function $\alpha\mapsto\omega^{\cdot \alpha}$ is normal. By the above, it follows that $\omega^{\cdot\lambda}=\lambda$ for all uncountable cardinals $\lambda$. In particular, it suffices to prove the result for ordinals $\alpha$ that are an ordinal power of $\kappa$, since these ordinals are cofinal in $\kappa^+$, and a representation as desired for an ordinal gives (by restriction) such a representation for any smaller ordinal.

By the above, $\kappa^{\cdot\rho}=\omega^{\cdot\kappa\cdot\rho}$ for any $\rho$. It is easy to see that for any $\delta$, if $\alpha<\omega^{\cdot\delta}$, then the interval $\null[\alpha,\omega^{\cdot\delta})$ is order isomorphic to $\omega^{\cdot\delta}$; this can be proved by a straightforward induction on $\delta$.

For any $\alpha<\kappa^+$, we can write $\kappa^{\cdot\alpha+1}=\bigcup_{\nu<\kappa}A_\nu$, where $A_\nu=[\kappa^{\cdot \alpha}\cdot\nu,\kappa^{\cdot\alpha}\cdot(\nu+1))$ so it has order type $\kappa^{\cdot\alpha}$.

Also, if $\alpha$ is a limit ordinal below $\kappa^+$, then we can write $\alpha=\sup_{\nu<\mbox{\small cf}(\alpha)}\beta_\nu$ for some strictly increasing continuous sequence $(\beta_\nu:\nu<\mbox{cf}(\alpha))$ cofinal in $\alpha$. Let $A_0=\kappa^{\cdot\beta_1}$ and $A_\nu=[\kappa^{\cdot\beta_\nu},\kappa^{\cdot\beta_{\nu+1}})$ for $0<\nu<\mbox{cf}(\alpha)$. Then $\kappa^{\cdot\alpha}=\bigcup_\nu A_nu$ and each $A_\nu$ has order type $\kappa^{\cdot\beta_{\nu+1}}$.

[That the sequence $\beta_\nu$ is continuous (at limits) ensures that the $A_\nu$ cover $\kappa^{\cdot \alpha}$. That they have the claimed order type follows from the “straightforward inductive argument” three paragraphs above.]

So we have written each $\kappa^{\cdot\rho}$ as an increasing union of $\sigma$ many intervals whose order types are ordinal powers of $\kappa$, and $\sigma$ is either $\kappa$ or $\mbox{cf}(\rho)$. Now proceed by induction. We may assume that each ordinal below $\kappa^{\cdot\rho}$ can be written as claimed in the paradox. In particular, each $A_\nu$, having order type an ordinal smaller than $\kappa^{\cdot\rho}$, can be written that way, say $A_\nu=\bigcup_n A_{\nu,n}$ where $\mbox{ot}(A_{\nu,n})<\kappa^{\cdot n}$. If $\sigma=\omega$, this immediately gives the result for $\kappa^{\cdot\rho}$: Take $X_0=\emptyset$ and $X_{2^m(2n+1)}=A_{m,n}$. Clearly their union is $\kappa^{\cdot\rho}$ and they have small order type as required. If $\sigma>\omega$, take $X_0=X_1=\emptyset$ and $X_{n+2}=\bigcup_\nu A_{\nu,n}$. Again, their union is $\kappa^{\cdot\rho}$, and $\mbox{ot}(X_{n+2})$ is at most the order type of concatenating $\kappa$ many copies of $\kappa^{\cdot n}$ [it is here that we use that $A_\nu for $\nu<\mu$], so $\mbox{ot}(X_{n+2})\le\kappa^{\cdot n+1}$.