# Well ordering agreeing with ordinal ordering on a cardinal

This is an exercise from Kunen book - Set theory, an introduction to independence proofs.

Let $\kappa$ be an infinite cardinal and $\triangleleft$ any well-ordering of $\kappa$. Show that there is an $X \subset \kappa$ such that:

1. $\vert X \vert = \kappa$,
2. $\triangleleft$ and $<$ agree on $X$.

I'm trying to build $X$ by transfinite induction, but I don't succeed to prove that its cardinal can be equal to $\kappa$.

• Do you know the Erdos-Dushnik-Miller theorem? – Asaf Karagila Jun 18 '15 at 20:53
• @Asaf. Unfortunately not. This is an exercise on chapter 1 of the book at page 45. So nothing "complex" is yet introduced. However, the exercise is starred which means a more difficult one. – mathcounterexamples.net Jun 18 '15 at 21:00
• – Asaf Karagila Jun 18 '15 at 21:39

First let's prove this for $\kappa$ regular:

WLOG, assume the order-type of $\triangleleft$ is again $\kappa$. Now suppose I have a set $A\subseteq \kappa$ on which $\triangleleft$ agrees with $<$ and $\vert A\vert<\kappa$; then (since $\kappa$ is regular) there must be $\kappa$-many elements of $\kappa$ which are $>$-greater than every element of $A$; but then, since $A$ has order-type $\kappa$, one (in fact, $\kappa$-many) must also be $\triangleleft$-greater than every element of $A$, so $A$ can be strictly extended to a longer set on which $<$ and $\triangleleft$ agree.

Now what about the singular case? Let $cf(\kappa)=\lambda$, $\kappa=\bigcup_{\alpha<\lambda} A_\alpha$ where

• if $\alpha<\beta$ then each element of $A_\alpha$ is $<$-less than each element of $A_\beta$, and

• the $A_\alpha$ have increasing regular cardinalities $\mu_\alpha$,

and again WLOG assume $\triangleleft$ has order type $\kappa$ on $\kappa$ and ordertype $\mu_\alpha$ on each $A_\alpha$. Define a new ordering $\prec$ on $\lambda$, given by $$\alpha\prec\beta\iff \sup_{\triangleleft}(A_\alpha)\triangleleft\sup_{\triangleleft}(A_\beta).$$ Note that because the $\triangleleft$-order on $A_\alpha$ has ordertype $\mu_\alpha$, and the $\mu_\alpha$s are distinct, $\prec$ is actually a linear order on $\lambda$, and moreover is easily seen to be a well-order. So since $\lambda$ is regular, pick a simultaneously $\prec$- and $<$-increasing sequence $\{\theta_\eta: \eta<\lambda\}$ of elements of $\mu$. Since $\lambda$ is regular, this sequence is $<$-cofinal in $\lambda$.

Now by definition of $\prec$ we may recursively pick, for each $\eta<\lambda$, a $\triangleleft$-cofinal subset $C_{\theta_\eta}$ of $A_{\theta_\eta}$ - on which $\triangleleft$ and $<$ agree! - such that $\eta<\gamma$ implies that every element of $C_{\theta_\eta}$ is $\triangleleft$-less than every element of $C_{\theta_\gamma}$. Since each $A_{\theta_\eta}$ is of regular cardinality, $$C=\bigcup_{\eta<\lambda} C_{\theta_\eta}$$ has cardinality $\kappa$, and by construction $<$ and $\triangleleft$ agree on $C$.

• I'm now terrified I swapped "$<$," "$\triangleleft$," and "$\prec$" somewhere in there . . . :P – Noah Schweber Jun 18 '15 at 21:39
• Nice argument! I remember having a hard time with this problem during my grad school days. – hot_queen Jun 18 '15 at 21:54