well quasi ordering

Let $Q$ be a set and $\precsim$ a quasi-order on $Q$. Aninfinite sequence in $Q$ is referred to as bad if forall , $a_i\precsim ̸a_j$ holds; otherwise it is calledgood. Note that an antichain is obviously a bad sequence.

A quasi-ordering $\precsim$ on $Q$ is a well-quasi-ordering (wqo) if for every infinite sequence is good. Every well-ordering is a well-quasi-ordering.

The following proposition gives equivalent definitions forwell-quasi-ordering:

Proposition 1.

Given a set $Q$ and a binary relation $\mathrm{\precsim }$ over $Q$, thefollowing conditions are equivalent:

• $(Q,\precsim )$ is a well-quasi-ordering;

• $(Q,\precsim )$ has no infinite ($\omega$-) strictly decreasing chainsand no infinite antichains.

• Every linear extension of $Q{/}_{\approx }$ is a well-order, where $\approx$ is the equivalence relation and $Q{/}_{\approx }$ is the set of equivalence classes induced by $\approx$.

• Any infinite ($\omega$-) $Q$-sequence contains anincreasing chain.

The equivalence of WQO to the second and the fourth conditions is proved by the infinite version of Ramsey’s theorem.