well quasi ordering
Let $Q$ be a set and $\precsim $ a quasiorder on $Q$. An infinite^{} sequence^{} in $Q$ is referred to as bad if for all $$, ${a}_{i}\precsim \u0338{a}_{j}$ holds; otherwise it is called good. Note that an antichain^{} is obviously a bad sequence.
A quasiordering $\precsim $ on $Q$ is a wellquasiordering (wqo) if for every infinite sequence is good. Every wellordering is a wellquasiordering.
The following proposition^{} gives equivalent^{} definitions for wellquasiordering:
Proposition 1.
Given a set $Q$ and a binary relation^{} $\mathrm{\precsim}$ over $Q$, the following conditions are equivalent:

•
$(Q,\precsim )$ is a wellquasiordering;

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

•
Every linear extension^{} of $Q{/}_{\approx}$ is a wellorder, 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 

Canonical name  WellQuasiOrdering 
Date of creation  20130322 13:54:15 
Last modified on  20130322 13:54:15 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  13 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 06A99 
Classification  msc 06A07 
Synonym  well quasi order 
Synonym  wqo 
Related topic  quasiOrder 
Related topic  QuasiOrder 