|
|
|
|
well quasi ordering
|
(Definition)
|
|
|
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 \NN$ , $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:
The equivalence of WQO to the second and the fourth conditions is proved by the infinite version of Ramsey's theorem.
|
"well quasi ordering" is owned by CWoo. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
See Also: pre-order, pre-order
| Other names: |
well quasi order, wqo |
| Keywords: |
Order, Orderings, QuasiOrdering, PartialOrderings, WellQuasiOrdering |
|
|
Cross-references: Ramsey's theorem, equivalence, increasing, contains, induced, equivalence classes, equivalence relation, linear extension, chains, strictly decreasing, binary relation, definitions, equivalent, proposition, well-ordering, antichain, sequence, infinite, quasi-order
This is version 10 of well quasi ordering, born on 2003-08-26, modified 2008-03-08.
Object id is 4653, canonical name is WellQuasiOrdering.
Accessed 5104 times total.
Classification:
| AMS MSC: | 06A99 (Order, lattices, ordered algebraic structures :: Ordered sets :: Miscellaneous) | | | 06A07 (Order, lattices, ordered algebraic structures :: Ordered sets :: Combinatorics of partially ordered sets) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
