귀류법

귀류법은 많이 쓰이는 증명 방법이다. 어떤 명제가 성립함을 증명하려면 그 명제를 부정하고, 부정이 참이라고 가정한 뒤 모순을 이끌어 내려고 한다. 목표는 그 가정이 말이 안 되는 결과로 이어진다는 것을 보이는 것이다.

간단한 예

“가장 작은 양의 유리수는 없다”라는 주장을 생각하자. 이 주장을 귀류법으로 증명하려면 먼저 주장을 부정한다: “가장 작은 양의 유리수가 있다.” 이 수를 q라고 하자. q가 가장 작은 양의 유리수이면 그보다 작은 양의 유리수는 찾을 수 없다. 그런 수가 있으면 q가 가장 작은 수가 아니게 되기 때문이다.

이것을 이용해 모순을 찾는다. q를 어떻게 고르든 그보다 작은 수를 찾을 수 있다면 모순에 이르고, 부정한 명제는 성립하지 않는다. 가장 작은 수로 예를 들어 0.1을 고르면 0.01이 더 작다는 것을 알 수 있다. 0.001은 그보다 작고, 0.0001은 또 그보다 작다. 수 q를 10으로 나누기만 하면 더 작은 수를 얻는다. 사실 1보다 큰 어떤 수로 나누어도 된다. 예를 들어 2로 나누어도 q의 절반은 당연히 q보다 작다.

즉 q/2는 q보다 작은 양의 유리수이다. 이로써 부정한 주장과 모순이 생기므로, 부정한 주장은 성립하지 않고 부정하기 전의 원래 주장이 성립한다.

흥미로운 수

귀류법의 원리를 잘 보여 주는 재미있는 증명으로 다음과 같은 것이 있다. 어떤 식으로든 흥미로운 자연수가 있다고 하자. 예를 들어 2는 2 · 2 = 2 + 2가 성립하므로 흥미롭다. 꽤 드문 성질이다. 42는 모든 것에 대한 답이므로 흥미롭다. 이런 식이다. 문제는 흥미로운 수가 무한히 많으냐는 것이다.

반대로 흥미로운 수는 유한개뿐이고 흥미롭지 않은 수도 있다고 가정하자. 흥미롭지 않은 자연수를 모아 흥미롭지 않은 수의 집합을 만든다. 이제 그 가운데 가장 작은 흥미롭지 않은 수를 고른다. 잠깐, 가장 작은 흥미롭지 않은 수라고? 꽤 흥미롭게 들리지 않는가? :-)

이로써 모순에 이른다. 가장 작은 흥미롭지 않은 수는 사실 꽤 흥미로우므로, 가장 작은 흥미롭지 않은 수는 있을 수 없다. 따라서 흥미롭지 않은 수의 집합은 공집합이어야 한다.

물론 이 증명은 말이 안 된다. 흥미로운 수가 무엇인지 제대로 정의하지 않았기 때문이다. 하지만 증명의 진행 방식 자체는 올바르다.

소수가 무한히 많다는 증명

이 예에서는 앞 절과 비슷한 방법을 쓰지만, 이번에는 모든 면에서 올바른 증명이다.

소수는 서로 다른 두 수, 즉 1과 자기 자신으로만 나누어떨어지는 수이다. 이 정의에 따르면 1은 소수가 아니고 2는 소수이다.

소인수분해는 1을 제외한 자연수를 소수의 곱으로 나타내는 것이다. 자연수의 꽤 흥미로운 성질이다. 1을 제외한 어떤 자연수를 고르든 몇 개의 소수(같은 소수가 여러 번 나와도 된다)의 곱으로 나타낼 수 있다. 예를 들면 다음과 같다.

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

소인수분해에 관한 이 주장을 산술의 기본 정리라고 한다. 이 정리에 따르면 소인수분해는 하나뿐이다. 즉 한 자연수를 서로 다르게 소인수분해할 수는 없다. 또 소인수분해의 결과가 수 하나, 즉 자기 자신뿐인 수는 소수밖에 없다. 예를 들어 7을 소인수분해하면 7이다. 이 사실들을 이용해 다음 주장을 증명한다.

이제 “소수는 무한히 많다”라는 주장을 증명하자. 이번에도 주장을 부정한다: “소수는 유한개이다.” 다음 수열이 존재하는 모든 소수를 나타낸다고 가정하자.

$$a_1,a_2,a_3,\dots ,a_n$$

이 수열에 모든 소수가 들어 있다면, 소수이면서 이 수열에 없는 수는 더 이상 찾을 수 없다. 모든 소수가 수열 안에 있으므로 수열 밖에는 소수가 하나도 있으면 안 된다.

모순을 이끌어 내려면 이 수열에 없는 소수를 만들어야 한다. 이를 위해 수 q를 이용한다. 수열의 모든 소수를 곱하고 1을 더해 이 수를 만든다.

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

이제 이 수가 소수이거나, 어떻게든 새로운 소수를 낳는다는 것을 보여야 한다. q는 자연수이고, 모든 자연수는 소수의 곱으로 나타낼 수 있다. 그런데 어떤 소수 a_i도 q를 나누어떨어지게 하지 못한다. 나누면 항상 1이 남는다. 예를 들어 q를 소수 a₂로 나누어 보면 다음과 같다.

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

먼저 분수를 둘로 나눈다. 첫 번째 분수에서 a₂를 약분하면 소수의 곱이 남는데, 이는 어떤 정수일 뿐 중요하지 않다. 두 번째 분수는 약분할 것이 없고, 항상 정수가 아닌 수이다(1은 소수가 아니므로 분모가 1일 수 없다). 따라서 합은 정수가 아니고, 소수 a₂는 q를 나누어떨어지게 하지 못한다.

이것으로 수열 a_n의 어떤 소수도 q를 나누어떨어지게 하지 못한다는 것이 증명되었다. (참고: a₂에 대해서만 보였지만, a₂를 일반적인 a_i로 바꾸면 쉽게 일반화할 수 있다.) 그런데 모든 자연수는 소수의 곱으로 나타낼 수 있으므로, 수열 a_n에는 없지만 q의 소인수분해에 나타나는 다른 소수가 있어야 한다. 물론 q 자신이 소수일 수도 있고, 그때는 소인수분해에 q만 나타난다. 마지막으로 생각의 흐름을 다시 한 번 정리하자.

1. 모든 자연수는 소수의 곱으로 나타낼 수 있다.
2. 가정에 따라 수열 a_n은 존재하는 모든 소수를 포함한다.
3. 이 수열이 모든 소수를 포함하므로, 첫 번째 주장을 모든 자연수는 수열 a_n의 항 몇 개의 곱으로 나타낼 수 있다고 바꿔 말할 수 있다.
4. 수열 a_n의 어떤 수도 q를 나누어떨어지게 하지 못함을 증명했다.
5. 이로써 가정과 모순이 생긴다 → 모든 자연수를 소수의 곱으로 나타낼 수 있어야 하는데 수열 a_n에 q를 나누어떨어지게 하는 수가 없으므로, q를 나누어떨어지게 하고 q의 소인수분해에 나타나는 다른 소수가 있어야 한다.

이로써 모순에 이르렀다. q의 소인수분해에는 모든 소수를 포함한다고 가정한 수열에 없는 소수가 들어 있다. 따라서 부정한 주장은 성립하지 않고, 부정하기 전의 원래 주장이 성립한다. 소수는 무한히 많다.