In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements from contains an increasing pair with Motivation 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. (Here, by abuse of terminology, a quasiorder is said to be well-founded if the corresponding strict order is a well-founded relation.) 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 for a set one can define a quasiorder on 's power set by setting if and only if for each element of one can find some element of that is larger than it with respect to . One can show that this quasiordering on needn't be well-founded, but if one takes the original quasi-ordering to be a well-quasi-ordering, then it is. Formal definition A well-quasi-ordering on a set is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements from contains an increasing pair with . The set 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 ) 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. Examples , the set of natural numbers with standard ordering, is a well partial order (in fact, a well-order). However, , the set of positive and negative integers, is not a well-quasi-order, because it is not well-founded (see Pic.1). , the set of natural numbers ordered by divisibility, is not a well-quasi-order: the prime numbers are an infinite antichain (see Pic.2). , the set of vectors of natural numbers (where is finite) with component-wise ordering, is a well partial order (Dickson's lemma; see