# Heights of several interesting posets

Let the height of a poset $P$ be the supremum of ordinals that are order types of all well-ordered subsets of $P$ (with order inherited from $P$).

Define several sets of total functions, in each case partially ordered by eventual domination:

1. computable functions $\mathbb{N} \to \mathbb{N}$
2. arithmetic functions $\mathbb{N} \to \mathbb{N}$ (i.e. the set of all pairs $(n, f(n))$ is an arithmetical set)
3. all functions $\mathbb{N} \to \mathbb{N}$
4. all functions $\mathbb{N} \to \mathbb{R}$
5. elementary functions $\mathbb{R} \to \mathbb{R}$
6. real analytic functions $\mathbb{R} \to \mathbb{R}$
7. all functions $\mathbb{R} \to \mathbb{R}$
8. all functions $\omega_1 \to \omega_1$
9. Any other interesting cases?

What is the height of each of these posets? Is anything of these a known open problem? Has anything been proven to be independent of $ZFC$?

-
Anything whose cardinality depends on the value of the continuum is independent of ZFC. –  Asaf Karagila Nov 29 '11 at 8:44
What do you mean by eventual domination in case 5, 6, and 7? Mod finite or off a compact set or something else? –  Juris Steprans Nov 29 '11 at 13:14
@Asaf: not exactly anything, right? Surely $c \neq \aleph_\omega$ is true in ZFC... –  Maxime Bourrigan Nov 29 '11 at 16:12

For (3) you can attain any ordinal $\alpha < \omega_2$. This can be shown by using transfinite induction. As an induction hypothesis on $\alpha$ assume that for any strictly increasing $f:\mathbb{N} \to \mathbb{N}$ there is a sequence $f_\xi$ for ${\xi\in\alpha + 1}$ ordered by eventual domination such that $f_\alpha = f$. The first case to consider is $\alpha = \omega_1 + 1$. Construct $f_\xi$ for $\xi\in\omega_1$ by using a countable induction at each stage to fill in the gap between $f_\xi$ and $f= f_{\omega_1}$.

Now given an arbitrary $\alpha < \omega_2$ either $\alpha = \beta+1$ --- in which case take $f'= f/2$ and add $f$ to the well ordered chain of length $\beta$ ending with $f'$--- or $\alpha$ is a limit. If $\alpha$ is a limit of cofinality $\omega_1$ and $f$ is given start with a chain $f_\xi$ ordered by eventual domination of length $\omega_1+1$ ending with $f$ and choose a sequence $\alpha_\xi$ for ${\xi\in\omega_1}$ cofinal in $\alpha$. Then use the induction hypothesis to fill in the interval between $f_{\alpha_\xi}$ and $f_{\alpha_{\xi+1}}$ with a chain of order type $\mu$ such that $\alpha_\xi + \mu = \alpha_{\xi + 1}$. The countable cofinality case is similar.

This is the best that can be done because in the model obtained by adding $\aleph_3$ Cohen reals to a model of CH there are no chains of length $\omega_2$. Of course there are always chains of length $\mathfrak{b}$ and $\mathfrak{b}$ can be arbitrarily large.

-

Let me start out with a partial answer.

The ordinals in 1 and 2 are precisely $\omega_1$. To see that they are at least this large, observe that the partial orders of 1 and 2 both admit a countable dense linear suborder, a copy of $\mathbb{Q}$, and every countable ordinal embeds into $\mathbb{Q}$; thus, every countable ordinal arises as a suborder. (The copy of $\mathbb{Q}$ arises even for the class of functions $\mathbb{N}\to \{0,1\}$.) To see that the heights are at most $\omega_1$, observe that the partial orders of 1 and 2 are countable and hence $\omega_1$ itself cannot arise in a suborder.

The ordinals in the other cases are strictly larger than $\omega_1$, in light of Hausdorff gaps.

-