Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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