단조 부분 수열 정리 (monotone subsequence theorem)

단조 부분 수열 정리는 다음과 같습니다.

모든 수열은 단조 부분 수열을 가진다.

간단하죠?

다시 말하면

수열 $(x_n)$이 어떤 방식으로 정의되든 상관없이

단조 증가 부분 수열 $(x_{n_k})$ 혹은 단조 감소 부분 수열 $(x_{r_k})$을 가진다는 것입니다.

증명은 다음과 같습니다.

모든 수열은

자신 이후의 모든 수열 값이 자기 보다 작거나 같은 수열이

(예를들어 $x_m$이 그런 수열이라면

자연수 $m$보다 크거나 같은 모든 자연수 $n$에 대해 $x_m\geq x_n$을 만족합니다.)

유한개인 경우와 무한개인 경우로 나뉘어 집니다.

무한개인 경우는 

그런 수열 값에 해당하는 index를 순서대로 $m_1,~m_2,~m_3,~\cdots$라고 했을때

$x_{m_1}\geq x_{m_2}\geq x_{m_3}\geq \cdots$를 만족하므로 단조 감소 수열을 가지고 있습니다.

유한개인 경우는

그 유한개의 수열 값을 제외한 나머지 수열은

자신 이후에 자신보다 큰 수열 값이 존재하므로

먼저 하나의 수열 값 $x_{r_1}$을 선택하고

$r_2$는 $n>r_1$중에 $x_n\geq x_{r_1}$인 $x_n$을 선택하고

같은 방법으로 $r_3,~r_4,~\cdots$를 선택하는 방법으로

단조 증가 수열을 찾을 수 있습니다.