1 鳩の巣原理

word(ss,s)F … \(\)
列（関数）\(f\) の値を \(f(i)\) と書きます。1点の値だけを変えた列があること（upd𝕄）を仮定します（存在は示しません）。
upd𝕄 … \(\exists g \, ( g ( k ) = p , \forall i \in \mathbb{M} . ( i \neq k \Longrightarrow g ( i ) = f ( i ) ) )\)
鳩の巣原理：\(N\) 個の \(i \lt N\) を \(M\) 個の値 \(\lt M\) へ相異なるように送れるなら \(N \le M\)。
PH … \(N , M \in \mathbb{M} , \forall i \in \mathbb{M} . ( i < N \Longrightarrow f ( i ) \in \mathbb{M} , f ( i ) < M ) , \forall i \in \mathbb{M} . \forall j \in \mathbb{M} . ( i < N , j < N , f ( i ) = f ( j ) \Longrightarrow i = j ) \Longrightarrow N \le M\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，𝕄0s ，IND𝕄 ，suc𝕄 ，+𝕄 ，upd𝕄

順序の補題。

2つの数 \(p, q \lt n\) は \(p \cdot n + q \lt n \cdot n\) で1つの数に表せ（L<sq）、表し方は1通り（Lcode）。

2 単調な部分列

\(f \nearrow k\) は \(f(0) \lt f(1) \lt \cdots \lt f(k)\)、\(f \searrow k\) は \(f(0) > f(1) > \cdots > f(k)\)（値は自然数）。
word(ss,p) … \(\nearrow\)  \(\searrow\)
↗. … \(f \nearrow k \Longleftrightarrow \forall j \in \mathbb{M} . ( j \le k \Longrightarrow f ( j ) \in \mathbb{M} ) , \forall j \in \mathbb{M} . ( j < k \Longrightarrow f ( j ) < f ( j \textit{+1} ) )\)
↘. … \(f \searrow k \Longleftrightarrow \forall j \in \mathbb{M} . ( j \le k \Longrightarrow f ( j ) \in \mathbb{M} ) , \forall j \in \mathbb{M} . ( j < k \Longrightarrow f ( j \textit{+1} ) < f ( j ) )\)
列 \(a\) の部分列は、\(s \nearrow k\) となる添字の列 \(s\) と合成 \(a \circ s\) で表します（\((a \circ s)(j) = a(s(j))\)＝∘𝕄 を仮定します）。
word(ss,s) … \(\circ\)
∘𝕄 … \(x \in \mathbb{M} \Longrightarrow ( f \circ g ) ( x ) = f ( g ( x ) )\)
単調な列は短く切っても単調（Ltr↗・Ltr↘）。増加列の値は最後の項以下（Lmono）。
部分列の後ろに1項を足して伸ばす（添字の部分 LEs・値の部分 LE↗・LE↘）。
有限個の選択：\(i \lt M\) の各 \(i\) にラベルを選んだ列があれば \(M\) にも（LCH）。