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

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


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.