3 主定理

相異なる \(n^2+1\) 個の数の列は、長さ \(n+1\) の増加部分列か減少部分列を持つ（Erdős–Szekeres）。ここでは値を自然数とします（使うのは値の大小だけです）。
証明：どちらも無いと仮定します。各位置 \(i\) に、\(i\) で終わる最長の増加部分列・減少部分列の長さ \(p+1\)・\(q+1\)（\(p, q \lt n\)）を対応させます（「長さ \(p+1\) のものはあり、\(p+2\) のものは無い」で決める＝LI・LD）。\(i \lt j\) で \(a(i) \lt a(j)\) なら \(i\) で終わる増加部分列を \(j\) まで伸ばせるので \(p\) が違い、\(a(i) > a(j)\) なら \(q\) が違います（INJ1）。よって \(i \mapsto p \cdot n + q\) は \(n^2+1\) 個の位置を \(n^2\) 個の値へ相異なるように送り、鳩の巣原理 PH に反します。
\(\begin{cases} n \in \mathbb{M} \\ \forall i \in \mathbb{M} . ( i < ( n \cdot n ) \textit{+1} \Longrightarrow a ( i ) \in \mathbb{M} ) \\ \forall i \in \mathbb{M} . \forall j \in \mathbb{M} . ( i < ( n \cdot n ) \textit{+1} , j < ( n \cdot n ) \textit{+1} , a ( i ) = a ( j ) \Longrightarrow i = j ) \end{cases} \Longrightarrow \exists s \, ( s \nearrow n , s ( n ) < ( n \cdot n ) \textit{+1} , ( a \circ s \nearrow n \mathbin{\rm o\!r} a \circ s \searrow n ) )\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，𝕄0s ，IND𝕄 ，suc𝕄 ，+𝕄 ，*𝕄 ，upd𝕄 ，∘𝕄