# Is every well-founded simplification order a well-partial order?

I'm contemplating the proof of Kruskal's Tree Theorem, as presented in the book "Term Rewriting and All That." They use it to prove that every simplification order is well-founded: first by showing that the homeomorphic embedding is a wpo, and then by showing that every simplification order contains the homeomorphic embedding.

It seems to me that the only properties they use of the homeomorphic embedding in the proof are that it's well-founded, and that each term is > its subterms -- exactly the property that defines a simplification order. Does the same proof work if I instead use an arbitrary simplification order*? Does this mean every simplification order is a well-partial order*?

*One caveat: restricting terms to a finite set of variables, because it's trivial to construct a counterexample with an infinite set of variables.

• In your second paragraph, you refer to "the proof" and "the same proof". Are you referring to the proof of Kruskal's theorem?
– cody
Aug 24, 2016 at 22:29
• Yes, I am referring to the proof of Kruskal's Theorem Aug 28, 2016 at 5:18

If $R$ is a well-quasi order, and $S$ is a partial order, and $R\subseteq S$, then $S$ is a well-partial order.