Loading article…
網羅的証明は、事例による証明、事例分析による証明、完全帰納法、または力ずく法とも呼ばれ、証明する命題を有限個の事例または同等の事例の集合に分割し、各事例の種類をチェックして問題の命題が成り立つかどうかを確認する数学的証明の方法です。 [1]これは直接証明の方法です。網羅的証明には通常、2つの段階があります。
- ケースの集合が網羅的であることの証明。つまり、証明されるステートメントの各インスタンスが、(少なくとも) 1 つのケースの条件に一致すること。
- それぞれのケースの証明。
デジタルコンピュータの普及により、網羅的証明法の使用の利便性が大幅に向上しました（たとえば、 1976年の4色定理の最初のコンピュータ支援による証明など）。ただし、このようなアプローチは、数学的な優雅さに基づいて異議を唱えられることもあります。エキスパートシステムを使用すると、提示された多くの質問に対する答えを得ることができます。理論的には、網羅的証明法は、ケースの数が有限である場合に使用できます。ただし、ほとんどの数学的集合は無限であるため、この方法は一般的な数学的結果を導き出すためにほとんど使用されません。[2]
カリー・ハワード同型性では、網羅的証明と事例分析は ML スタイルのパターンマッチングと関連している。[要出典]
例
徹底的な証明は、整数が完全な立方体である場合、それが9の倍数であるか、9の倍数より1大きいか、9の倍数より1小さいかのいずれかであることを証明するために使用できます。[3]
証明:
各完全立方体は整数nの立方体です。ここでn は3 の倍数、3 の倍数より 1 大きい、または 3 の倍数より 1 小さいです。したがって、次の 3 つのケースが網羅的です。
- ケース 1: n = 3 pの場合、n 3 = 27 p 3となり、これは 9 の倍数になります。
- ケース 2: n = 3 p + 1 の場合、n 3 = 27 p 3 + 27 p 2 + 9 p + 1 となり、これは 9 の倍数より 1 大きい値です。たとえば、n = 4 の場合、n 3 = 64 = 9×7 + 1 となります。
- ケース3: n = 3 p − 1 の場合、n 3 = 27 p 3 − 27 p 2 + 9 p − 1 となり、これは 9 の倍数より 1 少ない。たとえば、n = 5 の場合、n 3 = 125 = 9×14 − 1となる。QED
優雅
数学者は、多数のケースを網羅的に証明することは洗練されていないとみなされるため、それを避けることを好みます。そのような証明がいかに洗練されていないかを示す例として、現代の夏季オリンピックはすべて4 で割り切れる年に開催されるという次の証明を見てみましょう。
証明：最初の近代夏季オリンピックは1896年に開催され、その後は4年ごとに開催されました（第一次世界大戦、第二次世界大戦、COVID-19パンデミックによって大会スケジュールが混乱したなどの例外的な状況は除きます）。1896 = 474 × 4は4で割り切れるので、次のオリンピックは474 × 4 + 4 = (474 + 1) × 4の年になり、これも4で割り切れます（これは数学的帰納法による証明です）。したがって、この命題は証明されました。
この命題は、夏季オリンピックが開催されたすべての年をリストアップし、そのすべてが 4 で割り切れるかどうかを調べることによって、網羅的に証明することもできます。2016 年現在、夏季オリンピックは合計 28 回開催されているため、これは 28 のケースによる網羅的証明です。
網羅的証明は、エレガントさに欠けるだけでなく、夏季オリンピックが開催されるたびに追加のケースが必要になります。これは、将来にわたってステートメントを無期限に証明する数学的帰納法による証明とは対照的です。
症例数
徹底的な証明で許容されるケースの数に上限はありません。ケースが 2 つまたは 3 つだけの場合もあります。数千または数百万の場合もあります。たとえば、チェスの終盤 パズルを厳密に解くには、その問題のゲーム ツリーで非常に多くの可能な位置を考慮する必要があります。
四色定理の最初の証明は、1834 のケースを網羅した証明でした。[4]この証明は、ケースの大部分が手作業ではなくコンピュータ プログラムによってチェックされたため、議論を巻き起こしました。今日知られている四色定理の最短の証明でも、600 を超えるケースが含まれています。
一般的に、証明全体の誤りの確率は、事例の数が増えるにつれて増大する。事例の数が多い証明は、定理が偶然にのみ成立し、何らかの根本的な原理や関係によるものではないという印象を与える。帰納法による証明（数学的帰納法）などの他の種類の証明は、より簡潔であると考えられている。しかし、他の証明方法が見つかっていない重要な定理もいくつかある。
- 10 次有限射影平面が存在しないことを証明します。
- 有限単純群の分類。
- ケプラー予想。
- ブールピタゴラスの三つ組の問題。
参照
注記
- ^ Reid, D. A; Knipping, C (2010)、数学教育における証明：研究、学習、および教育、Sense Publishers、p. 133、ISBN 978-9460912443。
- ^ S., Epp, Susanna (2011-01-01).離散数学とその応用. Brooks/Cole. ISBN 978-0495391326. OCLC 970542319.
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク) - ^ Glaister, Elizabeth; Glaister, Paul (2017年9月). 「数学的議論、言語、証明 — AS/Aレベル2017」(PDF)。数学協会。 2019年10月25日閲覧。
- ^ Appel, Kenneth; Haken, Wolfgang; Koch, John (1977)、「すべての平面マップは4色で色付け可能。II. 還元可能性」、Illinois Journal of Mathematics、21 (3): 504、doi : 10.1215/ijm/1256049012、MR 0543793、
𝓤の1834の構成のうち