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

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

• $Q/_{\approx}$ is a well-order, where $\approx$ is the equivalence relation and $Q/_{\approx}$$\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