Here is how Donald Newman would prove it.

Let be a sequence in a totally ordered set . Define to bedominantif 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.