Minimal counterexample
수학(mathematics)에서, 최소 반대예제(minimal counterexample)는 주장을 반증하는 가장 작은 예제이고, 최소 반대예제에 의한 증명(proof by minimal counterexample)은 최소 반대예제의 사용과 귀납법에 의한 증명(proof by induction)과 모순에 의한 증명(proof by contradiction)의 아이디어를 결합한 증명의 방법입니다.[1][2] 보다 구체적으로, 제안 P를 증명하려고 시도할 때, 우리는 먼저 그것이 거짓이고, 따라서 적어도 하나의 반대예제(counterexample)가 있어야 한다는 모순에 의해 가정합니다. 그런-다음 (신중하게 선택해야 할 수도 있는) 크기의 몇 가지 아이디어와 관해, 최소(minimal)인 그러한 반대예제 C가 있다고 결론을 내립니다. 논증과 관련하여, C는 일반적으로 매우 가설적인 것이지만 (P의 진리가 C의 가능성을 배제하기 때문에), 만약 C가 존재했으면, 그것은 모순을 야기할, 귀납적 증명에서 그것과 유사한 몇 가지 추론을 적용한 후, 어떤 명확한 속성을 가질 것이고, 그것에 따라 명제 P가 실제로 참이라는 것을 보여줄 것이라고 주장하는 것이 가능할 것입니다.[3]
만약 모순의 형식이 우리가 추가 반대예제 D를 유도할 수 있다는 것이고, 그것이 최소성의 작동하는 가설의 의미에서 C보다 작다는 것이면, 이 기술은 전통적으로 무한 하강에 의한 증명(proof by infinite descent)이라고 불립니다. 어떤 경우에서, 증명의 논증을 구성하는 여러 가지 더 복잡한 방법이 있을 수 있습니다.
반대예제가 있으면, 최소의 반대예제가 있다는 가정은 일종의 바른-순서화(well-ordering)에 기반합니다. 자연수 위에 보통의 순서화는 수학적 귀납법(mathematical induction)의 가장 보통의 형식화에 의해 명확하게 가능합니다; 그러나 방법의 범위는 임의의 종류의 바른-순서화된 귀납법(well-ordered induction)을 포함할 수 있습니다.
Examples
최소 반대예제 방법은 유한 단순 그룹의 분류(classification of finite simple groups)에 많이 사용되었습니다. 순환 그룹(cyclic groups)이 아닌 유한 단순 그룹이 짝수 순서를 가진다는 파이트–톰프슨 정리(Feit–Thompson theorem)는 일부의 가설, 및 따라서 홀수 순서의 일부 최소, 단순 그룹 G을 기반으로 했습니다. G의 모든 적절한 부분그룹은 해결-가능 그룹(solvable group)으로 가정될 수 있으며, 이는 그러한 부분그룹에 대한 많은 이론이 적용될 수 있음을 의미합니다.
산술의 기본 정리에 대한 유클리드의 증명(Euclid's proof of the fundamental theorem of arithmetic)은 최소 반대예제를 사용하는 간단한 증명입니다.[4][5]
References
- ^ Chartrand, Gary, Albert D. Polimeni, and Ping Zhang. Mathematical Proofs: A Transition to Advanced Mathematics. Boston: Pearson Education, 2013. Print.
- ^ Klipper, Michael (Fall 2012). "Proof by Minimum Counterexample" (PDF). alpha.math.uga.edu. Archived from the original (PDF) on 2018-04-17. Retrieved 2019-11-28.
- ^ Lewis, Tom (Fall 2010). "§20 Smallest Counterexample" (PDF). math.furman.edu. Retrieved 2019-11-28.
{{cite web}}: CS1 maint: url-status (link) - ^ "The Fundamental Theorem of Arithmetic | Divisibility & Induction | Underground Mathematics". undergroundmathematics.org. Retrieved 2019-11-28.
- ^ "The fundamental theorem of arithmetic". www.dpmms.cam.ac.uk. Retrieved 2019-11-28.