> [!NOTE] Theorem (Infinite sequence contains monotonic subsequence) > Any [[Real sequences|sequence]] $(a_{n})_{n \geq 0}$ of real numbers contains a [[Monotonic Sequence of Real Numbers|monotonic]] [[Real Subsequence|subsequence]]. >*Proof*. We'll call an element $a_{j}$ 'high' if $a_{j}\geq a_{n}\quad \forall n\geq j$Suppose that there are an infinite number of high elements, with indices $(n_{j})_{j=1}^{\infty}$. Then, by definition, $a_{n_{j+1}}\leq a_{n_{j}} \quad \text{for very j,}$so $(a_{n_{j}})_{j=1}^{\infty}$ is a decreasing subsequence. > >If there are only a finite number of high elements, them there is an index $N$ such that $a_{j}$ is not high for every $j\geq N$. > >Take $n_{1} = N$. >Since $a_{n_{1}}$ is not high, there exists $n_{2}>n_{1}$ such that $a_{n_{2}}>a_{n_{1}}$. >Since $a_{n_{2}}$ is not high, there exists $n_{3}>n_{2}$ such that $a_{n_{3}}>a_{n_{2}}$. >Continuing this way, we find indices $n_{j+1}>n_{j}$ such that $a_{n_{j+1}}>a_{n_{j}}$. >So now we have a increasing subsequence $(a_{n_{j}})_{j=1}^{\infty}$. > [!NOTE] Theorem (Erdös-Szekeres) > Every finite sequence $a_{1},\dots,a_{(r-1)(s-1)+1}$ of distinct real numbers contains either an increasing [[Real Subsequence|subsequence]] of length $r$ or a decreasing subsequence of length $s$. >See [[Erdös-Szekeres Theorem|proof]]. # Applications - [[Bolzano-Weierstrass Theorem (Sequential Compactness of The Reals)]]