[해석학] 증명과정에서 귀류법이 작동되는 원리

수학에서 크게 세가지 증명 방법이 존재한다.

첫째, Mathematical induction, 즉 수학적 귀납법

둘째, Deductive proof, 즉 연역적 증명법

셋째, Proof by contradiction, 즉 귀류법이다.

​

오늘 말하고자 하는건 귀류법이다

귀류법이란, p -> q 를 증명하기 위해서

p ∩~q →~p​

임을 보이는 것이다. (~은 부정이란 의미이다.) 위 관계만 봐서는 좀 난해해 보이지만 아래의 p와 q간의 모든 관계를 표현한 네가지 벤다이어그램에서 위 관계를 만족하는 벤다이어그램 관계는 (4)밖에 없음을 확인할 수 있다. 즉, (4)는 q가 p를 포함하는 관계로, p->q 가 성립한다.

​

​

즉, 정리하면 귀류법이란 p -> q 를 보이기 위해

p ∩~q →~p​

임을 보이는 방법이다. (어쩌면 Dual Problem 같기도 하다.)

​

​

즉 p와 ~q를 같이 가정하였을 때, 그 상황하에서 절대 p가 성립할 수 없음을 보이는 것이다. (즉, p와 ~q 가 성립하는 상황하에서는 p의 부정이 성립함을 보인다.)

이는 한편, 우리가 p를 가정하여 얻은 결과인데 p가 성립할 수 없다고 하니 모순이기도 하다.

즉, 이러한 모순의 원흉이 p와 ~q를 같이 가정하였기 때문이니, p일때는 ~q가 발생할 수 없음을 은연중에 암시하기도 한다.

​

귀류법은 간단한 방법이지만, 생각보다 복잡한 문제를 증명할 때 많이 쓰인다.

​

예제)

두개의 실수 x, y가 있다고 할 때,

x < y+e for all e>0 then, x <= y.

​

proof)

x < y+e for all e>0 이며, x>y 라고 하자. (p와 ~q를 가정)

그러면,

e0 = x-y >0 이 존재한다.

그러면 y + e0 = y + (x-y) = x 이다.

그러므로, Trichotomy Property(두 실수 a,b는 a=b or a>b or a<b 중 하나의 관계에 있다.) 에 의해

y + e0 는 x보다 클수 없다. 따라서 이는 x < y+e for all e>0 라는 가정을 위배한다.(모순)

(즉, p이면서 ~q인 상황하에서는 p가 성립할 수 없음을 보였다.)

​

따라서 x < y+e for all e>0 then, x <= y 는 참이다.