Erdős–Szekeres の定理：相異なる \(n^2+1\) 個の数の列は、長さ \(n+1\) の増加部分列か減少部分列をもつ。

1 鳩の巣原理

鳩の巣原理：\(X\) から \(Y\) への単射があれば \(X\) の個数は \(Y\) の個数以下。
PH … \(X \stackrel{\#}= m \in \mathbb{M} , Y \stackrel{\#}= k \in \mathbb{M} , F \subset X \times Y , \forall x \in X . \exists! y \, \langle x , y \rangle \in F , \forall x , x' , y \, ( \langle x , y \rangle \in F , \langle x' , y \rangle \in F \Longrightarrow x = x' ) \Longrightarrow m \le k\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，Ax𝕄 ，ax_s ，+𝕄

2 主定理

相異なる \(n^2+1\) 個の数の列 \(a(0), \dots, a(n^2)\) は、長さ \(n+1\) の増加部分列か減少部分列をもつ（Erdős–Szekeres）。部分列は添字の集合 \(S\) で表し、値は自然数とします。
証明：どちらも無いとします。位置 \(i\) で終わる増加部分列の長さの集合を \(P(i) \subset \{1, \dots, n\}\)、減少部分列の長さの集合を \(Q(i)\) とし、\(i\) に個数の組 \((\#P(i), \#Q(i))\) を対応させます。\(i < j\) で \(a(i) < a(j)\) なら、\(i\) で終わる増加部分列は \(j\) まで伸ばせるので \(\#P(i) < \#P(j)\)（E6）。\(a(i) > a(j)\) なら \(\#Q(i) < \#Q(j)\)。よってこの対応は \(n^2+1\) 個の位置から \(n^2\) 個の組への単射で、鳩の巣原理 PH に反します。
本体は \(n^2\) を積 \(n \cdot n\) で書いた形（Ev⋅）で示し、↑ で書いた形はその言い換え。
\(n \in \mathbb{M} , \forall i \in 0 \mathinner{\ldotp\ldotp} ( n ^ 2 ) . {a} ( i ) \in \mathbb{M} , \forall i \in 0 \mathinner{\ldotp\ldotp} ( n ^ 2 ) . \forall j \in 0 \mathinner{\ldotp\ldotp} ( n ^ 2 ) . ( {a} ( i ) = {a} ( j ) \Longrightarrow i = j ) \Longrightarrow \exists S \, ( S \subset 0 \mathinner{\ldotp\ldotp} ( n ^ 2 ) , S \stackrel{\#}= n + 1 , ( \forall x \in S . \forall y \in S . ( x < y \Longrightarrow {a} ( x ) < {a} ( y ) ) \mathbin{\rm o\!r} \forall x \in S . \forall y \in S . ( x < y \Longrightarrow {a} ( y ) < {a} ( x ) ) ) )\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，Ax𝕄 ，ax_s ，+𝕄 ，⋅𝕄 ，↑𝕄