整列単調量による停止定理

**ステップ1($k$ ステップ後の評価)。** $s_0 \to s_1 \to s_2 \to \cdots \to s_k$ を任意の有効な $k$ ステップの遷移列とする。$i = 1, 2, \dots, k$ に対して仮定 $M(s_{i}) \le M(s_{i-1}) - 1$ を適用して辺々加えると、望遠鏡和により $M(s_k) \le M(s_0) - k$ を得る。

**ステップ2($k$ の上界)。** 到達可能なすべての状態 $s_k \in \mathcal{S}$ について $M(s_k) \ge 0$ なので、2つの不等式を合わせると $0 \le M(s_k) \le M(s_0) - k$、すなわち $k \le M(s_0)$ がただちに従う。したがって長さ $k > M(s_0)$ の有効な遷移列は存在せず、過程は高々 $M(s_0)$ ステップで停止する。