Editing Well-quasi-ordering (section)

==Infinite increasing subsequences==
If <math>(X, \le)</math> is wqo then every infinite sequence <math>x_0, x_1, x_2, \ldots,</math> contains an '''infinite''' increasing subsequence <math>x_{n_0} \le x_{n_1}\le x_{n_2} \le \cdots</math> (with <math>n_0< n_1< n_2< \cdots</math>). Such a subsequence is sometimes called '''perfect'''.
This can be proved by a [[Ramsey theory|Ramsey argument]]: given some sequence <math>(x_i)_i</math>, consider the set <math>I</math> of indexes <math>i</math> such that <math>x_i</math> has no larger or equal <math>x_j</math> to its right, i.e., with <math>i<j</math>. If <math>I</math> is infinite, then the <math>I</math>-extracted subsequence contradicts the assumption that <math>X</math> is wqo. So <math>I</math> is finite, and any <math>x_n</math> with <math>n</math> larger than any index in <math>I</math> 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.