You are here
Homewell quasi ordering
Primary tabs
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 $i<j\in{\mathbf{N}}$, $a_{i}\not\precsim 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 $\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.
Mathematics Subject Classification
06A99 no label found06A07 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections