Question

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?

Answer 1

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)$.