徹底的な証明

総当たり証明（事例による証明、事例分析による証明、完全帰納法、総当たり法とも呼ばれる）は、議論をいくつかの異なる事例に分割し、それぞれの事例で命題が成り立つことを証明することによって命題を確立する数学的証明法である。事例は、考えられるすべての状況が考慮されるように、網羅的でなければならない。 ^{[ 1 ]}

デジタルコンピュータの普及により、網羅的証明法（例えば、1976年の4色定理の最初のコンピュータ支援証明）の使用は大幅に便利になったが、このようなアプローチは数学的な優雅さの観点からも異議を唱えられることがある。エキスパートシステムは、提示された多くの質問に対する答えを導き出すために使用できる。理論的には、網羅的証明法は、ケースの数が有限であればいつでも使用できる。しかし、ほとんどの数学的集合は無限であるため、この方法は一般的な数学的結果を導出するためにめったに使用されない。^{[ 2 ]}

場合分けによる証明は通常、次の手順に従います。^{[ 3 ]}

1. 考えられるすべてのケースを特定し、あらゆる可能性を網羅する。
2. 最初のケースについて、その主張を証明せよ。
3. 残りの各ケースについて、その主張を証明せよ。
4. すべての事例が正しいと証明された場合、その命題は成立すると結論づける。いずれかの事例が命題を否定する場合、その命題は成立しない。

事例による証明は、問題が自然に次のような明確なカテゴリに分かれる場合によく使用されます。^{[ 4 ]}

• 偶数と奇数
• 正の値、負の値、ゼロの値
• 関数の異なる区間

この議論は、単一の議論ではあらゆる状況に容易に対応できない場合に特に有効です。

任意の整数 n に対して、n が偶数であれば n ²は偶数であり、n が奇数であればn ^{2は奇数であることを証明せよ。}

証拠：

2つのケースを考えてみましょう。

ケース1

• nは偶数です
• すると、ある整数 k に対して n=2k となる。
• すると n ² = (2k) ² = 4k ² = 2(2k ² ) となり、これは偶数である。

ケース2

• nは奇数です
• すると、n = 2k+1 となる（k はある整数）。
• すると n ² = (2k+1) ² = 4k ² + 4k +1 = 2(2k ² + 2k) +1 となり、これは奇数である。

両方のケースが証明されたので、この主張はすべての整数 n に対して成り立つ。

整数が完全立方数であるならば、それは9の倍数、9の倍数より1大きい数、または9の倍数より1小さい数のいずれかであることを証明せよ。^{[ 5 ]}

証明： 完全立方数はすべて、ある整数nの立方数である。ここでnは 3 の倍数、3 の倍数より 1 大きい数、または 3 の倍数より 1 小さい数のいずれかである。したがって、次の 3 つのケースで全てが網羅される。

• ケース 1: n = 3 pの場合、n ³ = 27 p ³となり、これは 9 の倍数です。
• ケース2：n = 3p  +  1 の場合、n ³ = 27p 3 ⁺  27p  2 + 9p ⁺ 1となり、これは 9 の倍数より 1 大きい数です。例えば、n = 4 の場合、 n ³ = 64 = 9×7 + 1 となります。        
• ケース3：n = 3p  −  1 の場合、n ³ =  27p 3 − 27p ² + 9p − 1 となり、これは9の倍数より1小さい数です。^例えば、n = 5 の場合、 n ³ = 125 = 9×14 − 1となります。証明終了          

数学者は、多数の場合を網羅的に検証する証明を避けることを好みます。これは、数学的に洗練されていないと見なされるからです。数学 的洗練とは、数学的証明の単純さと有効性に基づいた主観的な判断と定義できます。それはしばしば、複雑な概念を表現する最も単純な方法を見つけることとして表されます。^{[ 6 ]} この方法が数学的に洗練されていないと見なされる主な理由は、この方法は結果の数が有限なシナリオで最もよく使用されるからです。結果の数が多い、または無限であるシナリオでは、この方法で証明するのははるかに困難です。^{[ 7 ]}このような証明がどのように洗練されていないかの例として、すべての近代夏季オリンピックが4で割り切れる年に開催されるという次の証明を見てみましょう。

証明：近代夏季オリンピックは1896年に初めて開催され、その後4年ごとに開催されました（第一次世界大戦、第二次世界大戦、COVID-19パンデミックなどにより大会日程が中断された例外的な状況は除きます）。1896年は474×4で割り切れるので、次のオリンピックは474×4+4=(474+1)×4年となり、これも4で割り切れます。以下同様です（これは数学的帰納法による証明です）。したがって、この主張は証明されました。

この主張は、夏季オリンピックが開催されたすべての年を列挙し、それぞれの年が4で割り切れることを確認することで、網羅的に証明することもできます。2016年時点で夏季オリンピックは合計28回開催されているため、これは28の事例による網羅的証明となります。

網羅的証明は、洗練さに欠けるだけでなく、夏季オリンピックが開催されるたびに新たな事例を検討する必要がある。これに対し、数学的帰納法による証明は、その命題を無限に未来まで証明できる。

網羅的証明において、検討すべきケースの数に上限はありません。ケースが2つか3つしかない場合もあれば、数千、あるいは数百万に及ぶ場合もあります。例えば、チェスの終盤パズルを厳密に解くには、その問題のゲームツリーにおける非常に多くの可能な局面を検討する必要があるかもしれません。

四色定理の最初の証明は、1834 のケースによる網羅的証明でした。^{[ 8 ]}この証明は、ケースの大部分が手作業ではなくコンピュータ プログラムによってチェックされたため、物議を醸しました。現在知られている四色定理の最短の証明でも、600 を超えるケースがあります。

一般的に、証明全体における誤りの確率は、ケースの数が増えるにつれて高くなります。ケースの数が多い証明は、定理が偶然に真であるだけで、何らかの根本的な原理や関連性によるものではないという印象を与えます。帰納法（数学的帰納法）などの他の種類の証明は、より洗練されていると考えられています。しかし、他の証明方法が見つかっていない重要な定理もいくつかあります。

• 位数10の有限射影平面が存在しないことを証明する。
• 有限単純群の分類。
• ケプラー予想。
• ブールピタゴラス三つ組問題。

• 大英博物館のアルゴリズム
• コンピュータ支援による証明
• 列挙的帰納法
• 数学的帰納法
• 背理法による証明
• 論理和除去