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:
“One who pressed forward incessantly and never rested from his labors, who grew fast and made infinite demands on life, would always find himself in a new country or wilderness, and surrounded by the raw material of life. He would be climbing over the prostrate stems of primitive forest-trees.”
—Henry David Thoreau (1817–1862)
“Without looking, then, to those extraordinary social influences which are now acting in precisely this direction, but only at what is inevitably doing around us, I think we must regard the land as a commanding and increasing power on the citizen, the sanative and Americanizing influence, which promises to disclose new virtues for ages to come.”
—Ralph Waldo Emerson (1803–1882)