2
$\begingroup$

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.

  • 0
    What is the multiset order?2012-07-06
  • 0
    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}$.2012-07-06
  • 0
    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?2012-07-06
  • 0
    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.2012-07-06
  • 0
    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.2012-07-06
  • 0
    Yes, I know wqo's etc. And graphs (and degenerately, trees) ordered by embedding may be the only other answer to my question. But I am looking for an extension to sets similar to tuples and multisets. Graphs and trees can be built recursively from tuples or multisets, so they are not as "fundamental". Are there any other "fundamental" well-foundedness preserving extensions to sets besides tuples and multisets?2012-07-06

1 Answers 1