Well-quasi-ordering

In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements x 0 {displaystyle x_{0}} , x 1 {displaystyle x_{1}} , x 2 {displaystyle x_{2}} , … from X {displaystyle X} contains an increasing pair x i ≤ x j {displaystyle x_{i}leq x_{j}} with i < j {displaystyle i<j} . In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements x 0 {displaystyle x_{0}} , x 1 {displaystyle x_{1}} , x 2 {displaystyle x_{2}} , … from X {displaystyle X} contains an increasing pair x i ≤ x j {displaystyle x_{i}leq x_{j}} with i < j {displaystyle i<j} . Well-founded induction can be used on any set with a well-founded relation, thus one is interested in when a quasi-order is well-founded. However the class of well-founded quasiorders is not closed under certain operations—that is, when a quasi-order is used to obtain a new quasi-order on a set of structures derived from our original set, this quasiorder is found to be not well-founded. By placing stronger restrictions on the original well-founded quasiordering one can hope to ensure that our derived quasiorderings are still well-founded. An example of this is the power set operation. Given a quasiordering ≤ {displaystyle leq } for a set X {displaystyle X} one can define a quasiorder ≤ + {displaystyle leq ^{+}} on X {displaystyle X} 's power set P ( X ) {displaystyle P(X)} by setting A ≤ + B {displaystyle Aleq ^{+}B} if and only if for each element of A {displaystyle A} one can find some element of B {displaystyle B} that is larger than it under ≤ {displaystyle leq } . One can show that this quasiordering on P ( X ) {displaystyle P(X)} needn't be well-founded, but if one takes the original quasi-ordering to be a well-quasi-ordering, then it is. A well-quasi-ordering on a set X {displaystyle X} is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements x 0 {displaystyle x_{0}} , x 1 {displaystyle x_{1}} , x 2 {displaystyle x_{2}} , … from X {displaystyle X} contains an increasing pair x i {displaystyle x_{i}} ≤ x j {displaystyle x_{j}} with i {displaystyle i} < j {displaystyle j} . The set X {displaystyle X} is said to be well-quasi-ordered, or shortly wqo. A well partial order, or a wpo, is a wqo that is a proper ordering relation, i.e., it is antisymmetric. Among other ways of defining wqo's, one is to say that they are quasi-orderings which do not contain infinite strictly decreasing sequences (of the form x 0 {displaystyle x_{0}} > x 1 {displaystyle x_{1}} > x 2 {displaystyle x_{2}} >…)nor infinite sequences of pairwise incomparable elements. Hence a quasi-order (X,≤) is wqo if and only if (X,<) is well-founded and has no infinite antichains. In practice, the wqo's one manipulates are quite often not orderings (see examples above), and the theory is technically smoother if we do not require antisymmetry, so it is built with wqo's as the basic notion. On the other hand, according to Milner 1985, no real gain in generality is obtained by considering quasi-orders rather than partial orders... it is simply more convenient to do so. Observe that a wpo is a wqo, and that a wqo gives rise to a wpo betweenequivalence classes induced by the kernel of the wqo. For example, if we order Z {displaystyle mathbb {Z} } by divisibility, we end up with n ≡ m {displaystyle nequiv m} if and only if n = ± m {displaystyle n=pm m} , so that ( Z , ∣ ) ≈ ( N , ∣ ) {displaystyle (mathbb {Z} ,mid );;approx ;;(mathbb {N} ,mid )} . If ( X {displaystyle X} , ≤) is wqo then every infinite sequence x 0 {displaystyle x_{0}} , x 1 {displaystyle x_{1}} , x 2 {displaystyle x_{2}} , … contains an infinite increasing subsequence x n 0 {displaystyle x_{n0}} ≤ x n 1 {displaystyle x_{n1}} ≤ x n 2 {displaystyle x_{n2}} ≤…(with n 0 {displaystyle {n0}} < n 1 {displaystyle {n1}} < n 2 {displaystyle {n2}} <…). Such a subsequence is sometimes called perfect.This can be proved by a Ramsey argument: given some sequence ( x i ) i {displaystyle (x_{i})_{i}} , consider the set I {displaystyle I} of indexes i {displaystyle i} such that x i {displaystyle x_{i}} has no larger or equal x j {displaystyle x_{j}} to its right, i.e., with i < j {displaystyle i<j} . If I {displaystyle I} is infinite, then the I {displaystyle I} -extracted subsequence contradicts the assumption that X {displaystyle X} is wqo. So I {displaystyle I} is finite, and any x n {displaystyle x_{n}} with n {displaystyle n} larger than any index in I {displaystyle I} can be used as the starting point of an infinite increasing subsequence.