Printable View
Here's the problem I have to prove:
Every sequence in a totally ordered set has a monotonic subsequence.
We have to use induction to prove this statement, but I am not too good and writing induction proofs as I don't know how to start them and what to put in my induction hypothesis. Any suggestions would be appreciated! Thanks
Here is how Donald Newman would prove it.Quote:
Originally Posted by beachbum87
Let $\displaystyle \{ a_n\}$ be a sequence in a totally ordered set $\displaystyle A$. Define $\displaystyle a_m$ to be dominant if $\displaystyle a_m > a_k$ for all $\displaystyle k>m$.
Case 1: There are infinitely many dominant terms. Then choose $\displaystyle a_{n_1},a_{n_2}, ... $ to be dominant terms, in increasing substrict order as you go along the sequence. Then $\displaystyle a_{n_1} > a_{n_2} > ... $ is a monotone subsequence.
Case 2: There are finitely many dominant terms. Let $\displaystyle N$ be larger of all indexes of the dominant terms, i.e. if $\displaystyle n\geq N$ then $\displaystyle a_n$ is not dominant. Pick $\displaystyle a_N$, this is not dominant so there is $\displaystyle n_2$ so that $\displaystyle a_{n_2}\geq a_N$. But $\displaystyle a_{n_2}$ is not dominant so pick $\displaystyle n_3$ so that $\displaystyle a_{n_3}\geq a_{n_2}$. And so on. Thus, $\displaystyle \left< a_N, a_{n_2}, a_{n_3}, ... \right>$ is a monotone subsequence.
