맛있는 증명 4번째 칼럼, 귀류법(간접 증명법)

시작하겠습니다.

저번 시간에는 직접 증명법을 익혀보았다. 

하지만 직접 증명법 이외에도 간접 증명법이 존재한다.

대표적으로 귀류법, 대우법, 존재 증명법, 반례 증명법이 존재한다.

이 중 귀류법 이외는 직관적이므로, 여기서 간단히 설명하고

여기서는 귀류법을 자세히 다루려고 한다.

귀류법은 어떤 명제 p→q 이 이분법적인 명제일 때

이 명제의 결론을 부정하여 반례가 존재한다고 가정한 후

이에 대해 모순이 있음을 보여주는 것으로 원 명제가 참임을 보여주는 것이다.

중요한 부분 1. 증명하고자 하는 명제는 이분법적이어야 한다.

즉 결론이 

~이 존재한다/존재하지 않는다 

실수 ~는 유리수이다/무리수이다

등으로 이분법적이어야 한다는 의미이다.

중요한 부분 2. p→q 의 부정은 p 그리고 ~q 이다.

즉 반례가 존재한다고 가정하는 것은 p 그리고 ~q를 만족하는 원소가 존재한다고 가정하는 것이다.

예를 들어 “자연수 n에 대하여 n^2이 짝수이면 n이 짝수이다.” 라는 명제를 귀류법으로 증명하려고 하면

우리가 모순을 보여야 하는 가정은 “n^2이 짝수이고 n이 홀수인 자연수 n이 존재한다.” 이다.

저 가정은 원 명제의 반례를 억지로 만든 것이다. 

원 명제가 참이므로 원래는 반례가 존재할 리가 없다.

하지만 우리가 없는 반례를 억지로 만들었으니, 

모순이 발생하는 것은 당연한 이치이다.

그 모순을 찾아 ‘너가 찾던 그 반례는 오류투성이’임을 보여주는 것이 귀류법의 핵심이다.

만약 p이면 q이다에서 ‘p이면’이 생략된 경우,

예를 들어 “√2가 무리수이다.” 같은 명제인 경우

단순히 결론을 부정하여 “√2가 유리수라고 가정하자.” 라고 쓰면 된다.

중요한 부분 3. 모순은 꼭 가정과 관련되지 않을 수 있다.

귀류법을 쓰면서 발생하는 실수가 “이는 가정과 모순이므로” 라는 문구이다.

귀류법의 핵심은 모순이 존재함을 보이는 것이지, 그 모순이 가정과 관련될 필요는 없다.

그래서 그냥 “이는 모순이므로” 라고 쓰는 것으로 충분하다.

귀류법의 개요는 다음과 같다.

1. 결론 부정

2. 모순 찾기

3. 결론

1. 결론 부정

결론 부정 단계에서는 “결론을 부정하여” 라는 문구를 쓰며 읽는 사람에게 귀류법을 사용하려는 것을 피력하자.

예를 들어 “결론을 부정하여 √2가 유리수리고 가정하자.” 와 같이 쓰면 된다.

2. 모순 찾기

모순이 존재함을 밝히는 작업이다.

모순을 발견했으면, 마무리는 “~이므로, 이는 모순이다.” 로 끝내면 된다.

3. 결론

결론은 원 명제를 다시 한 번 쓰면 된다.

예를 들면, “따라서 √2는 무리수이다.” 정도면 된다.

귀류법의 대표적인 증명은 √2가 무리수임을 증명하는 것이 아닐까 싶다.

그래서 필자도 여기서는 √2가 무리수임을 증명하려고 한다.

그런데 기존의 √2가 무리수임을 증명하는 것에 무언가 이상한 점이 있지 않는가?

왜 √2= p/q 인 두 정수 p, q가 서로소여야 하는가? 

유리수의 정의에는 두 정수가 서로소라고 명시하지 않았다.

서로소라고 가정하지 않고도 무리수라고 증명할 수는 없는가?

결론부터 말하자면, 서로소라고 가정하지 않고도 √2가 무리수임을 증명할 수 있다.

그렇기 위해서는 다음 공리를 받아드려야 한다.

정렬 원리 (Well ordering property)

공집합이 아닌 자연수의 부분집합 S는 최소원소 s 가 존재한다.

무슨 이야기냐? 예시를 들어보자.

S={1,3,5,7,9}이면, S의 최소원소는 1이다.

S가 소수 전체의 집합이라면, 소수의 최소원소는 2이다.

S가 홀수 전체의 집합이면, 홀수의 최소원소는 1이다.

당연한 말이다. 당신이 어떠한 자연수의 부분집합을 고르든, 항상 최소원소가 존재할 것이다.

이를 공리로 받아드리자. 

공리란, 자명하므로 참으로 받아드리는 명제이다.

이제 정렬 원리를 이용하여 √2가 무리수임을 증명하자.

어려울 수 있다. 워낙 생소한 증명이므로, 

천천히 씹어먹자.

만약 증명이 이해가 되지 않는다면

√3이 무리수임을 해당 증명을 참고하여 똑같이 증명해 보자.

그러면 이 증명이 이해가 갈 것이다.

더 쉬운 예시는. 앞선 칼럼에서도 보여주었던 다음 문제의 증명이다.

어떤가? 이 정도면 귀류법에 대한 감이 잡혔을 것이라 생각한다.

마지막으로 귀류법 외에도 다른 간접 증명법을 언급하며 칼럼을 마치겠다.

<기타 간접 증명법>

먼저 대우법, p→q 라는 명제 대신 이의 대우 명제 ~q→~p 라는 명제를 증명하는 것이다.

원 명제와 대우명제는 둘 다 참이거나 둘 다 거짓이어야 하므로,

대우 명제를 증명하는 것으로도 원 명제를 증명할 수 있다.

예를 들면 “자연수 n에 대하여 n^2이 짝수이면 n이 짝수이다.” 라는 명제를

이의 대우 명제인 “자연수 n에 대하여 n이 홀수이면 n^2이 홀수이다.” 라는 명제로 바꿔

이를 대신 증명하는 것이다.

존재 증명법, 어떤 명제를 만족시키는 원소가 존재함을 보여줌으로써 어떤 명제가 참임을 밝히는 것이다.

간단히 말하자면 “여기 이 원소 있죠? 증명 끝!” 이다. 

예를 들어 “피타고라스 정리 a^2 + b^2 = c^2를 만족하는 세 정수 a, b, c가 존재함을 밝히시오.”

라는 명제를 증명하려면,

단순히 “a=3, b=4, c=5가 존재한다.” 라고 말하면서 증명을 끝내면 된다.

반례 증명법은 반대로, 어떤 명제의 반례가 존재함을 밝히면서 그 명제가 거짓임을 증명하는 것이다.

간단히 말하자면 “그 명제 반례 있는데요? 증명 끝!” 이다.

예시로는 오일러의 추측이 있을 것이다.

실제 오일러의 추측은 약간 더 복잡하니, 예시는 간단히 들겠다.

이 추측이 거짓임은 다음 한 줄이면 충분하다.

이번 칼럼의 요약은 다음과 같다.

1. 결론 부정


2. 모순 찾기


3. 결론

오늘의 칼럼은 여기까지이다. 

다음 칼럼에서는 수학적 귀납법을 다룰 예정이다.

많은 관심 바란다.

이만.