귀류법

3. 수학에서의 귀류법

수학에서 '''귀류법''' 또는 '''배리법'''은 증명하려는 명제의 결론을 부정한 뒤, 이것이 모순된 가정을 낳는다는 것을 보여 원래 명제가 참임을 증명하는 방법이다. 이 방법은 유클리드가 약 2000년 전 소수가 무한히 많다는 것을 증명하기 위해 사용했을 정도로 역사가 깊다.

예를 들어, $\backslash sqrt\{2\}$가 유리수가 아니라는 사실은 귀류법을 사용하여 증명할 수 있다. (자세한 증명 과정은 하위 섹션 참조)

고전 논리에서 귀류법의 타당성은 명제 ''¬¬P ⇒ P''의 진리표를 통해 확인할 수 있다. 이 진리표는 해당 명제가 항상 참인 항진 명제임을 보여준다.

귀류법은 배중률로부터 유도될 수도 있다. ''¬¬P''를 가정하고 ''P''를 증명하고자 할 때, 배중률에 따라 ''P''는 성립하거나 성립하지 않는다.

# 만약 ''P''가 성립하면 증명이 끝난다.

# 만약 ''¬P''가 성립하면, 모순율을 ''¬P''와 ''¬¬P''에 적용하여 거짓을 유도하고, 폭발 원리를 사용하여 ''P''를 결론 내릴 수 있다.

어떤 경우든 ''P''가 성립함을 보일 수 있다. 반대로 귀류법을 사용하여 배중률을 유도하는 것도 가능하다.

고전 시퀀트 계산 LK에서는 귀류법이 부정에 대한 추론 규칙으로부터 파생될 수 있다.

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

귀류법의 초기 사례 중 하나는 유클리드 기하학 제1권 명제 6에서 찾아볼 수 있다.^[7]

삼각형에서 두 각이 서로 같으면, 같은 각에 마주보는 변의 길이도 서로 같다.

만약 $f\_1,\backslash ldots,f\_k$가 n개의 변수를 갖는, 복소수 계수를 가진 다항식이고 공통된 복소수 영점을 갖지 않는다면, $f\_1g\_1+\backslash ldots\; +f\_kg\_k=1.$을 만족하는 다항식 $g\_1,\backslash ldots,\; g\_k$가 존재한다.

소수는 주어진 어떤 소수의 집합보다 더 많다.

3. 1. √2가 무리수임을 증명 (예시)

3. 2. 소수의 무한성 증명 (예시)

소수는 주어진 어떤 소수 무리보다 더 많다.

4. 논리적 형식화

귀류법의 원리는 명제 공식 ''¬¬P ⇒ P''로 형식화될 수 있다. 이는 ''(¬P ⇒ ⊥) ⇒ P''와 동등하며, "만약 ''P''가 거짓이라고 가정했을 때 모순(⊥)이 발생한다면, ''P''는 참이다"라고 해석할 수 있다.

자연 연역에서는 이 원리가 다음과 같은 추론 규칙으로 나타난다.

: $\backslash cfrac\{\backslash vdash\; \backslash lnot\; \backslash lnot\; P\}\{\backslash vdash\; P\}$

이는 "만약 $\backslash lnot\backslash lnot\; P$가 증명되면, $P$를 결론으로 도출할 수 있다"는 의미이다.

시퀀트 계산에서는 이 원리를 다음과 같은 시퀀트로 표현한다.

: $\backslash Gamma,\; \backslash lnot\backslash lnot\; P\; \backslash vdash\; P,\; \backslash Delta$

이는 "가설 $\backslash Gamma$와 $\backslash lnot\backslash lnot\; P$는 결론 $P$ 또는 $\backslash Delta$를 함의한다"는 의미이다.

고전 논리에서 이 원리는 명제 ''¬¬P ⇒ P''의 진리표를 통해 정당화될 수 있으며, 이 진리표는 해당 명제가 항진명제임을 보여준다.

고전 시퀀트 계산 LK에서는 귀류법이 부정에 대한 추론 규칙으로부터 다음과 같이 파생될 수 있다.

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

4. 1. 다른 증명 기법과의 관계

5. 직관주의 논리에서의 귀류법

귀류법은 일반적으로 직관 논리에서는 유효하지 않다. 하지만 부정의 증명이나 모순율은 직관 논리에서도 유효한 원리로 받아들여진다.

직관 논리에서 귀류법이 문제가 되는 이유 중 하나는 알고리즘적 해석과 관련이 있다. 만약 모든 명제에 대해 귀류법이 성립한다고 가정하면, 해결 불가능하다고 증명된 정지 문제를 해결할 수 있다는 모순이 발생할 수 있다. 예를 들어, 특정 튜링 기계 ''M''이 정지하는지에 대한 명제 ''H(M)''을 생각해보자. ''M''이 정지하지 않는다는 명제의 부정, 즉 "''M''은 정지하지도 않고 정지하지 않는 것도 아니다"는 모순율에 따라 항상 거짓이다. 만약 귀류법이 보편적으로 유효하다면, 이를 이용해 임의의 튜링 기계 ''M''이 정지하는지 여부를 판별하는 알고리즘을 만들 수 있게 되는데, 이는 정지 문제가 해결 불가능하다는 사실과 충돌한다.

직관 논리에서는 $\backslash lnot\backslash lnot\; P\; \backslash Rightarrow\; P$ (P가 아니지 않으면 P이다)를 만족하는 명제 ''P''를 '¬¬-안정 명제'라고 부른다. 귀류법은 이러한 ¬¬-안정 명제에 대해서만 제한적으로 적용될 수 있다.

¬¬-안정 명제의 대표적인 예시는 결정 가능한 명제이다. 결정 가능한 명제란 $P\; \backslash lor\; \backslash lnot\; P$ (P이거나 P가 아니다)가 성립하는 명제를 말한다. 배중률이 귀류법을 함축한다는 증명 과정을 살펴보면, 결정 가능한 명제가 ¬¬-안정 명제임을 알 수 있다. 직접적인 계산이나 확인을 통해 참 또는 거짓을 명확히 알 수 있는 명제들이 결정 가능한 명제에 해당한다. 예를 들어, "$n$은 소수이다" 또는 "$a$는 $b$를 나눈다"와 같은 명제는 결정 가능한 명제의 예시이다.

6. 자동 정리 증명

자동 정리 증명에서 해법은 귀류법에 기반한다. 즉, 주어진 명제가 주어진 가설에 의해 함의됨을 보이기 위해, 자동 증명기는 가설과 명제의 부정을 가정하고 모순을 유도하려고 시도한다.^[17]

7. 한국의 관점

귀류법은 한국의 수학 교육 과정에서도 중요하게 다루어지는 증명 방법 중 하나이다. 특히, √2가 무리수임을 증명하는 예시는 중학교 및 고등학교 수학에서 논리적 사고의 예시로 자주 활용된다. 해당 증명 과정은 다음과 같다.

# $\backslash sqrt\{2\}$가 유리수라고 가정한다. 따라서 $\backslash sqrt\{2\}\; =\; \backslash frac\{b\}\{a\}$으로 둘 수 있다. (이때 $a,\; b$는 서로소인 자연수이다.)

# 양변을 제곱하여 정리하면 $2a^\{2\}\; =\; b^\{2\}$이므로 $b^\{2\}$는 2의 배수이다. 제곱수가 2의 배수이면 원래의 수도 2의 배수이므로, $b$도 2의 배수이다. 따라서 $b=2k$ (여기서 $k$는 자연수)로 둘 수 있다.

# 이를 $2a^\{2\}\; =\; b^\{2\}$에 대입하면 $2a^\{2\}\; =\; (2k)^\{2\}\; =\; 4k^\{2\}$이 되고, 양변을 2로 나누면 $a^\{2\}=2k^\{2\}$이다. 따라서 $a^\{2\}$도 2의 배수이고, 같은 원리로 $a$도 2의 배수이다.

# 이는 $a$와 $b$가 모두 2의 배수라는 결론으로 이어지는데, 이는 처음에 $a,\; b$가 서로소라고 가정한 것에 모순된다.

# 따라서 최초의 가정 "$\backslash sqrt\{2\}$가 유리수이다"는 거짓이며, 결론적으로 $\backslash sqrt\{2\}$는 유리수가 아니다(즉, 무리수이다).

참조

_[1] 서적 Foundations of Constructive Analysis Academic Press 1967
_[2] 웹사이트 Proof By Contradiction https://www2.edc.org[...] 2023-06-12
_[3] 웹사이트 Reductio ad absurdum {{!}} logic https://www.britanni[...] 2019-10-25
_[4] 웹사이트 Proof by contradiction https://ncatlab.org/[...] 2022-10-07
_[5] 서적 Book of Proof https://www.people.v[...] 2022
_[6] 웹사이트 Proof of negation and proof by contradiction http://math.andrej.c[...] 2021-10-26
_[7] 웹사이트 Euclid's Elements, Book 6, Proposition 1 https://mathcs.clark[...] 2022-10-02
_[8] 간행물 Ueber die vollen Invariantensysteme https://resolver.sub[...] 1893
_[9] 웹사이트 Euclid's Elements, Book 9, Proposition 20 https://mathcs.clark[...] 2022-10-02
_[10] 간행물 Five stages of accepting constructive mathematics 2017
_[11] 웹사이트 Why is the square root of 2 irrational? http://www.math.utah[...] Department of Mathematics, University of Utah 2013-02-06
_[12] 웹사이트 Math Forum Discussions http://mathforum.org[...]
_[13] 서적 Introduction to Lattices and Order Cambridge University Press 2002
_[14] 문서 Introduction to Modal Logic https://web.archive.[...]
_[15] 문서 The Comprehensive LaTeX Symbol List http://www.ctan.org/[...]
_[16] 서적 A Mathematician's Apology https://www.math.ual[...] Cambridge University Press 1992
_[17] Citation Linear Resolution http://dx.doi.org/10[...] The MIT Press 2023-12-21
_[18] 웹인용 Reductio ad absurdum http://www.utm.edu/r[...] 2011-01-25
_[19] 뉴스 귀류법에 관하여 http://www.kyeongin.[...] 경인일보 2010-01-24
_[20] 뉴스 2015 수시 논술중심전형 수리논술 대비 방안 http://www.veritas-a[...] 베리타스알파 2014-09-15
_[21] 뉴스 ‘수열’ 파트 증명 문제 어떻게 https://news.naver.c[...] 세계일보 2014-07-27