## 116c- Homework 7

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 ${sf 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 ${rm 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 and $(gamma_alpha:alpha 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 ${rm cf}(beta)={rm cf}(kappa)$. We circunvent 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 ${rm cf}(beta)={rm cf}(gamma)$.

To implement this idea, let $(kappa_i:i<{rm cf}(kappa))$ be an increasing sequence of regular cardinals cofinal in $kappa$, with ${rm cf}(kappa). 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_0cup 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$.