Let $\kappa$ be a cardinal. I want to show that every ordinal $\alpha < \kappa^+$ can be embedded (as an order) in any interval of $\kappa^{<\omega}$, ordered lexicographically.

This is exactly how Jech states the result in his paper about trees (page 3). He doesn't define the order explicitly, but I think that he refers to this (so if $x \subseteq y$ then $x \leq y$).

I tried to adapt the steps for the similar statement about the rational numbers (Embedding ordinals in $\mathbb{Q}$), but I got nowhere.

Update: as pointed out in the comments, my guess about what the author means by "lexicographic order" is very unlikely to be correct, since then $\kappa^{<\omega}$ wouldn't be dense.

  • $\begingroup$ "Any interval" seems shady : what about an interval containing only one point ? $\endgroup$ Apr 25, 2016 at 15:25
  • $\begingroup$ This is not possible because $\kappa^{<\omega}$ is dense. $\endgroup$
    – aerdna91
    Apr 25, 2016 at 15:35
  • $\begingroup$ I would try to prove by induction on $\alpha<\kappa^+$ that there is an embedding $\phi:\alpha\to\kappa^{<\omega}$. The succesor case has no problem since given an embedding $\phi:\alpha\to\kappa^{<\omega}$ we can "switch to the right" by the map $h:\kappa^{<\omega}\to\kappa^{<\omega}$ defined by $h(s)=0\wedge s$. I just don't know how to prove the limit case, but it won't be necessary if in addition we have $|\kappa^\omega|>\kappa$ $\endgroup$
    – Darío G
    Apr 25, 2016 at 16:18
  • $\begingroup$ @aerdna91: Are you quite sure that this is a dense order? It appears to me that $\langle 2,0\rangle$ is the immediate successor of $\langle 2\rangle$, for instance. $\endgroup$ Apr 25, 2016 at 16:59
  • $\begingroup$ Of course you and @CaptainLama are right. My bad. I have updated the question. $\endgroup$
    – aerdna91
    Apr 25, 2016 at 17:20

1 Answer 1


Your original understanding of the lexicographic order on $\kappa^{<\omega}$ is correct. The claim isn’t true as stated, but something that should be good enough for the intended purpose is true.

Proposition. Each ordinal $\alpha<\kappa^+$ can be order-embedded in $\kappa^{<\omega}$.

Proof. Suppose that $\varphi:\alpha\to\kappa^{<\omega}$ is an order embedding. Then

$$\varphi^+:\alpha+1\to\kappa^{<\omega}:\xi\mapsto\begin{cases} 0^\frown\varphi(\xi),&\text{if }\xi\in\alpha\\ \langle 1\rangle,&\text{if }\xi=\alpha \end{cases}$$

is an order-embedding of $\alpha+1$. If $\alpha<\kappa^+$ is a limit ordinal, and each $\beta<\alpha$ can be order-embedded in $\kappa^{<\omega}$, let $\lambda=\operatorname{cf}\alpha\le\kappa$, and let $\langle\alpha_\xi:\xi<\lambda\rangle$ be a strictly increasing sequence cofinal in $\alpha$ such that $\alpha_0=0$. For $\xi<\lambda$ let $\beta_\xi$ be the order type of the interval $I_\xi=[\alpha_\xi,\alpha_{\xi+1})$; clearly $\beta_\xi\le\alpha_{\xi+1}<\alpha$, so there is an order-embedding $\varphi_\xi$ of $I_\xi$ into $\kappa^{<\omega}$. For $\eta\in\alpha$ let $\xi(\eta)<\lambda$ be such that $\eta\in I_{\xi(\eta)}$, and let


then $\varphi$ order-embeds $\alpha$ in $\kappa^{<\omega}$. $\;\dashv$

Now let $x,y\in\kappa^{<\omega}$ be such that $x\prec y$, where $\preceq$ is the lexicographic order on $\kappa^{<\omega}$. Assume further that if $y=x^\frown z$, at least one term of $z$ is not $0$. Then there is an $x'\succeq x$ such that $x'\prec y$ and $x'$ is not an initial segment of $y$. Let

$$I=\left\{z\in\kappa^{<\omega}:x'\subsetneqq z\right\}\;$$

then $I$ is order-isomorphic to $\kappa^{<\omega}$, and $I\subseteq(x',y)\subseteq(x,y)$. Thus, each ordinal less than $\kappa^+$ order-embeds into any interval $(x,y)$ of $\langle\kappa^{<\omega},\preceq\rangle$ such that $y$ is not an extension of $x$ by a string of zeroes.

  • $\begingroup$ Thank you very much for this amazing reply. It was really helpful, because I could adapt your proof (with almost no changes) to show that the statement holds for the set of eventually-zero-sequences in $\kappa^\omega$, which is sufficient for my purpose. $\endgroup$
    – aerdna91
    May 6, 2016 at 10:30
  • $\begingroup$ @aerdna91: You're very welcome. $\endgroup$ May 6, 2016 at 11:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .