Let be a sequence in a totally ordered set . Define to be dominant if for all .
Case 1: There are infinitely many dominant terms. Then choose to be dominant terms, in increasing substrict order as you go along the sequence. Then is a monotone subsequence.
Case 2: There are finitely many dominant terms. Let be larger of all indexes of the dominant terms, i.e. if then is not dominant. Pick , this is not dominant so there is so that . But is not dominant so pick so that . And so on. Thus, is a monotone subsequence.