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.

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

It is well known that for a given set $S$ with well-founded order relation $R$, the lexicographic order that extends $R$ on tuples of $S$ is also well-founded.

Also, the multiset order on the multiset extension of $S$ is also well-founded.

Are there any other extensions to sets besides the lexicographic extension and the multiset extension that have a natural ordering that preserve well-foundedness?

I seem to remember reading that lexicographic and multiset extensions are the only extensions that preserve well-foundedness, but I cannot find the reference.

I am only asking about well-foundedness, i.e., not assuming the orderings are necessarily total.

share|cite|improve this question
What is the multiset order? – azarel Jul 6 '12 at 15:15
Let $\mathcal{M}(S)$ denote the set of all finite multisets over $S$. The multiset order $>_{mul}$ on $\mathcal{M}(S)$ is as follows: $A >_{mul} B$ iff there exist $X,Y \in \mathcal{M}(S)$ such that $\emptyset \neq X \subseteq A$ and $B = (A - X) \cup Y$ and $\forall y \in Y. \exists x \in X. x > y$. For example, ${5, 3, 1, 1} >_{mul} {4, 3, 3, 1}$. – Brenton Jul 6 '12 at 15:40
I thought the lexicographic order was not well-founded. Suppose we have $S=\{0,1\}$ with $1\succ 0$. Then $(1)\succ (0,1)\succ (0,0,1)\ldots$ is an infinite descending chain and thus is a nonempty subset with no minimal element. What have I misunderstood in your question? – MJD Jul 6 '12 at 15:55
The order used in dictionaries of course does not terminate (e.g., the given example of $(1) \succ (0, 1) \succ (0, 0, 1) \ldots$), but traditionally, the lexicographic order is used for tuples of the same length so that there is not a problem of non-well-foundedness. Even for tuples of different lengths, it is easy to preserve well-foundedness with i.e., the shortlex order. – Brenton Jul 6 '12 at 19:35
You may want to read about quasi-order; well-quasi-order; and more importantly better-quasi-order. The last one has strong properties of well-foundedness. – Asaf Karagila Jul 6 '12 at 20:10

There are certainly other natural constructions than lexicographic orders that preserver well orders.

For example, we can compare $(a,b)$ with $(c,d)$ first by comparing $\max(a,b)$ with $\max(c,d)$ and fall back to the lexicographic ordering iff the maxima are the same. This has the nice property that if $S$ has order type $\omega$, then so does $S\times S$.

share|cite|improve this answer
I am not assuming that the original relation $R$ is a total order on $S$, so $max(a, b)$ might not be defined. – Brenton Jul 6 '12 at 16:03
If it is a well-order, then by definition it is total. If we're speaking about partial orders, we may use least upper bounds instead of max, and declare that $(a,b)$ is incomparable with everything else unless $a$ and $b$ has a lub. Then the construction preserves the property of being a well-founded partial order. – Henning Makholm Jul 6 '12 at 16:13
Right, I edited the question to use "well-founded" everywhere, so as to not imply totality. Declaring $(a, b)$ incomparable unless $a$ and $b$ have a $lub$ is certainly allowed, but I was more looking for entirely different extensions to sets that have a natural ordering, instead of playing with the existing extensions. There are tuples and multisets. Are there are other extensions to sets that have a natural ordering that preserves well-foundedness? – Brenton Jul 6 '12 at 19:39

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.