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.