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<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 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
Canonical name	WellQuasiOrdering
Date of creation	2013-03-22 13:54:15
Last modified on	2013-03-22 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