# Are lexicographic and multiset the only extensions of sets that preserve well-foundedness?

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.

-
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

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