직접증명, 대우와 모순

프로그램을 몇 가지 입력으로 실행해 보고 오류가 없었다고 해서, 모든 입력에서 오류가 없다고 말할 수는 없습니다. 수학의 증명도 같은 구분에서 시작합니다. 예를 여러 개 확인하는 일과, 조건을 만족하는 모든 대상에서 결론이 성립한다는 것을 보이는 일은 다릅니다. 이 글에서는 조건명제와 추론 규칙을 바탕으로, 짧은 수학적 명제를 증명하는 세 가지 방법을 익힙니다. 다 읽고 나면 가정과 정의와 결론을 구분하고, 명제에 맞는 방법을 골라 짧은 증명을 쓸 수 있습니다.

확인과 증명은 다르다

"두 홀수의 합은 짝수다"를 컴퓨터로 확인해 보겠습니다. -21부터 21까지의 홀수 22개로 만들 수 있는 모든 쌍에서 합이 짝수인지 계산합니다.

odd = range(-21, 22, 2)
print(all((a + b) % 2 == 0 for a in odd for b in odd), len(odd) ** 2)

True 484

484쌍 모두에서 참이었습니다. 하지만 홀수는 끝없이 많으므로, 확인하지 않은 쌍에서 거짓일 가능성은 이것만으로는 없앨 수 없습니다. 확인은 명제가 참일 것 같다는 짐작을 주고, 틀린 명제라면 반례를 찾아 주지만, 모든 경우에 참이라는 것은 증명으로 보여야 합니다. 알고리즘 교재에서 검사와 증명의 역할을 나눈 것과 같은 이야기입니다.

정의를 식으로 바꾸기

증명은 대개 낱말의 정의를 식으로 바꾸는 데서 시작합니다. 정수 n이 짝수라는 것은 어떤 정수 k가 있어서 $n=2k$라는 뜻이고, 홀수라는 것은 어떤 정수 k가 있어서 $n=2k+1$이라는 뜻입니다. 이 정의는 0과 음수에도 그대로 쓰입니다. $0=2\cdot0$이라 0은 짝수이고, $-3=2\cdot(-2)+1$이라 -3은 홀수입니다. "짝수"라는 낱말을 "2에 정수를 곱한 꼴"이라는 식으로 바꾸어야, 그다음에 계산을 할 수 있습니다.

직접증명: 가정에서 결론까지 이어 쓰기

가정에서 출발해 정의와 이미 아는 사실로 한 줄씩 결론까지 가는 증명을 직접증명(direct proof)이라고 합니다. "두 홀수의 합은 짝수다"를 직접증명으로 보이면 다음과 같습니다.

1. 임의의 홀수 a와 b를 잡는다. 3과 5처럼 특정한 수를 고르는 것이 아니라, 홀수라는 것 말고는 아무것도 정하지 않은 a와 b다.
2. 홀수의 정의에 따라 $a=2r+1$, $b=2s+1$인 정수 r과 s가 있다.
3. 더하면 $a+b=(2r+1)+(2s+1)=2(r+s+1)$이다.
4. $r+s+1$은 정수이므로, $a+b$는 2에 정수를 곱한 꼴이라 짝수다.

첫 줄의 "임의의"가 이 증명이 모든 홀수 쌍을 다루게 해 줍니다. 특정한 수가 아니라 아무 홀수에서나 같은 계산이 되므로, 앞에서 확인한 484쌍뿐 아니라 끝없이 많은 모든 쌍에서 결론이 성립합니다. 마지막 줄도 단순한 계산의 끝이 아니라, 계산 결과를 짝수의 정의에 맞추어 결론을 얻는 줄입니다.

흔한 실수는 증명해야 할 결론을 먼저 가정하는 것입니다. "a + b가 짝수이므로 $a+b=2k$라 하자"로 시작하면 결론을 이미 믿고 출발한 것이라 아무것도 증명하지 못합니다. 이것을 순환 논증이라고 합니다. 증명에서 새로 쓰는 사실이 가정, 정의, 이미 증명한 사실 가운데 어디서 왔는지 늘 확인해야 합니다.

대우증명: 동치인 명제를 대신 증명하기

조건명제 $P\to Q$와 그 대우 $\neg Q\to\neg P$는 논리적으로 동치이므로, 원래 명제보다 대우가 증명하기 쉽다면 대우를 대신 증명해도 됩니다. 이것을 대우증명(proof by contraposition)이라고 합니다. 역 $Q\to P$는 원래 명제와 동치가 아니므로, 역을 증명하는 것과 혼동하면 안 됩니다.

"정수 n에 대해 $n^2$이 짝수이면 n은 짝수다"를 보겠습니다. 직접증명으로 하려면 $n^2=2k$에서 출발해야 하는데, 이 식에서 n의 모양을 바로 알아내기는 어렵습니다. 대우는 "n이 홀수이면 $n^2$은 홀수다"이고, 이쪽은 n의 모양에서 출발하므로 계산이 쉽습니다. n이 홀수이면 $n=2r+1$인 정수 r이 있고, 다음 식이 성립합니다.

$2r^2+2r$이 정수이므로 $n^2$은 홀수입니다. 대우가 참이므로 원래 명제도 참입니다. 이 증명에는 모든 정수가 짝수와 홀수 가운데 정확히 하나라는 사실이 숨어 있습니다. "짝수가 아니다"를 "홀수다"로 바꾸어 쓸 수 있었던 것이 그 덕분입니다. 정수가 아닌 실수에는 이 구분이 없으므로 같은 논증을 쓸 수 없습니다.

모순증명: 결론을 부정해 모순 찾기

모순증명(proof by contradiction)에서는 증명하려는 명제가 거짓이라고 가정하고, 그 가정에서 동시에 참일 수 없는 두 사실, 곧 모순을 이끌어 냅니다. 거짓이라는 가정이 불가능하므로 명제가 참입니다. 조건명제 $P\to Q$라면 P와 $\neg Q$를 함께 가정하고 모순을 찾습니다.

수의 체계에서 무리수의 예로 든 $\sqrt2$가 정말 무리수인지 증명해 보겠습니다. $\sqrt2$가 유리수라고 가정합니다. 그러면 $\sqrt2=a/b$인 양의 정수 a와 b가 있고, 공약수를 모두 약분해 두었다고 할 수 있으므로 a와 b는 1 말고는 공약수가 없는 서로소입니다.

양변을 제곱하면 $2=a^2/b^2$, 곧 $a^2=2b^2$이므로 $a^2$은 짝수입니다. 앞에서 증명한 명제에 따라 a도 짝수이고, $a=2k$인 정수 k가 있습니다. 이것을 대입하면 $4k^2=2b^2$, 곧 $b^2=2k^2$이므로 $b^2$도 짝수이고, 같은 명제로 b도 짝수입니다. 그러면 a와 b가 모두 2로 나누어떨어지므로 서로소라는 가정과 맞지 않습니다. 이 모순은 $\sqrt2$가 유리수라는 가정에서 나왔으므로 그 가정이 거짓이고, $\sqrt2$는 무리수입니다.

이 증명은 앞에서 대우증명으로 보인 명제를 두 번이나 썼습니다. 이미 증명한 명제는 다음 증명의 도구가 됩니다. 또 $\sqrt2$의 소수 전개를 아무리 많은 자리까지 계산해도 이 결론은 얻을 수 없다는 점도 중요합니다. 무리수라는 것은 소수 전개가 되풀이되지 않는다는 것이고, 유한한 자리만 보아서는 그 뒤에 되풀이가 시작될지 알 수 없기 때문입니다.

더 깊이: 소수가 끝없이 많다는 유클리드의 증명

모순증명의 또 다른 고전은 소수가 무한히 많다는 증명입니다. 유클리드의 『원론』 9권 명제 20은 원래 소수가 몇 개 주어지든 그 밖의 소수가 있다는 꼴로 이를 보이는데, 같은 논증을 모순증명으로 옮기면 다음과 같습니다. 소수가 유한하다고 가정하고 그것을 모두 $p_1,p_2,\ldots,p_n$이라 합니다. 이들을 모두 곱한 뒤 1을 더한 $N=p_1p_2\cdots p_n+1$을 생각하면, N은 1보다 크므로 소수로 나누어떨어지는데, 어느 $p_i$로 나누어도 나머지가 1입니다. 그러면 N을 나누는 소수는 목록에 없는 소수여야 하므로, 목록이 모든 소수라는 가정과 맞지 않습니다.

이 증명을 "N 자체가 새로운 소수다"로 잘못 읽는 경우가 많습니다. 증명이 보여 준 것은 N을 나누는 소수 가운데 목록 밖의 것이 있다는 사실뿐이고, N이 소수일 필요는 없습니다. 실제로 처음 여섯 소수를 곱해 1을 더한 $2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031$은 $59\times509$로 소수가 아니지만, 59와 509는 모두 13보다 큰, 목록 밖의 소수입니다. 증명의 결론과 그 과정에서 만든 대상의 성질을 나누어 읽어야 한다는 좋은 예입니다.

세 방법을 고르는 기준

직접증명은 가정에서 결론으로 가는 길이 보일 때 가장 먼저 시도합니다. 가정보다 결론의 부정에서 출발하는 쪽이 다루기 쉬우면 대우증명을 씁니다. 앞의 예처럼 "$n^2$이 짝수"보다 "n이 홀수"가 식으로 바꾸기 쉬운 경우입니다. 결론이 "무엇이 아니다"나 "무엇은 존재하지 않는다"처럼 부정의 꼴이라 직접 다룰 거리가 없을 때는 모순증명이 잘 맞습니다. "$\sqrt2$는 유리수가 아니다"가 그런 예입니다.

대우증명과 모순증명은 비슷해 보이지만 끝나는 방식이 다릅니다. 대우증명은 $\neg Q$에서 출발해 $\neg P$에 도착하면 끝나고, 모순증명은 P와 $\neg Q$를 함께 가정해 불가능한 사실에 도착하면 끝납니다. 증명을 쓸 때는 어느 방법인지, 무엇을 가정했는지를 처음에 밝혀 두면 읽는 사람이 따라가기 쉽습니다. 증명의 출발점이 되는 가정은 공리라 하고, 공리와 이미 증명한 명제에서 증명한 명제를 정리라고 합니다. 공리는 그 체계에서 출발점으로 받아들인 가정이지, 모든 상황에서 저절로 참인 진리라는 뜻은 아닙니다.

정리

• 예를 많이 확인하는 것은 명제가 참일 것 같다는 짐작을 주지만, 모든 경우에 참임을 보이려면 증명이 필요합니다.
• 증명은 짝수를 $2k$, 홀수를 $2k+1$로 쓰듯 정의를 식으로 바꾸는 데서 시작하며, 임의의 대상을 잡아야 모든 경우를 다룰 수 있습니다.
• 직접증명은 가정에서 결론까지 한 줄씩 이어 가고, 결론을 미리 가정하는 순환 논증을 피해야 합니다.
• 대우증명은 원래 명제와 동치인 대우 $\neg Q\to\neg P$를 대신 증명하며, 역을 증명하는 것과 다릅니다.
• 모순증명은 명제가 거짓이라고 가정해 모순을 이끌어 내며, $\sqrt2$가 무리수라는 것이 대표적인 예입니다.

연습 문제

1. 짝수와 홀수의 합

짝수와 홀수를 더하면 홀수임을 직접증명하세요.

2. 제곱이 홀수이면

정수 n에 대해 "$n^2$이 홀수이면 n은 홀수다"를 대우증명하세요. 이 명제의 역도 참인가요?

3. 경우를 나누는 증명

모든 정수 n에 대해 $n^2+n$이 짝수임을 증명하세요.

증명을 쓸 때마다 어떤 대상에 대한 명제인지, 무엇을 가정했는지, 어느 정의로 마무리했는지를 표시해 보세요. 논증의 방향이 헷갈리면 추론 규칙으로 돌아가면 됩니다. 다음 글 존재증명과 반례에서는 예 하나로 충분한 명제와 모든 경우를 다뤄야 하는 명제를 구분합니다.