수학적 진리는 실험이 아니라 증명으로 확인한다. 증명의 방법은 몇 가지 기본 형태로 나뉘며, 문제의 모양에 따라 알맞은 방법을 고르는 것이 중요하다.
핵심 개념
- 직접증명: 가정에서 출발해 정의와 이미 아는 정리로 결론을 이끈다.
- 대우증명: $p\to q$ 대신 $\lnot q\to\lnot p$를 증명한다.
- 귀류법: 결론을 부정하고 모순을 이끌어 낸다.
- 경우 나누기: 가능한 경우를 빠짐없이 나누어 각각 증명한다.
- 반례: 전칭명제가 거짓임을 보일 때 쓴다.
- 존재증명: 직접 만들어 보이거나(구성적), 없다고 가정해 모순을 보인다(비구성적).
핵심 정리 (예시)
- $\sqrt2$는 무리수이다. (귀류법)
- 무리수 $a$, $b$ 중 $a^b$가 유리수인 것이 있다. (비구성적 존재증명)
증명 보기
$\sqrt2$는 무리수. 유리수라고 가정하고 $\sqrt2=\frac pq$ ($p,q$는 서로소인 자연수)로 쓰자. 제곱하면 $p^2=2q^2$이므로 $p^2$은 짝수이고, 따라서 $p$는 짝수이다(대우: 홀수의 제곱은 홀수). $p=2k$를 넣으면 $4k^2=2q^2$, $q^2=2k^2$이므로 $q$도 짝수이다. $p,q$가 모두 짝수이면 서로소라는 가정에 모순이다.
$a^b$가 유리수인 무리수 $a,b$. $\sqrt2^{\sqrt2}$를 생각하자. 이것이 유리수이면 $a=b=\sqrt2$가 답이다. 무리수이면 $a=\sqrt2^{\sqrt2}$, $b=\sqrt2$로 두면 $a^b=\sqrt2^{\sqrt2\cdot\sqrt2}=\sqrt2^2=2$로 유리수이다. 어느 경우든 존재한다. (실제로 어느 쪽인지는 이 증명이 알려 주지 않는다.) $\blacksquare$
예제
- 직접증명: 두 홀수의 합은 짝수 — $(2a+1)+(2b+1)=2(a+b+1)$
- 경우 나누기: $n^2+n$은 항상 짝수 — $n$이 짝수이면 $n^2$, $n$ 모두 짝수, $n$이 홀수이면 둘 다 홀수이고 합은 짝수. (또는 $n(n+1)$은 연속한 두 수의 곱)
- 귀류법: 소수의 무한성 (정수론 ‘소수’ 단원)
확인 문제
$a^2+b^2=c^2$을 만족하는 정수 $a,b,c$ 중 적어도 하나는 짝수임을 보이시오.
풀이 보기
귀류법. 모두 홀수라고 가정하면 $a^2$, $b^2$은 홀수이므로 $a^2+b^2$은 짝수이다. 그런데 $c^2$은 홀수이므로 모순이다.
정리
- 결론이 ‘아니다’, ‘무한하다’, ‘유일하다’이면 귀류법을 먼저 생각한다.
- 가정이 ‘…이 아니면’으로 쓰기 좋으면 대우를 쓴다.
