If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?
Here's a nice property of WQOs:


  If $R$ is a WQO on terms, and $S$ is another transitive relation such that
  $$ R\ \subseteq\ S$$
  Then $S$ is a WQO


Proof: Let $t_1,\ldots, t_n,\ldots$ be an infinite sequence of terms. Because $R$ is a WQO, there are $i, j$ with $i&lt;j$ such that $t_i\ R\ t_j$. But this implies $t_i\ S\ t_j$, so $S$ is a WQO as well.

This (somewhat counter-intuitive) result means you can always make your relation more permissive while preserving the WQO property.