Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been pondering the following question.

How can we measure the amount of "space" above an element $p$ in a partially ordered set $P$?

One way would be to try to cram the elements of increasingly large ordinals into the space above $p$, respecting order. The least ordinal whose elements "don't fit" is then a measure of the amount of space above $p$ in $P$.

This suggests the following definition. (Recall that an order monomorphism preserves strict order relationships).

Definition. Given a partially ordered set $P$ and an element $p \in P$, the cramming ordinal of $p$ is the least ordinal $\alpha$ such that there is no order monomorphism $f : \alpha \rightarrow P$ satisfying $f(0)=p$.

This begs the following question.

What is the cramming ordinal of the element $0 \in \mathbb{R}$?

(Actually, I presume all elements of $\mathbb{R}$ have the same cramming ordinal in $\mathbb{R}$, but lets just consider $0$ for concreteness).

Now observe that $\omega$ is a lower bound for the cramming ordinal of $0$, because $f$ is witnessed by the identity function.

Observe also that given a monomorphism $f : \alpha \rightarrow \mathbb{R}$ satisfying $f(0)=0$, it holds that $\tan^{-1} \circ f$ is also a monomorphism. However, the range of $\tan^{-1} \circ f$ is bounded above in $\mathbb{R}$. So we can copy the idea of $\tan^{-1} \circ f$ repeatedly, in fact $\omega$ many times. So if $\alpha$ is a lower bound for the cramming ordinal of $0$, then $\alpha \omega$ is a lower bound, too.

Thus since $\omega$ is a lower bound for the cramming ordinal of $0$, so too are $\omega^2$, $\omega^3$ etc.

My question is, what is the cramming ordinal of $0 \in \mathbb{R}$?

share|improve this question
    
See also JDH's answer here and this question. –  Martin Sleziak Apr 2 '13 at 12:30
add comment

2 Answers 2

up vote 9 down vote accepted

First of all, the technical term is "cofinality of the cone generated by $p$", not "cramming ordinal of $p$".

Now, for the case of $\Bbb R$, note that the order is homogeneous, so the actual point we choose to "cram" above is irrelevant, but this also means that $0$ is as good as any.

More to the point, since the rationals are dense in $\Bbb R_+$, we can embed any countable into $\Bbb R_+$. This is proved by transfinite induction.

  • Clearly it's true for $0$;
  • If you can embed $\alpha$ using $f$, then without loss of generality you can embed it into $[0,1)$, then extend $f$ by setting $f(\alpha)=1$. This is clearly order preserving.
  • If $\beta$ is a limit ordinal and we can embed every smaller ordinal than $\beta$, write it as the union of intervals $[\alpha_i,\alpha_{i+1})$ each with order type strictly less than $\beta$ (e.g. take a strictly increasing sequence of ordinals, $\alpha_i$ with limit $\beta$).

    By the assumption we can embed every ordinal smaller than $\beta$, so we can embed the ordinal isomorphic to $[\alpha_i,\alpha_{i+1})$ into the interval $[i,i+1)$ in the rationals. Clearly we have embedded $\beta$ into the rationals by gluing the maps. $\square$

Furthermore if we do embed $\omega_1$, then we can cut $\Bbb R$ into $\aleph_1$ disjoint open intervals, this is impossible because there is an injection from every family of disjoint open intervals into $\Bbb Q$.

Therefore the cramming ordinal is $\omega_1$.

share|improve this answer
1  
Why is it that we can embed any countable ordinal into $\mathbb R$ in a way that preserves order? –  Andrew Salmon Mar 31 '13 at 22:13
1  
It's not immediately obvious that any countable limit ordinal is a $\omega$-indexed sum of strictly smaller ordinals. –  Hurkyl Mar 31 '13 at 22:24
2  
@Hurkyl: Take $f$ a bijection of $\omega$ and $\alpha$, some countable limit ordinal. This bijection cannot have an infinite decreasing sequence, so for every $n$ there is some $k>n$ such that $f(n)<f(k)$. Since $f$ is a bijection this sequence must be cofinal in $\alpha$. –  Asaf Karagila Mar 31 '13 at 22:38
1  
@Asaf: Ah yes, it's much clearer when you come at it from that angle. –  Hurkyl Mar 31 '13 at 22:42
2  
But I like cramming ordinal of $p$: it has real style! –  Brian M. Scott Apr 1 '13 at 1:35
show 10 more comments

Here's a more elementary argument that any countable ordinal can be embedded into $\mathbb Q$. The trick is to show something stronger: any countable total order can embedded into $\mathbb Q$:

Let $(\mathbb N,{\sqsubset})$ be an arbitrary countable total order. (We can assume wlog that the underlying set is $\mathbb N$ -- that's what it means to be countable!) We defined an order monomorphism $f: (\mathbb N,{\sqsubset})\to(\mathbb Q,{<})$ by ordinary long induction on $\mathbb N$:

  • Arbitrarily set $f(0)=42$.

  • For $n>0$ suppose we have already decided what $f(m)$ is for $m<n$.

    If $n\sqsubset m$ for all $m<n$, then let $f(m)=\min_{m<n}f(m)-1$.

    If $m\sqsubset n$ for all $m<n$, then let $f(m)=\max_{m<n}f(m)+1$.

    Otherwise let $f(m)=\dfrac{\max_{m<n, m\,\sqsubset\, n}f(m) + \min_{m<n, n\,\sqsubset\, m}f(m)}{2}$

In fact essentially this construction shows that any countable total order can be embedded into any dense subset of $\mathbb R$.

Once we've mapped something into $\mathbb R$, we can remap it into $\mathbb R_+$, by composing with, say, $x\mapsto e^x$.

share|improve this answer
    
Thanks. Does that argument allow any countable total order to be embedded into any dense total order? –  goblin Apr 4 '13 at 9:18
1  
@user18921: Yes. (If the dense total order has a maximum or minimum, start by picking two points in it and restrict your attention to the open interval between them). In this general case the argument requires the Axiom of Choice (or Dependent Choice). –  Henning Makholm Apr 4 '13 at 11:44
add comment

Your Answer

 
discard

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.