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'm learning about set theory and partial orders, well orders, total orders, etc. I'm curious to know of any good decomposition theorems that apply to all (or very general types of) total orders.

As examples of other decompositions, I'm thinking about Cantor normal form for ordinal numbers, or things like the singular value decomposition of matrices. These are results that provide a perspective of a general object as being built from more structured pieces in a way that reveals useful properties of the original object.

share|improve this question

2 Answers 2

up vote 12 down vote accepted

This question has been studied extensively, starting with a series of key results due to Hausdorff. Luckily, his relevant papers have been recently published (in English, with commentaries) by the AMS and the London Mathematical Society, "Hausdorff on Ordered Sets", J.M. Plotkin, ed., and I strongly recommend that you at least take a look at this book. There is also the classic "Linear Orderings" by Rosenstein.

One of Hausdorff's main results is as follows: A linear order is scattered iff it doesn't contain a copy of ${\mathbb Q}$.

Theorem (Hausdorff). A linear order is scattered iff its order type is in some $S_\alpha$ ($\alpha$ an ordinal), where:

  1. $S_0=\{0,1\}$.
  2. For $\alpha>0$, $S_\alpha$ is the smallest class obtained as follows: If $\gamma$ is an ordinal, $I$ is $\gamma$, $\gamma^*$, or $\gamma^*+\gamma$, and for each $i\in I$ the linear order $L_i$ is in $\bigcup_{\beta<\alpha}S_\beta$, then $\sum_{i\in I}L_i\in S_\alpha$.

Here, $\gamma^*$ is the "reverse" of $\gamma$ (for example, $\omega^*$ is the order type of the negative integers), and the sum is obtained by taking the disjoint union of the $L_i$ and setting, for $a\in L_j$ and $b\in L_k$ that $a<b$ iff $j=k$ and $a<b$ in $L_j$, or else $j<k$ in $I$.

This is a really useful result, and I think it is very much of the kind you are hoping for. Its usefulness comes from the fact that it provides us with a "ranking" that allows us to prove theorems about orders (or scattered orders) by transfinite induction. To understand why it is in the spirit of what you are looking for, note that there is a natural way of assigning to a scattered order a "tree" that codes its construction as it appears in $\bigcup_\alpha S_\alpha$. (This "tree" is the analogue of the Cantor normal form you mention in your examples.)

Next in complexity past the scattered orders are the $\sigma$-scattered ones, those that are a countable union of scattered orders (${\mathbb Q}$ being a not terribly interesting example). The main results here are due to Laver. In particular, Laver obtained a nice decomposition theorem for countable scattered orders, as a consequence of what is one of the fundamental results in the area:

A quasi-ordering $\le$ is a reflexive and transitive binary relation on a set $A$. Write $a<b$ when $a\le b$ but not vice versa. $(A,<)$ is a wqo, well-quasi-ordering iff $A$ has no infinite descending chains and no infinite pairwise incomparable sets. Laver proved Fraïssé's conjecture, that the countable order types form a wqo under embeddability. In fact:

Theorem (Laver). If $(L_i\mid i\in\omega)$ is a sequence of $\sigma$-scattered linear orders, then there are $i<j$ such that $L_i$ embeds in $L_j$.

To see how to obtain decomposition results from this, let me mention a corollary: Any countable scattered linear order is a finite sum of ha-orders, "hereditarily additively indecomposable" linear orders. Here, the class of ha-orders is the smallest class that contains $1$, and contains $\sum_{i\in\omega}L_i$ and $\sum_{i\in\omega^*}L_i$ whenever it contains each $L_i$ and each $L_i$ is embeddable in infinitely many $L_j$.

There are also interesting results about dense linear orders. Up to isomorphism, the only countable one is ${\mathbb Q}$. In the uncountable realm, things are much more interesting. There are negative results saying that in some cases there is no nice decomposition, and positive results in some specific settings. One of the reasons why this is interesting is that it leads to independence results in set theory. The following papers by Justin Moore (available from Justin's page) are highly relevant:

  • A five element basis for the uncountable linear orders. Annals of Mathematics (2) 163 (2006), n 2, pp. 669-688.
  • Minimality of non sigma-scattered orders. Fundamenta Mathematicae. 205 (2009), n 1, pp. 29-44.
  • (with Tetsuya Ishiu): $\omega_1$ and $\omega_1^*$ may be the only minimal uncountable order types. Michigan Math. Journal 55 (2007), n 2, pp. 437-457.

As an example of an independence result related to Justin's papers above and the possibility or not of a useful decomposition theorem for non-scattered orders: It is consistent that any two dense subsets of ${\mathbb R}$ of size $\aleph_1$ are isomorphic. This is actually a consequence of PFA, the Proper forcing axiom. On the other hand, Sierpiński showed that if CH holds, then there are $2^{\aleph_1}$ (the maximum possible) pairwise incomparable such dense sets.

This led to the natural question of whether, short of a full classification or decomposition, one can at least identify a "basis" for the uncountable linear orders, i.e., a class $S$ such that any uncountable linear order contains a copy of a member of $S$. Shelah conjectured that a finite basis was possible, and in fact it should follow from PFA that there is a basis of size 5. Justin proved this conjecture. It is not known if it is consistent to have a finite basis of size other than 5.

Instead of a nice basis, one can ask about "minimal" orders. An uncountable linear order $A$ is minimal iff any uncountable subset of $A$ contains a copy of $A$. Justin proved that it is consistent that the only $A$ with this property are $\omega_1$ and its reverse.

(There are also weaker versions of Sierpiński's results for larger cardinalities. Some of these results depend on additional assumptions, such as instances of GCH.)

share|improve this answer
Thanks for the detailed answer! –  Tyler May 13 '11 at 22:11
@Tyler: Hope you find it useful; it is a very interesting topic. –  Andres Caicedo May 13 '11 at 22:51

Here are a few general facts that may fit with what you are seeking.

  • Every partial order $\langle\mathbb{P},\leq\rangle$ is isomorphic to a collection of sets under the $\subseteq$ relation. To see this, associate any element $p\in\mathbb{P}$ the lower cone $A_p=\{q\in\mathbb{P}\mid q\leq p\}$.

  • Every separative partial order is order isomorphic to a dense subset of a complete Boolean algebra. Just take the Boolean algebra consisting of the regular open subsets of the partial order, and map every element to the regular open set arising from the lower cone. This idea is used in forcing, as a way of seeing the equivalence between poset-based forcing and Boolean algebra based forcing.

  • Every partial order relation can be extended to a linear order. Indeed, every partial order relation is equal to the intersection of the linear orders that extend it.

  • Every partially ordered set is a union of its maximal chains.

  • Every linear order has a largest well-ordered initial segment, called its well-founded part.

  • Every well-founded relation admits an ordinal ranking function, an assignment of nodes to ordinals, such that if $p$ is related to $q$, then the ordinal label of $p$ is lower than the ordinal label of $q$.

share|improve this answer

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.