Proof by contradiction

논리학(logic) 및 수학(mathematics)에서, 모순에 의한 증명(proof by contradiction)은 전제(proposition)가 거짓이라고 가정하면 모순(contradiction)으로 이어짐을 보임으로써 전제의 진리(truth) 또는 타당성(validity)을 확립하는 증명(proof)의 한 형식입니다. 모순에 의한 증명은 간접적 증명(indirect proof), 반대를 가정함으로써 증명(proof by assuming the opposite), 및 reductio ad impossibile으로 역시 알려져 있습니다.^[1] 그것은 reductio ad absurdum으로 알려진 논증의 보다 일반적인 형식의 특정한 종류입니다.^[2]^[3]

Principle

모순에 의한 증명은 아리스토텔레스(Aristotle)에 의해 형이상학적 원칙으로 공식화된 비-모순 법칙(law of noncontradiction)에 근거합니다. 비-모순은 역시 전제적 논리(propositional logic)에서 정리입니다. 이것은 주장이나 수학적 명제가 참과 거짓 둘 다가 될 수 없음을 말합니다. 즉, 전제 Q와 그 부정 $\lnot$ Q ("not-Q")는 둘 다 사실일 수 없습니다. 모순에 의한 증명에서, 입증하려는 명제의 거부가 그러한 모순을 초래한다는 것을 보여줍니다. 그것은 reductio ad absurdum 논증의 형식을 가지고, 보통 다음으로 진행됩니다:

증명되려는 전제 P는 거짓인 것으로 가정합니다. 즉, $\lnot$ P는 참입니다.
그런-다음 $\lnot$ P는 두 개의 서로 상충되는 주장, Q와 $\lnot$ Q를 의미함을 보여줍니다.
Q와 $\lnot$ Q는 둘 다 참일 수 없으므로, P가 거짓이라는 가정이 잘못되었으므로, P는 참이어야 합니다.

세 번째 단계는 유효한 논증 p → q의 다음 가능한 진리 값 경우를 기반으로 합니다.

p(T) → q(T), 여기서 p(x)에서 x는 명제 p의 진리 값입니다; 참에 대해 T 및 거짓에 대해 F입니다.
p(F) → q(T).
p(F) → q(F).

만약 거짓 명제는 가정된 명제에서 유효한 논리를 통해 도달되면, 가정된 명제는 거짓 명제임을 말합니다. 이 사실은 모순에 의해 증명에서 사용됩니다.

모순에 의한 증명은 ${\text{p}}\equiv {\text{p}}\vee \bot \equiv \lnot \left(\lnot {\text{p}}\right)\vee \bot \equiv \lnot {\text{p}}\to \bot$ 으로 공식화되며, 여기서 $\bot$ 는 논리적 모순 또는 거짓 명제 (진리 값이 거짓인 명제)입니다. 만약 $\bot$ 이 유효한 논리를 통해 $\lnot$ P에서 도달되면, $\lnot {\text{p}}\to \bot$ 가 참으로 입증되므로 p는 참으로 입증됩니다.

모순에 의한 증명의 대안적인 형식은 $\lnot$ P가 P를 의미함을 보여줌으로써 입증되려는 명제와 모순을 유도합니다. 이것은 모순이므로 {\ displaystyle \ lnot} P는 거짓이어야 합니다. 진리. 이것은 가정 $\lnot$ P는 반드시 거짓이어야 하며, 동등하게 P는 참이어야 합니다. 이것은 ${\text{p}}\equiv {\text{p}}\vee {\text{p}}\equiv \lnot \left(\lnot {\text{p}}\right)\vee {\text{p}}\equiv \lnot {\text{p}}\to {\text{p}}$ 으로 공식화됩니다.

모순에 의한 존재 증명(existence proof)은 어떤 대상이 존재하지 않는다고 가정하고, 그런-다음 이것이 모순으로 이어질 것임을 증명합니다; 따라서 그러한 대상이 반드시 존재해야 합니다. 비록 수학적 증명에서 상당히 자유롭게 사용될지라도, 모든 수학적 사고의 학파가 이런 종류의 비-구성적 증명(nonconstructive proof)을 보편적으로 유효한 것으로 받아들이지는 않습니다.

Law of the excluded middle

모순에 의한 증명은, 역시 아리스토텔레스가 처음으로 공식화된, 제외된 중간의 법칙(law of the excluded middle)에 의존합니다. 이것은 주장 또는 그 부정 중 하나가 참이어야 함을 말합니다:

\forall P\vdash (P\lor \lnot P)

(모든 전체 P에 대해, P 또는 not-P 중 하나는 참입니다)

즉, 전체가 취할 수 있는 "참"과 "거짓" 이외에 다른 진리 값은 없습니다. 비-모순의 원칙과 결합되어, 이것은 $P$ 와 $\lnot P$ 중 정확히 하나가 참임을 의미합니다. 모순에 의한 증명에서, 이것은 $\lnot P$ 의 가능성이 제외되었으므로, $P$ 는 반드시 참이어야 한다는 결론을 내립니다.

제외된 중간의 법칙은 사실상 모든 공식적인 논리에서 받아들여집니다; 어쨌든, 일부 직관주의(intuitionist) 수학자들은 그것을 받아들이지 않고, 따라서 실행-가능한 증명 기법으로 모순에 의한 증명을 거부합니다.^[4]

Relationship with other proof techniques

모순에 의한 증명은 대우에 의한 증명(proof by contrapositive)과 밀접하게 관련되고, 그 둘은 비록 그들이 구별되는 방법이지만 때때로 혼동되기도 합니다. 주요 차이점은 대우에 의한 증명은 $A\rightarrow B$ (즉, 함축) 형식으로 쓸 수 있는 명제 $P$ 에 오직 적용되지만, 모순에 의한 증명의 기법은 임의의 형식의 명제 $P$ 에 적용되는 것입니다:

대우에 의한 증명 (일반): $\lnot P$ 를 가정하고 모순을 유도합니다.

이것은, 전제적 논리(propositional logic)의 프레임워크에서, 동등

{\text{p}}\equiv {\text{p}}\vee \bot \equiv \lnot \left(\lnot {\text{p}}\right)\vee \bot \equiv \lnot {\text{p}}\to \bot

에 해당하며, 여기서

\bot

는 논리적 모순 또는 거짓 명제 (진리 값이 거짓인 명제)입니다.

입증하려는 명제가 함축 $A\rightarrow B$ 인 경우에서, 그런-다음 직접 증명, 대우에 의한 증명, 및 모순에 의한 증명 사이의 차이는 다음으로 윤곽을 그릴 수 있습니다:

직접 증명: $A$ 를 가정하고 $B$ 를 보입니다.
대우에 의한 증명: $\lnot B$ 를 가정하고 $\lnot A$ 를 보입니다.

이것은 동등

A\rightarrow B\equiv \lnot B\rightarrow \lnot A

에 해당합니다.

모순에 의한 증명: $A$ 와 $\lnot B$ 를 가정하고 모순을 유도합니다.

이것은 동등

{\text{p}}\to {\text{q}}\equiv \lnot {\text{p}}\vee {\text{q}}\equiv \lnot \left({\text{p}}\wedge \lnot {\text{q}}\right)\equiv \lnot \left({\text{p}}\wedge \lnot {\text{q}}\right)\vee \bot \equiv \left({\text{p}}\wedge \lnot {\text{q}}\right)\to \bot

에 해당합니다.

Examples

Irrationality of the square root of 2

수학으로부터 고전적인 모순에 의한 증명은 2의 제곱근이 무리수라는 증명입니다.^[5] 만약 그것이 유리수(rational)이면, 그것은 가장-낮은 항(lowest terms)에서 분수 a/b로 표현될 수 있으며, 여기서 a와 b는 정수(integers)이고, 그것 중 적어도 하나는 홀수(odd)입니다. 그러나 만약 a/b = √2이면, a² = 2b²입니다. 그러므로, a²은 짝수여야 하고, 홀수의 제곱은 홀수이기 때문에, 차례로 a는 그 자체로 짝수임을 의미하며 — 이것은 a/b가 가장-낮은 항이기 때문에 b가 홀수여야 함을 의미합니다.

다른 한편으로, 만약 a가 짝수이면, a²은 4의 배수입니다. 만약 a²이 4의 배수이고 a² = 2b²이면, 2b²은 4의 배수이고, 따라서 b²은 짝수여야 하며, 이것은 b 역시 그래야 함을 의미합니다.

그래서 b가 홀수와 짝수 둘 다이므로, 모순입니다. 그러므로, 초기 가정 — √2가 분수로 표현될 수 있음 — 은 거짓이어야 합니다.^[6]

The length of the hypotenuse

모순에 의한 증명의 방법은 임의의 비-퇴화(non-degenerate) 직각 삼각형(right triangle)에 대해, 빗변의 길이가 나머지 두 변의 길이의 합보다 작다는 것을 보여주기 위해 역시 사용되어 왔습니다.^[7] c를 빗변의 길이, a와 b를 다리의 길이로 놓음으로써, 우리는 주장을 보다 간결하게 a + b > c로 역시 표현할 수 있습니다. 이 경우에서, 모순에 의한 증명은 피타고라스의 정리(Pythagorean theorem)에 호소함으로써 만들어질 수 있습니다.

먼저, 그 주장은 a + b ≤ c임을 가정하기 위해 부정됩니다. 이 경우에서, 양쪽 변을 제곱하여 (a + b)² ≤ c², 또는 동등하게, a² + 2ab + b² ≤ c²임을 산출할 것입니다. 삼각형은 만약 각 변이 양의 길이를 가지면 비-퇴화이므로, a와 b 둘 다는 0보다 크다고 가정할 수 있습니다. 그러므로, a² + b² < a² + 2ab + b² ≤ c², 및 추이적 관계(transitive relation)는 나아가서 a² + b² < c²로 감소될 수 있습니다.

다른 한편으로, 피타고라스 정리에서 a² + b² = c²이라는 것이 역시 알려져 있습니다. 이것은 엄격한 부등식과 상등이 서로 배타적(mutually exclusive)이기 때문에 모순을 초래할 것입니다. 모순은 둘 다 참은 불가능이고 피타고라스 정리가 유지된다는 것으로 알려져 있음을 의미합니다. 그것으로부터 가정 a + b ≤ c는 거짓이어야 하고 따라서 a + b > c라는 주장을 입증했음을 따릅니다.

No least positive rational number

전제, P: "0보다 더 큰 가장-작은 유리수는 없습니다"를 생각해 보십시오. 모순에 의한 증명에서, 우리는 반대, ¬P: 가장-작은 유리수, 말하자면, r이 있음을 가정함으로써 시작합니다.

이제, r/2는 0보다 크고 r보다 작은 유리수입니다. 그러나 이것은 r이 가장-작은 유리수였다는 가정에 모순됩니다 (만약 "r이 가장-작은 유리수입니다"가 Q였으면, 우리는 "r/2이 r보다 더 작은 유리수"라는 ¬Q를 추론할 수 있습니다). 이 모순은 원래 명제 P는 참이어야 함을 보여줍니다. 즉, "0보다 더 큰 가장-작은 유리수는 없습니다".

Other

다른 예제에 대해, 2의 제곱근이 유리수가 아니라는 증명 (여기서 위의 증명과 다른 간접 증명이 찾아질 수 있음)과 칸토어의 대각선 논증(Cantor's diagonal argument)을 참조하십시오.

Notation

모순에 의한 증명은 때때로 단어 "모순!"으로 끝납니다. 아이작 배로(Isaac Barrow)와 베어만(Baermann)은 Q.E.D.의 줄을 따라, "quod est absurdum" ("이것은 터무니없습니다")에 대해, 표기법 Q.E.A.를 사용했지만, 이 표기법은 오늘날 거의 사용되지 않습니다.^[8]^[9] 모순에 대해 때때로 사용되는 그래픽 기호는 아래방향 지그재그 화살표 "번개" 기호 (U+21AF: ↯)이며, 예를 들어 데비와 프리즐리(Davey and Priestley)에 있습니다.^[10] 때때로 사용되는 다른 것은 ( $\rightarrow \!\leftarrow$ 또는 $\Rightarrow \!\Leftarrow$ 와 같은) 반대 화살표(opposing arrows)의 쌍, 밖으로-향한 화살표 ( $\nleftrightarrow$ ), (U+2A33: ⨳와 같은) 해시의 양식화된 형식, 또는 "참조 표식" (U+203B: ※)을 포함합니다.^[11]^[12] 철학자와 논리학자 (모순을 참조하십시오)에 의해 사용되는 "위방향 압정" 기호 (U+22A5: ⊥)가 역시 나타나지만, 직교성(orthogonality)에 대해 그것의 사용으로 인해 종종 피합니다.

Principle of explosion

비-모순 원리의 흥미로운 논리적 결과는 모순이 임의의 명제를 암시한다는 것입니다; 만약 모순이 참으로 받아들여지면, 임의의 전제 (그것의 부정을 포함하여)는 그것으로부터 입증될 수 있습니다.^[13] 이것은 폭발의 원리(principle of explosion) (Latin: ex falso quodlibet, "거짓말로부터, 임의의 것이 [따릅니다]", 또는 ex contradictione sequitur quodlibet, "모순으로부터, 임의의 것이 따릅니다"), 또는 유사-스카투스(pseudo-scotus)의 원리로 알려져 있습니다.

\forall Q:(P\land \lnot P)\rightarrow Q

(모든 Q에 대해, P와 not-P는 Q를 의미합니다)

따라서 형식적인 공리 시스템(formal axiomatic system)에서 모순은 비참한 것입니다; 임의의 정리가 참으로 입증될 수 있으므로, 그것은 진리와 허위의 관습적 의미를 파괴합니다.

러셀의 역설(Russell's paradox)과 같이, 20세기 초에서 수학의 토대에서 모순의 발견은 폭발의 원리로 인해 수학의 전체 구조를 위협했습니다. 이것은 20세기 동안 수학에 대해 논리적 토대를 제공하기 위해 일관된 공리 시스템을 만들기 위해 많은 연구에 동기를 부여했습니다. 이것은 역시 니우통 다 코스타(Newton da Costa), 월터 카르니엘리(Walter Carnielli), 및 그레이엄 프리스트(Graham Priest)와 같은 몇몇 철학자들이 초일관 논리(paraconsistent logic)와 변증법(dialethism)과 같은 이론을 일으켜, 비-모순의 원리를 거부하게 만들었으며, 이것은 참과 거짓 둘 다인 명제가 존재한다는 것을 받아들입니다.^[14]

Reception

고드프리 해럴드 하디(G. H. Hardy)는 모순에 의한 증명을 "수학자의 최고의 무기 중 하나", "그것은 임의의 체스 첫-수(chess gambit)보다 훨씬 더 좋은 첫-수입니다: 체스 플레이어는 폰 또는 심지어 피스의 희생을 제공할 수 있지만, 수학자는 게임을 제공합니다"라고 말하는 것으로 묘사합니다.^[2]

References

^ "Reductio ad absurdum | logic". Encyclopedia Britannica. Retrieved 2019-10-25.
^ ^a ^b G. H. Hardy, A Mathematician's Apology; Cambridge University Press, 1992. ISBN 9780521427067. PDF p.19.
^ S. M. Cohen, "Introduction to Logic", Chapter 5 "proof by contradiction ... Also called indirect proof or reductio ad absurdum ..."
^ "The Definitive Glossary of Higher Mathematical Jargon — Proof by Contradiction". Math Vault. 2019-08-01. Retrieved 2019-10-25.{{cite web}}: CS1 maint: url-status (link)
^ Alfeld, Peter (16 August 1996). "Why is the square root of 2 irrational?". Understanding Mathematics, a study guide. Department of Mathematics, University of Utah. Retrieved 6 February 2013.
^ "Proof by contradiction". Art of Problem Solving. Retrieved 2019-10-25.{{cite web}}: CS1 maint: url-status (link)
^ Stone, Peter. "Logic, Sets, and Functions: Honors" (PDF). Course materials. pp 14–23: Department of Computer Sciences, The University of Texas at Austin. Retrieved 6 February 2013.{{cite web}}: CS1 maint: location (link)
^ "Math Forum Discussions".
^ "The Definitive Glossary of Higher Mathematical Jargon — Q.E.A." Math Vault. 2019-08-01. Retrieved 2019-10-25.{{cite web}}: CS1 maint: url-status (link)
^ B. Davey and H.A. Priestley, Introduction to lattices and order, Cambridge University Press, 2002.
^ The Comprehensive LaTeX Symbol List, pg. 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf
^ Gary Hardegree, Introduction to Modal Logic, Chapter 2, pg. II–2. https://web.archive.org/web/20110607061046/http://people.umass.edu/gmhwww/511/pdf/c02.pdf
^ Ferguson, Thomas Macaulay; Priest, Graham (2016). A Dictionary of Logic. Oxford University Press. p. 146. ISBN 978-0192511553.
^ Carnielli, Walter; Marcos, João (2001). "A Taxonomy of C-systems". arXiv:math/0108036.