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.
Read more about this topic: Well-quasi-ordering
Famous quotes containing the words infinite and/or increasing:
““. . . Me miserable! which way shall I fly
Infinite wrath and infinite despair?
Which way I fly is Hell; myself am Hell;
And, in the lowest deep, a lower deep
Still threat’ning to devour me opens wide,
To which the Hell I suffer seems a Heaven.”
—John Milton (1608–1674)
“Push, labor, shove,—these words of great power in a city like this. Two years must find me with a living and increasing business, or I quit the city and probably the profession.”
—Rutherford Birchard Hayes (1822–1893)