well quasi ordering


Let Q be a set and a quasi-order on Q. An infiniteMathworldPlanetmath sequencePlanetmathPlanetmath in Q is referred to as bad if for all i<j𝐍, ai≾̸aj holds; otherwise it is called good. Note that an antichainMathworldPlanetmath is obviously a bad sequence.

A quasi-ordering 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 propositionPlanetmathPlanetmath gives equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath definitions for well-quasi-ordering:

Proposition 1.

Given a set Q and a binary relationMathworldPlanetmath over Q, the following conditions are equivalent:

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

  • (Q,) has no infinite (ω-) strictly decreasing chains and no infinite antichains.

  • Every linear extensionMathworldPlanetmath of Q/ is a well-order, where is the equivalence relation and Q/ is the set of equivalence classesMathworldPlanetmath induced by .

  • Any infinite (ω-) 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