比較ソートの下界

定理 6.1（「ソートアルゴリズム」§6）・ ✓公理まで証明済み

相異なる $n$ 個の要素を正しく整列する任意の決定的比較ソートについて、最悪の場合に必要な比較回数 $h(n)$ は

h(n) \ge \log_2 (n!) \ge n \log_2 n - n \log_2 e > n\log_2 n - 1.443\,n

を満たす。とくに $h(n) = \Omega(n\log n)$ である。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。