最小反例

数学において、極小反例とは、主張を偽とする最小の例であり、極小反例による証明とは、極小反例の使用と帰納的証明および背理法による証明の考え方を組み合わせた証明法である。^[1]^[2]より具体的には、命題P を証明しようとする場合、まず背理法によって命題 P が偽であると仮定し、したがって少なくとも 1 つの反例が存在すると仮定する。次に、何らかの大きさの考え方 (慎重に選択する必要があるかもしれない) に基づいて、極小の反例Cが存在すると結論付ける。議論に関して、C は一般に非常に仮説的なものである ( Pが真であればCが存在する可能性は排除されるため) が、C が存在するとすれば、帰納的証明と同様の推論を適用した後、 C には矛盾につながる明確な特性があり、それによって命題Pが真であることが示されると主張することは可能である。 ^[3]

矛盾の形式が、極小性の作業仮説の意味でCよりも小さいさらなる反例D を導き出すことができるというものである場合、この手法は伝統的に無限降下による証明と呼ばれます。その場合、証明の議論を構成する方法は複数あり、より複雑になる可能性があります。

反例がある場合、最小の反例が存在するという仮定は、ある種の整列に基づいています。自然数の通常の順序付けは、数学的帰納法の最も一般的な定式化によって明らかに可能ですが、この方法の範囲にはあらゆる種類の整列された帰納法を含めることができます。

例

最小反例法は有限単純群の分類に多用されてきた。巡回群でない有限単純群は偶数位数を持つというフェイト・トムソン定理は、奇数位数の、したがってある極小の単純群Gの仮説に基づいて証明された。G の適切な部分群はすべて可解群であると仮定することができ、そのような部分群の理論の多くを適用できることを意味する。^[4]

ユークリッドの算術基本定理の証明は、最小限の反例を用いた簡単な証明である。^[5]^[6]

クーラントとロビンズは、四色定理の文脈で、最小の反例に対して「最小犯罪者」という用語を使用した。 ^[7]

参考文献

^ Chartrand, Gary、Albert D. Polimeni、Ping Zhang。『数学的証明：上級数学への移行』ボストン：Pearson Education、2013年。印刷。
^ Klipper, Michael (2012年秋). 「最小反例による証明」(PDF) . alpha.math.uga.edu . 2018年4月17日時点のオリジナル(PDF)からアーカイブ。2019年11月28日閲覧。
^ Lewis, Tom (2010年秋). 「§20 最小の反例」(PDF) . math.furman.edu . 2019年11月28日閲覧。
^ フェイト、ウォルター、トンプソン、ジョン G. (1963)、「奇数次群の可解性」、パシフィックジャーナルオブマスマティクス、13 : 775–1029、doi : 10.2140/pjm.1963.13.775、ISSN 0030-8730、MR 0166261
^ 「算術の基本定理 | 割り切れるかどうかと帰納法 | アンダーグラウンド数学」undergroundmathematics.org . 2019年11月28日閲覧。
^ 「算術の基本定理」www.dpmms.cam.ac.uk . 2019年11月28日閲覧。
^ リチャード・クーラント、ハーバート・ロビンズ（1996年）。『数学とは何か？』（第2版）。オックスフォード：オックスフォード大学出版局。ISBN 9780195105193。ここでは、p.495 に「悪いマップを大きくしても意味がないので、反対に、口語的には最小の犯罪者と呼ばれる、最も小さい悪いマップを調べます。」とあります。

[1] Chartrand, Gary、Albert D. Polimeni、Ping Zhang。『数学的証明：上級数学への移行』ボストン：Pearson Education、2013年。印刷。

[2] Klipper, Michael (2012年秋). 「最小反例による証明」(PDF) . alpha.math.uga.edu . 2018年4月17日時点のオリジナル(PDF)からアーカイブ。2019年11月28日閲覧。

[3] Lewis, Tom (2010年秋). 「§20 最小の反例」(PDF) . math.furman.edu . 2019年11月28日閲覧。

[4] フェイト、ウォルター、トンプソン、ジョン G. (1963)、「奇数次群の可解性」、パシフィックジャーナルオブマスマティクス、13 : 775–1029、doi : 10.2140/pjm.1963.13.775、ISSN 0030-8730、MR 0166261

[5] 「算術の基本定理 | 割り切れるかどうかと帰納法 | アンダーグラウンド数学」undergroundmathematics.org . 2019年11月28日閲覧。

[6] 「算術の基本定理」www.dpmms.cam.ac.uk . 2019年11月28日閲覧。

[7] リチャード・クーラント、ハーバート・ロビンズ（1996年）。『数学とは何か？』（第2版）。オックスフォード：オックスフォード大学出版局。ISBN 9780195105193。ここでは、p.495 に「悪いマップを大きくしても意味がないので、反対に、口語的には最小の犯罪者と呼ばれる、最も小さい悪いマップを調べます。」とあります。