# well quasi ordering

Let $Q$ be a set and $\precsim$ a quasi-order on $Q$. An infinite sequence in $Q$ is referred to as bad if for all $i, $a_{i}\not\precsim a_{j}$ holds; otherwise it is called good. 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 for well-quasi-ordering:

###### Proposition 1.

Given a set $Q$ and a binary relation $\precsim$ over $Q$, the following conditions are equivalent:

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

• $(Q,\precsim)$ has no infinite ($\omega$-) strictly decreasing chains and 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 an increasing chain.

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

Title well quasi ordering WellQuasiOrdering 2013-03-22 13:54:15 2013-03-22 13:54:15 CWoo (3771) CWoo (3771) 13 CWoo (3771) Definition msc 06A99 msc 06A07 well quasi order wqo quasiOrder QuasiOrder