모순에 의한 증명

논리학에서 모순에 의한 증명은 명제를 거짓으로 가정하면 모순이 발생한다는 것을 보여줌으로써 명제의 진실성 또는 타당성을 확립하는 증명의 한 형태입니다.비록 그것이 수학적 증명에 아주 자유롭게 사용되지만, 모든 수학적 사고의 학파가 이러한 비건설적인 증명을 보편적으로 타당하다고 받아들이는 것은 아닙니다.

더 넓게 보면, 모순에 의한 증명은 최초의 가정이 증명해야 할 진술의 부정이 아닐 때에도 모순에 도달함으로써 진술을 확립하는 모든 형태의 논증입니다.이러한 일반적인 의미에서 모순에 의한 증명은 간접적 증명, 반대의 ^[1]가정에 의한 증명,^[2] 축소 불가능이라고도 합니다.

모순에 의한 증명을 사용하는 수학적 증명은 보통 다음과 같이 진행됩니다.

증명해야 할 명제는 P입니다.
우리는 P를 거짓으로 가정합니다. 즉, πP를 가정합니다.
그러면 θP는 거짓을 의미하는 것으로 나타납니다.이는 일반적으로 서로 상반되는 두 주장인 Q와 δQ를 도출하고 모순이 없는 법칙에 호소함으로써 달성됩니다.
P를 거짓으로 가정하면 모순이 발생하기 때문에 P를 사실로 결론짓습니다.

중요한 특수한 경우는 모순에 의한 존재 증명입니다. 주어진 성질을 가진 물체가 존재한다는 것을 증명하기 위해 모든 물체가 성질의 부정을 만족한다는 가정에서 모순을 도출합니다.

형식화

이 원리는 "P를 거짓으로 가정하는 것이 거짓을 의미한다면, P는 참이다"라는 명제 공식 ¬¬P ⇒ P와 동등하게 표현될 수 있습니다.

자연적 추론에서 원리는 추론 규칙의 형태를 취합니다.

{\cfrac {\vdash \lnot \lnot P}{\vdash P}

"만약 ¬ $\lnot \lnot P$ ${\displaystyle \lnot \lnot$ P $}$ 가 증명된다면, $P$ {\ $displaystyle$ P $}$ 는 종결될 수 있습니다."

순차 미적분학에서 원리는 순차적으로 표현됩니다.

\Gamma,\lnot \lnot P\vdash P,\Delta

"가설 $\Gamma$ 와 $\Gamma$ ${\displaystyle \lnot \lnot$ P $}$ 는 $\nnnot\lnot$ $결론$ P ${\displaystyle$ P $}$ 또는 $P$ $\Delta$ 를 수반합니다." $\Delta$

정당화

고전 논리학에서 이 원칙은 명제 ¬¬P ⇒ P의 진리표의 조사에 의해 정당화될 수 있으며, 이는 그것이 어투톨로지임을 보여줍니다.

p	$◦p$	$◦p$	$\neg\negp \Rightarrowp$
T	F	T	T
F	T	F	T

원칙을 정당화하는 또 다른 방법은 다음과 같이 배제중의 법칙에서 도출하는 것입니다.우리는 σP를 가정하고 P를 증명하려고 합니다.제외 중간 P의 법칙에 따라 다음 중 하나가 성립하거나 성립하지 않습니다.

P가 유지되면 당연히 P가 유지됩니다.
만약 τP가 성립한다면, 우리는 τP와 τP에 모순의 법칙을 적용함으로써 거짓을 도출하고, 그 후 폭발의 원리는 우리가 P를 결론지을 수 있게 합니다.

어느 경우든 우리는 P를 설립했습니다.반대로, 모순에 의한 증명은 배제중의 법칙을 도출하는 데 사용될 수 있음이 밝혀졌습니다.

고전적 순차 미적분학에서 모순에 의한 LK 증명은 부정에 대한 추론 규칙에서 유도할 수 있습니다.

{\cfrac {\cfrac {\}{\Gamma,P\vdash P,\Delta }}\;(I)}{\Gamma,\vdash \lnot P,P,\Delta }}\;({\lnot }R)}{\Gamma,\not \lnot P\vdash P,\Delta }}\;({\lnot }L)

다른 증명기법과의 관계

모순반박

모순에 의한 증명은 ^[3]^[4]γP가 다음과 같이 증명되는 모순에 의한 반박과 유사합니다.

증명해야 할 명제는 ¬P입니다.
P라고 가정합니다.
거짓을 알아냅니다.
결론 ¬P.

반대로 모순에 의한 증명은 다음과 같이 진행됩니다.

증명해야 할 명제는 P입니다.
¬P로 가정합니다.
거짓을 알아냅니다.
결론 P.

모순에 의한 반박은 증명해야 할 명제가 부정될 때만 적용되는 반면, 모순에 의한 증명은 어떤 명제에도 ^[5]적용될 수 있기 때문에 형식적으로 이것들은 같지 않습니다.P ${\displaystyle$ P $}$ 와 ¬ $\neg \neg P$ ${\displaystyle \neg \neg$ P $}$ 를 자유롭게 교환할 수 있는 $P$ 논리에서는 그 구분이 크게 모호합니다.따라서 수학적 실천에서 두 원리는 "모순에 의한 증명"이라고 불립니다.

배제중의 법칙

모순에 의한 증명은 아리스토텔레스에 의해 처음 공식화된 배제중의 법칙과 동등하며, 주장 또는 그 부정이 참이라는 P ∨ P.

모순금지법

모순이 없는 법칙은 아리스토텔레스에 의해 형이상학적 원리로 처음 언급되었습니다.명제와 그 부정이 모두 참일 수 없고, 또는 동등하게 명제가 참일 수도 없고 거짓일 수도 없다고 가정합니다.형식적으로는 모순이 없는 법칙을 ¬(P ∧ ¬ P)라고 쓰고 "명제가 참이면서 거짓인 경우는 아니다"라고 읽습니다.모순이 없는 법칙은 모순에 의한 증명의 원칙에 따르지도 않고 암시되지도 않습니다.

배제된 중치 법칙과 모순되지 않는 법칙이 함께 존재한다는 것은 P와 δP 중 하나만 참임을 의미합니다.

직관적 논리의 모순에 의한 증명

직관적 논리에서 모순에 의한 증명은 일반적으로 유효하지 않지만, 일부 특정 사례가 도출될 수 있습니다.반대로 부정의 증명과 모순의 원리는 직관적으로 타당합니다.

브라우어-모순에 의한 증명의 헤이팅-콜모고로프 해석은 다음과 같은 직관적 타당성 조건을 제공합니다.

"명제가 거짓이라고 단정할 수 있는 방법이 없다면, 그 명제가 참이라고 단정할 수 있는 방법이 있습니다."

알고리즘을 의미하는 것으로 "방법"을 택하면, 중단 문제를 해결할 수 있기 때문에 조건을 받아들일 수 없습니다.방법을 알아보려면 "튜링 머신 M이 정지하거나 정지하지 않습니다."라는 H(M) 문구를 생각해 보십시오.그 부정 ¬H(M)는 "M은 멈추지도 멈추지도 않는다"고 진술하는데, 이는 모순이 없는 법칙(직관적으로 타당함)에 의해 거짓입니다.만일 모순에 의한 증명이 직관적으로 유효하다면, 우리는 임의의 튜링 기계 M이 정지하는지 여부를 결정하는 알고리즘을 얻어서 정지 문제의 (직관적으로 유효한) 해결 불가능의 증명을 위반할 것입니다.

¬¬ $\lnot \lnot P\Rightarrow P$ ⇒ $\lnot \lnot P\Rightarrow P$ P ¬ $\lnot \lnot P\Rightarrow P$ ¬ P {\ $display$ style $\lnot \lnot$ P $\Rightarrow P}$ 를 만족시키는 명제 P를 --안정 명제라고 합니다.따라서 직관적 논리에서 모순에 의한 증명은 보편적으로 유효하지 않지만 π-안정 명제에만 적용될 수 있습니다.그러한 명제의 예는 결정 가능한 것, 즉 P $P\lor \lnot P$ $P\lor \lnot P$ ${\displaystyle$ P\ $lor \lnot$ P $P\lor \lnot P$ 를 $P\lor \lnot P$ 시키는 것입니다. 실제로, 배제된 중간 법칙이 모순에 의한 증명을 의미한다는 위의 증명은 결정 가능한 명제가 π-안정적이라는 것을 보여주기 위해 용도를 변경할 수 있습니다."n {\ $displaystyle$ n $}$ 이 $n$ prime" $또는$ "a {\ $displaystyle$ a $}$ 가 $a$ b{\ $displaystyle$ b $}$ 을(를) $분할$ 한다"와 같이 직접 계산으로 확인할 수 있는 문이 대표적인 예입니다.

모순에 의한 증명의 예

유클리드의 원소

모순에 의한 초기 증명은 유클리드의 요소, 1권, 명제 ^[6]6에서 찾을 수 있습니다.

삼각형에서 두 개의 각도가 서로 같다면, 같은 각도의 반대쪽 또한 서로 같습니다.

증명은 반대각이 같지 않다고 가정함으로써 진행되며, 모순을 도출합니다.

힐베르트의 널스텔렌사츠

모순에 의한 영향력 있는 증거는 데이비드 힐버트에 의해 제시되었습니다.그의 Nullstellensatz는 다음과 같이 말합니다.

f_{1},\ldots ,f_{k}

1

f_{1},\ldots ,f_{k}

f_{1},\ldots ,f_{k}

f_{1},\ldots ,f_{k}

f_{1},\ldots ,f_{k}

{\

displaystyle f_{1},\ldots,f_{k}

가 복소수 계수가 공통인

n개

의 불확정형이면

,

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

g

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

1

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

+ …,

g_{1},\ldots ,g_{k}

k {\

displaystyle g_{1},\ldots,g_{

k}가

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

g_{1},\ldots ,g_{k}

다항식

g_{1},\ldots ,g_{k}

1

g_{1},\ldots ,g_{k}

… +

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

k

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

=

.

{\

displaystyle f_{1}

g_

{1}+\ldots +f_{k}g_{

k}=1.

힐베르트는 이러한 $g_{1},\ldots ,g_{k}$ g $g_{1},\ldots ,g_{k}$ $g_{1},\ldots ,g_{k}$ $g_{1},\ldots ,g_{k}$ {\ $displaystyle g_{1},\ldots, g_{k}$ 가 $g_1, \ldots, g_k$ 없다고 가정하고 모순을 도출했습니다.^[7]

무한소 소수

유클리드의 정리는 무한히 많은 소수들이 있다는 것을 말합니다.유클리드의 원소에서 이 정리는 제9편 명제 20에 ^[8]나와 있습니다.

소수는 할당된 소수의 수보다 많습니다.

우리가 위 진술서를 어떻게 공식적으로 쓰느냐에 따라, 일반적인 증명은 모순에 의한 증명 또는 모순에 의한 반박의 형태를 취하게 됩니다.우리는 여기 전자를 제시합니다. 아래에서 어떻게 증명이 모순에 의한 반박으로 이루어지는지 확인합니다.

유클리드 정리를 모든 $자연수$ n ${\displaystyle$ n $}$ 에 $n$ 대하여 그것보다 더 큰 소수가 있다는 것으로 공식적으로 표현하면, 우리는 다음과 같이 모순에 의한 증명을 사용합니다.

임의의 $수$ ${\displaystyle$ n $n$ 이 주어졌을 때, 우리는 n{\ $displaystyle$ n $n$ 보다 큰 소수가 존재함을 증명하려고 합니다. 반대로 그러한 p가 존재하지 않는다고 가정합니다(모순에 의한 증명의 적용).그러면 모든 소수는 n ${\displaystyle$ n $n$ 보다 작거나 같으며, $p_{1},\ldots ,p_{k}$ $p_{1},\ldots ,p_{k}$ $p_{1},\ldots ,p_{k}$ {\ $displaystyle p_{1},\ldots, p_{k}$ 의 $p_{1},\ldots ,p_{k}$ $p_{1},\ldots ,p_{k}$ 을 만들 수 있습니다. $P=p_{1}\cdot \ldots \cdot p_{k}$ = $P=p_{1}\cdot \ldots \cdot p_{k}$ 1 ⋅ … ⋅ $P=p_{1}\cdot \ldots \cdot p_{k}$ ${\displaystyle$ P = $p_{1}\cdot \ldot \cdot p_{k}}$ 를 모든 소수의 곱이라 $Q=P+1$ Q = $Q=P+1$ + $Q=P+1$ {\ $displaystyle$ Q = $P+1$ $}$ 이라고 합니다. Q{\ $displaystyle$ Q}는 모든 소수보다 $Q$ 그 중 하나로 나누어져야 $.$ 이제 P ${\displaystyle$ P $}$ 와 $Q$ ${\displaystyle$ Q $}$ 는 $P$ d입니다.i는 $p_{i}$ ${\displaystyle p_{i$ 로 볼 수 있으므로 $Q-P=1$ Q - $Q-P=1$ = $Q-P=1$ {\ $displaystyle Q-P$ = $1$ 이(가) 어떤 소수로도 나눌 수 없기 때문입니다.따라서 모순이 있으므로 n ${\displaystyle$ n $}$ 보다 큰 소수가 있습니다.

모순에 의한 반박의 예

다음 예는 일반적으로 모순에 의한 증명으로 언급되지만 형식적으로는 모순에 의한 반박을 사용합니다(따라서 직관적으로 ^[9]타당합니다).

무한소 소수

유클리드의 정리인 제9권, 명제 20:^[10]

소수는 할당된 소수의 수보다 많습니다.

우리는 모든 소수의 유한한 목록에 대해, 그 목록에 없는 또 다른 소수가 있다는 것을 말하는 것으로 읽을 수도 있습니다. 이 소수는 거의 틀림없이 유클리드의 원래 공식과 더 가깝고 같은 정신입니다.이 경우 유클리드의 증명은 다음과 같이 한 단계에서 모순에 의한 반박을 적용합니다.

소수 $p_{1},\ldots ,p_{n}$ $p_{1},\ldots ,p_{n}$ $p_{1},\ldots ,p_{n}$ $p_{1},\ldots ,p_{n}$ ${\$ 의 유한한 목록이 주어지면, 이 목록에 없는 소수가 적어도 하나 더 존재하는 것으로 표시됩니다.P = $P=p_{1}\cdot p_{2}\cdots p_{n}$ 1 ⋅ $P=p_{1}\cdot p_{2}\cdots p_{n}$ 2 ⋯ $P=p_{1}\cdot p_{2}\cdots p_{n}$ n $P=p_{1}\cdot p_{2}\cdots p_{n}$ {\ $displaystyle P_{1}\cdot p_{2}\cdots p_{n}$ 를 나열된 모든 소수의 곱이라 $p$ p{\ $displaystyle$ p $}$ 를 P $P+1$ + $P+1$ {\ $displaystyle$ P $+$ $1$ 의 소수점으로 하고 $P+1$ $P+1$ + 1 {\ $displaystyle$ P+ $1}$ 자체일 $P+1$ 이 있습니다.p ${\displaystyle$ p $}$ 이 $p$ (가) 주어진 소수의 목록에 없다고 $p$ 합니다.(모순에 의한 반박의 적용)이라고 정반대로 가정합니다. $그러면$ p{\ $displaystyle$ p $}$ 는 $p$ P{\ $displaystyle$ P $}$ 와 $P$ $P+1$ P + $P+1$ {\ $displaystyle$ P $+1$ 을(를) 둘 $다$ 나눕니다. 따라서 이들의 차이는 1 ${\displaystyle$ 1 $1$ 이(가) 없기 때문에 모순됩니다.

2의 제곱근의 무리성

2의 제곱근이 비이성적이라는 고전적인 증거는 ^[11]모순에 의한 반박입니다.실제로, 우리는 2의 제곱근인 자연수 a와 b가 존재한다고 가정하고, 모순을 도출하여 부정 ¬ a, b ∈ $\mathbb {N}$ {\ $displaystyle \mathbb {N$ }}. a/b = √2를 증명하기 시작했습니다.

무한 혈통에 의한 증명

무한 하강에 의한 증명은 원하는 성질을 가진 가장 작은 물체가 다음과 같이 존재하지 않는 것을 증명하는 방법입니다.

원하는 속성을 가진 가장 작은 개체가 있다고 가정합니다.
원하는 속성을 가진 훨씬 더 작은 개체가 존재함을 입증하여 모순을 도출합니다.

그러한 증명은 다시 모순에 의한 반박입니다.전형적인 예는 "가장 작은 양의 유리수는 없다"는 명제의 증명이다: 가장 작은 양의 유리수 q가 있다고 가정하고 다음을 관찰함으로써 모순을 유도합니다.q/2는 심지어 q보다 작고 여전히 양수입니다.

러셀의 역설

러셀의 역설(Russell paradox)은 "요소가 자신을 포함하지 않는 정확하게 집합인 집합은 없다"고 정의하며, 일반적인 증명이 모순에 의한 반박인 부정된 진술입니다.

표기법

모순에 의한 증명은 때때로 "모순!"이라는 단어로 끝납니다.아이작 배로우와 베어만은 Q.E.D.의 행을 따라 Q.E.A.라는 표기법을 사용했지만 오늘날 ^[12]이 표기법은 거의 사용되지 않습니다.때때로 모순에 사용되는 그래픽 기호는 아래쪽 지그재그 화살표 "번개" 기호(U+21AF: ↯)이며, 예를 들어 Davey and Priestley에서 사용됩니다.다른 방법으로는 → ${\displaystyle \right$ arrow \!\ $left$ arrow $}$ 또는 $\Rightarrow \!\Leftarrow$ ⇐ {\ $displaystyle$ \ $right$ arrow \! $\Leftarrow}),$ 삼진 화살표 $\nleftrightarrow$ $↮$ ${\displaystyle \nleft$ right arrow $}),$ 해시의 스타일화된 형태(예: U+2A33: $⨳$ ), 또는 "참조 표시"(U+203B: $\times \!\!\!\!\times$ 또는 $\times \!\!\!\!\times$ ${\displaystyle$ \times $\!\!$ $\!\!\times$ ^[14]^[15]

하디의 견해

G.H. 하디는 모순에 의한 증명을 "수학자의 가장 훌륭한 무기 중 하나"라고 묘사하며, "이것은 어떤 체스 게임보다 훨씬 더 훌륭한 게임입니다. 체스 선수는 전당포나 심지어 조각의 희생을 제공할 수 있지만, 수학자는 ^[16]게임을 제공합니다."라고 말했습니다.

참고 항목

참고문헌

^ "Proof By Contradiction". www2.edc.org. Retrieved 12 June 2023.
^ "Reductio ad absurdum logic". Encyclopedia Britannica. Retrieved 25 October 2019.
^ "Proof by contradiction". nLab. Retrieved 7 October 2022.
^ Richard Hammack, Book of Proof, 3판, 2022, ISBN 978-0-9894721-2-8; "9장: 반증" 참조.
^ Bauer, Andrej (29 March 2010). "Proof of negation and proof by contradiction". Mathematics and Computation. Retrieved 26 October 2021.
^ "Euclid's Elements, Book 6, Proposition 1". Retrieved 2 October 2022.
^ Hilbert, David (1893). "Ueber die vollen Invariantensysteme". Mathematische Annalen. 42 (3): 313–373. doi:10.1007/BF01444162.
^ "Euclid's Elements, Book 9, Proposition 20". Retrieved 2 October 2022.
^ Bauer, Andrej (2017). "Five stages of accepting constructive mathematics". Bull. Amer. Math. Soc. 54 (2017), 481-498. Retrieved 2 October 2022.
^ "Euclid's Elements, Book 9, Proposition 20". Retrieved 2 October 2022.
^ 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.
^ "Math Forum Discussions".
^ B. 데이비와 H.A.프리스틀리, 격자와 질서 입문, 캠브리지 대학 출판부, 2002; "참고 지수" 참조, p. 286.
^ Gary Hardegree, Modal Logic 입문, 2장, pg.II–2. https://web.archive.org/web/20110607061046/http ://people.umass.edu/gmhwww/511/pdf/c02.pdf
^ The Comprehensive LaTeX Symbol List, 페이지 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf
^ G. H. Hardy, 수학자의 사과; Cambridge University Press, 1992 ISBN 9780521427067. PDF p.19 Wayback Machine에서 2021-02-16 보관

추가열람 및 외부 링크

Franklin, James; Daoud, Albert (2011). Proof in Mathematics: An Introduction. chapter 6: Kew. ISBN 978-0-646-54509-7.{{cite book}}: CS1 메인 : 위치 (링크)
Larry W. Cusick's How to Write Proofs의 모순에 의한 증명
인터넷 철학 백과사전 축소판; ISSN 2161-0002

[1] "Proof By Contradiction". www2.edc.org. Retrieved 12 June 2023.

[2] "Reductio ad absurdum logic". Encyclopedia Britannica. Retrieved 25 October 2019.

[3] "Proof by contradiction". nLab. Retrieved 7 October 2022.

[4] Richard Hammack, Book of Proof, 3판, 2022, ISBN 978-0-9894721-2-8; "9장: 반증" 참조.

[5] Bauer, Andrej (29 March 2010). "Proof of negation and proof by contradiction". Mathematics and Computation. Retrieved 26 October 2021.

[6] "Euclid's Elements, Book 6, Proposition 1". Retrieved 2 October 2022.

[7] Hilbert, David (1893). "Ueber die vollen Invariantensysteme". Mathematische Annalen. 42 (3): 313–373. doi:10.1007/BF01444162.

[8] "Euclid's Elements, Book 9, Proposition 20". Retrieved 2 October 2022.

[9] Bauer, Andrej (2017). "Five stages of accepting constructive mathematics". Bull. Amer. Math. Soc. 54 (2017), 481-498. Retrieved 2 October 2022.

[10] "Euclid's Elements, Book 9, Proposition 20". Retrieved 2 October 2022.

[11] 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.

[12] "Math Forum Discussions".

[13] B. 데이비와 H.A.프리스틀리, 격자와 질서 입문, 캠브리지 대학 출판부, 2002; "참고 지수" 참조, p. 286.

[14] Gary Hardegree, Modal Logic 입문, 2장, pg.II–2. https://web.archive.org/web/20110607061046/http ://people.umass.edu/gmhwww/511/pdf/c02.pdf

[15] The Comprehensive LaTeX Symbol List, 페이지 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf

[Hardy-16] G. H. Hardy, 수학자의 사과; Cambridge University Press, 1992 ISBN 9780521427067. PDF p.19 Wayback Machine에서 2021-02-16 보관

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[14]

[15]

[16]

Search

모순에 의한 증명

네임스페이스

더

목차

형식화

정당화

다른 증명기법과의 관계

모순반박

배제중의 법칙

모순금지법

직관적 논리의 모순에 의한 증명

모순에 의한 증명의 예

유클리드의 원소

힐베르트의 널스텔렌사츠

무한소 소수

모순에 의한 반박의 예

무한소 소수

2의 제곱근의 무리성

무한 혈통에 의한 증명

러셀의 역설

표기법

하디의 견해

참고 항목

참고문헌

추가열람 및 외부 링크