
ErdosSzekeres Theorem
Hello to all MHF members...
I want to share with you a nice proof of the theorem:
ErdősSzekeres Theorem  from Wolfram MathWorld
I will prove this theorem for using the following theorem:
(*) If are finite sets, then:
exist an injective function from to .
Proof of the main theorem:
Let be elements of the sequence.
Suppose that this sequence not contains a monotonic increasing subsequence of terms or a monotonic decreasing subsequence of terms.
By assumption, every monotonic increasing subsequence and every monotonic decreasing subsequence are at length of , at most.
Let be , now we look at the function:
, which is given by: , when is the length of the longest monotonic increasing subsequence which starts with and is the length of the longest monotonic decreasing subsequence which starts with .
is injective function.
Proof:
We need to show that if , then .
Every elements are diffident, therefor if , then , hence or .
If , we look at monotonic increasing subsequence which starts with her length is . Now we add to the beginning of this subsequence and we get monotonic increasing subsequence which starts with her length is , it is clear that . If we look at monotonic decreasing subsequence which starts with her length is , we add to the beginning of this subsequence, and we will get .
Anyway, or , hence .
Therfor is injective.
From the theorem above:
or , a contradiction, which is prove the theorem.
(*) Actually it is the "pigeonhole" principle.