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

  • 1
    $\begingroup$ Do you know the Erdos-Dushnik-Miller theorem? $\endgroup$ – Asaf Karagila Jun 18 '15 at 20:53
  • $\begingroup$ @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. $\endgroup$ – mathcounterexamples.net Jun 18 '15 at 21:00
  • 2
    $\begingroup$ Relevant. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.