証明

証明

執筆済 数学離散数学

前提から結論へ、論理的に飛躍なく至る道筋。

主な型#

型 方法 使う場面
直接証明 P を仮定して Q を導く 素直に導ける
対偶証明 ¬Q→¬P を示す 結論の否定の方が扱いやすい
背理法 P∧¬Q から矛盾を導く 存在しないことを示す
数学的帰納法 基底 + 帰納段階 自然数に関する主張
構成的証明 実際に作ってみせる 存在の証明。アルゴリズムが得られる

構成的か否か#

存在を示すだけの証明（非構成的）と、 実際の作り方を与える証明（構成的）は実用上大きく違う。

近似アルゴリズムの保証は構成的であることが多く、 証明がそのままアルゴリズムになる。 Goemans-Williamson の 0.878 保証がその例で、 SDP 緩和とランダム丸めという手続きが証明の中に含まれている。

反例#

否定するには反例 1 つで足りる。 McKinnon (1998) が Nelder-Mead 法の非収束を示したのも、 Reddi et al. (2018) が Adam の非収束を示したのも、具体的な反例の構成による。

参考文献#