MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\mathbb{R}^\mathbb{R}$ be the set of functions $\mathbb{R}\to\mathbb{R}$ patially ordered by eventual domination. Obviously, every ordinal below $\omega_1$ can be embedded in $\mathbb{R}^\mathbb{R}$ using only constant functions.

What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?

share|cite|improve this question
If one of two functions eventually dominates another, you can tell which by evaluating on integers. So the cardinality of this ordinal is at most $\mathbb R$, so an upper bound is the Hartogs function of $\mathbb R$. – Will Sawin May 24 '13 at 19:16
Certainly $\mathfrak b$, the unbounding number, can be embedded: Use functions on $\omega$, and interpolate them linearly. Also $\mathfrak b+1$ can be embedded, since for the embedding of $\mathfrak b$ we may use functions from $\omega$ into `$\{-1, -\frac12, -\frac13, \}$ etc. This can be continued.. At the moment I don't see if this gets us to everything below $\mathfrak b^+$, however. – Goldstern May 24 '13 at 19:37
You can do $\mathfrak{c}$: Suppose $r_\alpha$, $\alpha\lt\mathfrak{c}$ are distinct reals, if $f_\alpha$ is the characteristic function of $\lbrace r_\beta : \beta\lt\alpha\rbrace$ then this sequence is increasing under total domination. This is the best you can do for total domination. Assuming CH, this is also the best you can do for eventual domination because of the Erdos-Rado theorem. I'm not sure what happens if you don't assume CH. – François G. Dorais May 24 '13 at 19:43
Err... The Erdos-Rado argument only shows you can't do $(2^{\mathfrak{c}})^+$ (otherwise you can get a subsequence of length $\mathfrak{c}^+$ which is totally dominating on some tail $[n,\infty)$). – François G. Dorais May 24 '13 at 19:48
François, it is a wonderful idea, but I had interpreted the OP to be concerned with the relation: $f$ is eventually dominated by $g$, when $f(x)\lt g(x)$ for all sufficiently large $x$. Can you make your example work with that notion of eventual domination? – Joel David Hamkins May 24 '13 at 19:49
up vote 14 down vote accepted

Let me get things started with some simple observations.

Note that given any countable sequence of functions $f_n$, we can by diagonalization construct a function eventually dominating all of them, $f(x)=\max_{n\leq x}f_n(x)$. It follows that we may by transfinite recursion construct an embedding of $\omega_1$ into your order: at successor stages, add one to the previous function; at limit stages, use the diagonalization just described.

So actually, since $\mathbb{R}$ is order-isomorphic to bounded intervals of itself, we can therefore also embed $\omega_1$ into the order many times, on top of one another. So this gives strictly larger ordinals mapping in.

More generally, the bounding number $\mathfrak{b}$ is the size of the smallest unbounded family of functions, and any family of size less than $\mathfrak{b}$ will be bounded above. Thus, the recursive construction actually shows that we can find an embedding of $\mathfrak{b}$ into $\mathbb{N}^{\mathbb{N}}$ under eventual domination. Thus, we also get strictly larger ordinals than $\mathfrak{b}$ embedding in, by using the bounded-interval trick again.

There are diverse independence results concerning the exact value of $\mathfrak{b}$. Under CH, it is the same as the continuum, of course, but when CH fails, it can be far larger than $\omega_1$.

Using Péter's idea, once we have a map from $\mathfrak{b}$ into the order, then we may conclude that the class of ordinals that map into the order is closed under sums of length $\mathfrak{b}$. Thus, any ordinal up to $\mathfrak{b}^+$ is is order-embeddable into $\mathbb{R}^\mathbb{R}$ under eventual domination. So $\mathfrak{b}^+$ is a lower bound for your desired ordinal.

I guess the same idea shows that whenever an ordinal $\kappa$ embeds in, then the class of ordinals will be closed under sums of length $\kappa$, and so all ordinals up to $\kappa^+$ will also map in. Thus, the smallest ordinal not embedding in must be a cardinal, and furthermore, it must be a regular cardinal for the same reason.

Update. It is relatively consistent that the answer is $\mathfrak{c}^+$, even when the continuum $\mathfrak{c}$ is very large, and much larger than $\mathfrak{b}$. The reason is that by forcing, we can undertake a very long forcing iteration of length $\kappa$ to add a dominating real at each stage, and thereby get a model with continuum $\kappa$, such that $\kappa$ embeds into the order (and so the smallest ordinal not embedding into the order is $\kappa^+$). Now, the point is that with further ccc forcing, we can make $\mathfrak{b}$ small or whatever we like, but meanwhile, we still have our old functions showing that $\kappa$ maps into the order.

share|cite|improve this answer
Note also that it is consistent with $\text{ZF}+\neg\text{AC}$ that the answer is $\omega_1$, since it is consistent with ZF that there is no $\omega_1$-sequence of distinct reals. – Joel David Hamkins May 24 '13 at 21:20
Well, thanks for accepting my answer, although I think things are not yet completely settled. We've proved $\mathfrak{b}^+$ as a lower bound on your ordinal and also proved that this is not necessarily the answer, since $\mathfrak{c}^+$ can arise even when this is larger than $\mathfrak{b}^+$. The question remains whether it can be less than $\mathfrak{c}^+$ or not, and if so, what values are possible. – Joel David Hamkins May 25 '13 at 0:26
Let $\mathfrak b'$ be the least ordinal that cannot be embedded into $\omega^\omega$. Your argument really shows that $\mathfrak b'$ can be $\mathfrak c^+ > \mathfrak b$. Perhaps the ordinal taumu wants is really $\mathfrak b'$? ($\mathfrak b'$ is clearly a lower bound. – Goldstern May 26 '13 at 13:36
Goldstern, yes, I agree. But do we have any model where we get different ordinals by using $\omega^\omega$ versus $\mathbb{R}^{\mathbb{R}}$? – Joel David Hamkins May 26 '13 at 13:53
I should have said "Perhaps $\mathfrak b^{\tau\mu}=\mathfrak b'$?" I don't know any bounds for $\mathfrak b'$ that have not been mentioned already, but $\mathfrak b'$ looks like it is better suited than $\mathfrak b^{\tau\mu}$ to be compared to other well-known cardinals characteristics, so it would be helpful to know that the two are equal. (The ccc of $^mathbb R$ makes it difficult to distinguish the two, I think.) – Goldstern May 26 '13 at 14:32

One can define an eventually increasing sequence $\{f_\alpha:\alpha<\omega_1\}$ by transfinite recursion on $\alpha$. By inserting sequences in the intervals $(f_\alpha(x),f_{\alpha+1}(x))$ we can see that $\omega_1$-sums (and of course, $\omega$-sums) do not lead out of the representable ordinals. This gives that all ordinals $<\omega_2$ are representable and this is clearly sharp if CH holds, by Will's above answer. If CH fails, larger ordinals can be represented, if, e.g. Martin's Axiom holds.

share|cite|improve this answer
Sounds reasonable, but would you mind elaborating the “inserting sequences in the intervals”-part? – The User May 24 '13 at 19:54
The point is that because $\mathbb{R}$ is order-isomorphic to an interval (no matter how small), you can essentially map the whole order $\mathbb{R}^{\mathbb{R}}$ into the region between any two functions $f\lt\lt g$, with $f$ dominated by $g$. – Joel David Hamkins May 24 '13 at 19:57

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.