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

2

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

  • 0
    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?2012-07-06