3강. 증명 방법

증명은 참이라고 받아들인 것(정의, 공리, 이미 증명한 정리)에서 출발해 논리 규칙만으로 결론에 이르는 글입니다. 2강의 조건문과 한정기호가 증명의 문법이라면, 이 강은 자주 쓰는 증명의 틀을 다룹니다. 선형대수 1장 “증명하는 법”과 내용이 겹치지만, 여기서는 정수에 관한 예로 연습합니다.

3.1 정의를 먼저 적는다

정의 3.1 (짝수, 홀수). 정수 $n$이 어떤 정수 $k$에 대해 $n = 2k$이면 짝수, $n = 2k + 1$이면 홀수입니다.

정의 3.2 (나누어떨어짐). 정수 $a \ne 0$, $b$에 대해 $b = ak$인 정수 $k$가 있으면 “$a$가 $b$를 나눈다”고 하고 $a \mid b$로 씁니다.

증명의 첫 줄은 대개 가정을 정의로 풀어 쓰는 것입니다. “$n$이 짝수”라고 쓰고 멈추지 말고 “$n = 2k$인 정수 $k$가 있다”까지 씁니다.

3.2 직접 증명

$p \to q$를 보이려면 $p$를 가정하고 $q$를 끌어냅니다.

정리 3.3. 두 홀수의 곱은 홀수입니다.

증명. $m = 2a + 1$, $n = 2b + 1$이라 합시다. 그러면

이고 $2ab + a + b$는 정수이므로 $mn$은 홀수입니다. □

정리 3.4 (나누어떨어짐의 추이성). $a \mid b$이고 $b \mid c$이면 $a \mid c$입니다.

증명. $b = ak$, $c = bl$이면 $c = a(kl)$이고 $kl$은 정수입니다. □

3.3 대우 증명

$p \to q$와 대우 $\neg q \to \neg p$는 동치(1강)이므로, 대우를 증명해도 됩니다. 결론의 부정이 다루기 쉬울 때 씁니다.

정리 3.5. $n^2$이 짝수이면 $n$은 짝수입니다.

증명. 대우 “$n$이 홀수이면 $n^2$은 홀수”를 보입니다. 이는 정리 3.3에서 $m = n$으로 둔 경우입니다. □

직접 증명하려 하면 “$n^2 = 2k$이면 $n = \sqrt{2k}$”처럼 정수 밖으로 나가게 되어 막힙니다.

3.4 귀류법

$q$를 보이려면 $\neg q$를 가정하고 모순(어떤 $r$과 $\neg r$이 동시에 참)을 끌어냅니다.

정리 3.6. $\sqrt{2}$는 무리수입니다.

증명. $\sqrt{2}$가 유리수라고 가정하고, 기약분수 $\sqrt{2} = a/b$($a, b$는 공약수 1뿐인 정수, $b \ne 0$)로 씁시다. 양변을 제곱하면 $a^2 = 2b^2$이므로 $a^2$은 짝수이고, 정리 3.5에 따라 $a$도 짝수입니다. $a = 2c$를 넣으면 $4c^2 = 2b^2$, 곧 $b^2 = 2c^2$이므로 $b$도 짝수입니다. 그러면 $a$와 $b$가 공약수 2를 가져 기약분수라는 가정과 모순입니다. □

정리 3.7 (유클리드). 소수는 무한히 많습니다.

증명. 소수가 유한개 $p_1, \dots, p_n$뿐이라고 가정합시다. $N = p_1 p_2 \cdots p_n + 1$은 1보다 크므로 어떤 소수 $p$로 나누어떨어집니다. $p$는 $p_1, \dots, p_n$ 가운데 하나여야 하지만, $N$을 어느 $p_i$로 나눠도 나머지가 1이므로 모순입니다. □

3.5 경우 나누기

가정이 몇 가지 경우로 나뉘면 각 경우를 따로 증명합니다. 모든 경우를 빠짐없이 다뤘는지 확인하는 것이 중요합니다.

정리 3.8. 모든 정수 $n$에 대해 $n^2 + n$은 짝수입니다.

증명. $n$이 짝수이면 $n = 2k$이고 $n^2 + n = 2(2k^2 + k)$입니다. $n$이 홀수이면 $n = 2k + 1$이고 $n^2 + n = (2k+1)(2k+2) = 2(2k+1)(k+1)$입니다. 어느 경우든 짝수입니다. □

(짧게는 $n^2 + n = n(n+1)$이 연속한 두 정수의 곱이라 하나는 짝수라고 해도 됩니다.)

3.6 존재 증명과 반례

$\exists x\, P(x)$는 그런 $x$를 하나 보이면 됩니다(구성적 증명). $\forall x\, P(x)$가 거짓임을 보이려면 $P(x)$가 거짓인 $x$ 하나, 곧 반례(counterexample)를 보이면 됩니다.

예제 3.9. “모든 소수는 홀수”는 반례 $2$로 거짓입니다. “$n^2 + n + 41$은 모든 자연수 $n$에서 소수”는 $n = 0$부터 $39$까지 참이지만 $n = 40$에서 $40^2 + 40 + 41 = 41^2$이므로 거짓입니다. 예를 많이 확인해도 증명이 되지 않는다는 좋은 예입니다.

3.7 필요충분조건

$p \leftrightarrow q$(“$p$일 필요충분조건은 $q$”)는 $p \to q$와 $q \to p$를 따로 증명합니다.

정리 3.10. 정수 $n$에 대해, $n$이 짝수일 필요충분조건은 $n^2$이 짝수인 것입니다.

증명. ($\Rightarrow$) $n = 2k$이면 $n^2 = 2(2k^2)$입니다. ($\Leftarrow$) 정리 3.5입니다. □

쓰이는 곳. 논문의 Theorem–Proof 부분, 알고리즘의 정확성 증명, 머신러닝 이론의 일반화 상한이 이 강의 방법(직접, 대우, 귀류법, 경우 나누기)으로 쓰입니다.

3.8 이 장의 요약

문제

2

40

1,2,4

2311