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

In all "constructive" fixed-point theorems for functions on ordered sets that I am aware of, where the fixed point is obtained as the limit of a stationary increasing transfinite sequence, it is always an ordinal of cardinality greater than the cardinality of the set that is used in the proof. While this is of course sufficient, it seems like a real overkill. What you really need is the least ordinal that cannot be orderly embedded in the ordered set. Motivated by the finite case, I would be inclined to call that ordinal the height of the ordered set, even though the latter need not be well founded. Is there any standard terminology or work on this?

share|improve this question
add comment

1 Answer

EDIT SUMMARY: The first version of the answer only talked about linearly ordered sets; prompted by Ricky Demer's inquiry, I modified item 5, and added items 6 and 7.

The second paragraph of (6) is the newest addition.

I have never seen the concept introduced in the question studied systematically, but it is a very natural concept, and one can say a few sensible things about it.

For a poset $P$. let $o(P)$ be the least ordinal that cannot be order-isomorphically embedded into a partially ordered set $P$ (indeed $P$ can be even a quasi-order; i.e., ordered by a relation required only to be reflexive and transitive).

1. (Warm-up). For every ordinal $\alpha$, $o(\alpha) = \alpha + 1$.

2. $o(\Bbb{Q}) = \omega_1$ (the least uncountable ordinal), thanks to a theorem of Cantor, which states that every countable linear order can be embedded inside $\Bbb{Q}$.

3. $o(\Bbb{R}) = \omega_1$. This follows from (2) and the fact that any collection of pairwise disjoint open intervals of the real line is at most countable (by the density of rationals in the real line).

4. For every natural number $n$, let $\Bbb{R}^n$ be the n-fold lexicographically ordered Cartesian power of the real line. Then $o(\Bbb{R}^n)=\omega_1$ for each $n$. This follows from (3) using induction on $n$. A theorem of Harrington and Shelah vastly generalizes this this to : for every analytic linear order $L$, $o(L)\leq\omega_1$.

5. Let $L$ be a linear order of cardinality greater than $2^{\aleph_0}$, then $o(L) > \omega_{1} $, or $o(L^{\*}) > \omega_{1}$, where $L^{\*}$ is the reverse of $L$; by the Erdős–Rado theorem. More generally, if $P$ is a poset of cardinality greater than $2^{\kappa}$ for some infinite cardinal $\kappa$, then either $o(P) > \kappa^{+}$, or $o(P^{\*}) > \kappa^{+}$, or $P$ contains a subset of cardinality $\kappa^+$ of pairwise incomparable elements.

6. Let $A\subset_* B$ be defined as "$A$\$B$ is finite". Then $o(\cal{P}(\omega), \subset_*) > \omega_1$, by a diagonal argument plus transfinite induction (a more sophisticated version of this argument produces a "Hausdorff gap").

By a classical theorem of Parovicenko, every Boolean algebra of cardinality at most $\aleph_1$ can be embedded into $(\cal{P}(\omega), \subset_\*)$. This implies that indeed $o(\cal{P}(\omega), \subset_*) \geq \omega_2$. In the presence of the continuum hypothesis $o(\cal{P}(\omega), \subset_*) = \omega_2$.

7. A similar result to (6) is true for the set of functions from $\omega$ to itself, ordered by eventual dominance. Hardy (the number theorist) was among the people who noticed that there is a sequence of functions from $\omega$ to itself of order-type $\omega_1$; and he was quite impressed by this discovery.

This list is obviously woefully incomplete, but should give a rough idea that many results of (combinatorial) set theory can be couched in terms of $o(P)$.

share|improve this answer
Why restrict to a linear order? (for 1-4) –  Ricky Demer Jul 26 '11 at 2:29
Thanks for the comments Ricky; I modified my answer a bit to make it more general. –  Ali Enayat Jul 26 '11 at 5:10
$(\omega_1)^2 \leq o(2^{\omega},\subseteq_*)$, by partitioning $\omega$ into a countable well-ordered number of infinite pieces and embedding that many copies of $\omega_1$ in a chain. If CH, then $o(2^{\omega},\subseteq_*) \leq \omega_2$ since $|2^{\omega}| = \omega_1 < \omega_2$. –  Ricky Demer Jul 26 '11 at 7:29
In item 5, there should be a third option, namely that $o$ of the reversed order is big. For example, $P$ could be a long anti-well-order. (Apologies for the awkward formulation, caused by a French keyboard.) –  Andreas Blass Jul 26 '11 at 14:26
@Andreas: you are right, thanks, I will fix it. –  Ali Enayat Jul 26 '11 at 15:22
show 3 more comments

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.