# Range of an ordinal valued function

If $(X,<)$ is a linear order, then let $X^*$ denote $(X,>)$, let $o(X)$ denote the least ordinal which does not embed in $X$, let $\overline{o}(X)$ denote $\max(o(X),o(X^*))$.

I am trying to find all possible values of $\overline{o}$. Here is what I know:

-$o,\overline{o}$ can take any successor value, since $o(\alpha) = \overline{o}(\alpha) = \alpha+1$ if $\alpha \in Ord$.

-$o$ can take any non zero additively indecomposable value, since if $0 <\alpha$ is an additively indecomposable ordinal, then $o((\sum \limits_{\beta < cf(\alpha)} \varphi(\beta)^*)^*) = \alpha$, where $\varphi: cf(\alpha) \rightarrow \alpha$ is strictly increasing and cofinal.

-Using this, one can prove by induction that $o$ can take any non-zero value.

-$\overline{o}$ can take any singular additively indecomposable value, since if $\alpha$ is an additively indecomposable singular ordinal, then $\overline{o}((\sum \limits_{\beta < cf(\alpha)} \varphi(\beta)^*)^*) = \alpha$. (same conditions for $\varphi$)

-Using this, one can prove by induction that $\overline{o}$ can take any singular value.

-$\overline{o}$ can take any infinite successor cardinal value, since if $\alpha$ is an infinite ordinal, and $\mathbb{Q}((X_{\beta})_{\beta < \alpha})$ is the field of fractions with $\alpha$ indeterminates andcoefficients in $\mathbb{Q}$, ordered so that $\mathbb{Q}[X_{\beta}] < X_{\beta}'$ when $\beta < \beta'$, then $o(\mathbb{Q}((X_{\beta})_{\beta < \alpha}) = \alpha^+$.

-$\overline{o}$ doesn't take the value $\omega_0$ (is it the time to say that I am working in ZFC?) because if $\overline{o}(X)$ is infinite, then $X$ is infinite and so it hosts an infinite strictly monotone sequence. It is trivial that it doesn't take the value $0$ either.

-Piecing all this together, we see that $\overline{o}$ takes at least any value except some (possibly all) regular limit cardinals.

I haven't been able to prove that $\overline{o}$ doesn't take any other value, nor have I been able to find a linear order whose $\overline{o}$ is a regular limit cardinal. Does someone know if the range contain some regular limit cardinals?

• I suspect that the range contains all ordinals except for the weakly compact cardinals. A cardinal $\kappa$ is weakly compact iff every linear order of cardinality $\kappa$ contains an increasing or decreasing subsequence of order type $\kappa$. $\overline{o}(X) \ge \kappa$ implies that $|X| \ge \kappa$, and so has a monotone subsequence of order type $\kappa$, so $\overline{o}(X)$ cannot be $\kappa$. Unfortunately, I don't see how to prove the other direction, but I suspect that the existence of a linear order without a monotone subsequence of length $\kappa$ should get you what you want. Nov 28, 2016 at 8:19
• This is true: if $X$ is a linear order of size $\kappa$ without any monotone $\kappa$-sequence, then fixing a bijection $f:X \rightarrow \kappa$, the linear order $Y:= \sum \limits_{x \in X} f(x)$ satisfies $o(Y) = \kappa$ and $o(Y^*) \leq \kappa$. Nov 28, 2016 at 8:29
• (this is assuming $\kappa$ is regular, and the notation $\sum \limits_{x \in X} f(x)$ denotes $\bigcup \limits_{x \in X} f(x) \times \{x\}$ ordered by $(\alpha,x) \prec (\beta,y)$ iff $x < y$ or $(x = y$ and $\alpha < \beta$)) Nov 28, 2016 at 8:36
• Great, you're done then! Nov 28, 2016 at 8:38
• Yes, this answer is actually nicer than I expected the undecidability regarding regular limit cardinals would allow. Feel free to post your comment as an anwser and I'll accept it. Nov 28, 2016 at 8:40

The range contains all ordinals except for $0, \omega,$ and the weakly compact cardinals.
One formulation of weakly compact cardinal is a cardinal $\kappa$ such that every linear order of cardinality $\kappa$ contains an increasing or decreasing subsequence of order type $\kappa$. Then if $\overline{o}(X) \ge \kappa$, this implies $|X| \ge \kappa$, and so $X$ has a monotone subsequence of order type $\kappa$. Thus $\overline{o}(X)$ cannot be $\kappa$.
nombre figured out the other direction: if $\kappa$ is an uncountable regular cardinal that is not weakly compact, then there exists a linear order of cardinality $\kappa$ that does not contain a monotone subsequence of order type $\kappa$. Then we can fix a bijection $f:X \to \kappa$, and the linear order $Y := \sum_{x \in X} f(x) = \bigcup_{x \in X} f(x) \times \{x\}$ will satisfy $\overline{o}(Y) = \kappa$.