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<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 {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)<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_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.


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: