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 \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.


One Response to 116c- Homework 7

  1. […] amusing application of the fact that is that the result of Exercise 3 from Homework 7 holds in , although the proof I wrote there uses choice. Namely, work in and consider two […]

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 )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: