if we order by divisibility, we end up with if and only if , so that . Infinite increasing subsequences If is wqo then every infinite sequence contains an infinite increasing subsequence (with ). Such a subsequence is sometimes called perfect. This can be proved by a Ramsey argument: given some sequence , consider the set of indexes such that has no larger or equal to its right, i.e., with . If is infinite, then the -extracted subsequence contradicts the assumption that is wqo. So is finite, and any with larger than any index in can be used as the starting point of an infinite increasing subsequence. The existence of such infinite increasing subsequences is sometimes taken as a definition for well-quasi-ordering, leading to an equivalent notion. Properties of wqos Given a quasiordering the quasiordering defined by is well-founded if and only if is a wqo. A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by ) has no infinite descending sequences or antichains. (This can be proved using a Ramsey argument as above.) Given a well-quasi-ordering , any sequence of upward-closed subsets eventually stabilises (meaning there exists such that ; a subset is called upward-closed if ): assuming the contrary , a contradiction is reached by extracting an infinite non-ascending subsequence. Given a well-quasi-ordering , any subset of has a finite number of minimal elements with respect to , for otherwise the minimal elements of would constitute an infinite antichain. See also Notes Here x < y means: and References Binary relations Order theory Wellfoundedness