## 116c- Homework 7

May 20, 2008

Homework 7

Due Wednesday, May 28 at 2:30 pm.

Update. I present here a quick sketch of the solution of Exercise 3.(b). See Lecture 18, where it is shown that the result actually holds in $\mathsf{ZF}$, although the proof uses choice.

Let $<$ and $\prec$ be two well-orderings of a set $X$. We want to find a subset of $X$ of the same size as $X$ where the two well-orderings coincide. Let $\kappa=|X|$. By combining with an isomorphism between $(X,<)$ and its order type, we may assume that $X$ is an ordinal and $<=\in$. By restricting attention to the subset $\kappa$ of $X$, we may assume $\prec$ is a well-ordering of $\kappa$. By further restricting to the subset of $\kappa$ of order type $\kappa$ under $\prec$, we may assume that $\mathrm{ot}(\kappa,\prec)=\kappa$ as well.

Assume first that $\kappa$ is regular. The result follows easily. The desired set $Y$ can be built by a straightforward recursion: Given $\beta<\kappa$ and $(\gamma_\alpha:\alpha<\beta)$ a sequence of elements of $\kappa$ increasing under both well-orderings, regularity ensures that the sequence is bounded under both well-orderings, and we can find $\gamma_\beta$ which is larger than all the previous $\gamma_\alpha$ under both orderings.

The argument for $\kappa$ singular is slightly more delicate. Namely, we may not be able to carry out the construction above since the sequence could be unbounded in one of the orderings when $\mathrm{cf}(\beta)=\mathrm{cf}(\kappa)$. We circumvent the problem by only considering ordinals $\beta$ whose cofinality is larger than the cofinality of $\kappa$. Notice that if an increasing sequence of order type $\beta$  is unbounded in an ordinal of cofinality $\gamma$, then $\mathrm{cf}(\beta)=\mathrm{cf}(\gamma)$.

To implement this idea, let $(\kappa_i:i<\mathrm{cf}(\kappa))$ be an increasing sequence of regular cardinals cofinal in $\kappa$, with $\mathrm{cf}(\kappa)<\kappa_0$. Consider the subset $\kappa_0$. It must contain a subset of size $\kappa_0$ where $\prec$ coincides with $\in$. By the remark above, this subset $B$ is bounded in $(\kappa,\prec)$. Let $A$ denote the shortest initial segment of $(\kappa,\prec)$ containing $B$. By removing from $\kappa$ the set $\kappa_0\cup A$, we are left with a set of size $\kappa$, and any ordinal there is larger than the elements of $B$ under both orderings. The induction continues this way, by considering at stage $i$ a set of size $\kappa_i$.