증명 기법

개요 — 동기·문제의식

명제논리과 술어와 한정기호에서 수학적 명제를 정확하게 적는 언어를 갖추었다. 남은 문제는 그렇게 적힌 명제가 참임을 어떻게 확정하느냐이다. 증명(proof)은 공리·정의·이미 확립된 정리로부터 유효한 추론 규칙만으로 결론에 도달하는 유한한 논증이며, 수학에서 참을 확정하는 유일한 수단이다. 아무리 많은 사례를 확인해도 전칭 명제는 확정되지 않는다 — $n^2+n+41$은 $n=0,1,\dots,39$에서 모두 소수이지만 $n=40$에서는 $41^2$이 되어 무너진다.

이 장은 이산수학 전체에서 반복해서 쓰이는 표준 증명 전략을 정리한다. 조건문 $p\to q$를 공략하는 세 갈래 길(직접·대우·귀류), 전제를 쪼개는 경우 나누기, 존재 명제를 다루는 두 방식(구성적·비구성적), 그리고 자연수 전체에 대한 무한히 많은 명제를 두 단계 논증으로 처리하는 수학적 귀납법이 그것이다. 이후의 모든 장 — 집합과 함수의 집합 등식, 점화식의 점화식 해의 검증, 그래프와 트리의 트리 정리 — 이 여기서 세우는 틀 위에서 증명된다.

직관

증명 전략의 선택은 "결론까지 가는 길이 어느 방향에서 잘 보이는가"의 문제다. 직접증명은 전제에서 결론으로 정면으로 걸어가는 길이고, 대우증명은 같은 다리를 반대편에서 건너는 길이다 — 명제논리에서 본 대로 $p\to q$와 $\neg q\to\neg p$는 논리적 동치이므로 어느 쪽으로 건너든 같은 정리가 증명된다. "$n^2$이 짝수이면 $n$이 짝수"처럼 전제($n^2$이 짝수)에서 출발하기는 불편하지만 결론의 부정($n$이 홀수)에서 출발하기는 쉬울 때 대우가 위력을 발휘한다.

귀류법은 더 급진적이다. 증명하려는 명제가 거짓인 세계를 통째로 가정하고, 그 세계 안에서 모순이 터질 때까지 논리를 밀어붙인다. 모순이 나오면 그런 세계는 존재할 수 없으므로 원래 명제가 참이다. 한편 수학적 귀납법은 도미노 그림 하나로 요약된다 — 첫 도미노가 넘어지고(기초 단계), 각 도미노가 다음 도미노를 반드시 넘어뜨린다면(귀납 단계), 모든 도미노가 넘어진다. 무한히 많은 명제 $P(1),P(2),P(3),\dots$를 유한한 두 단계로 한꺼번에 처리하는 장치다. 강한 귀납법은 "바로 앞 도미노"가 아니라 "지금까지 넘어진 모든 도미노"의 힘을 빌리는 변형이며, 아래에서 보듯 정렬 원리와 같은 내용의 다른 표현이다.

정의

조건문의 세 가지 증명 경로

정의. 조건문 $p\to q$에 대하여 다음은 모두 유효한 증명 전략이다.

• 직접증명(direct proof): $p$를 가정하고 정의·공리·기존 정리를 연쇄 적용하여 $q$를 유도한다.
• 대우증명(proof by contraposition): 논리적 동치인 $\neg q\to\neg p$를 직접증명한다.
• 귀류법(proof by contradiction): 명제 $r$의 부정 $\neg r$을 가정하고 모순($s\wedge\neg s$ 꼴)을 유도한다. $r$이 $p\to q$ 꼴이면 $p\wedge\neg q$를 가정한다. 부정을 세울 때는 술어와 한정기호의 부정 규칙을 정확히 적용해야 한다.

경우 나누기와 존재 증명

정의. 경우 나누기(proof by cases): 전제가 $p_1\vee p_2\vee\cdots\vee p_n$으로 분해될 때, 동치 $(p_1\vee\cdots\vee p_n)\to q \equiv (p_1\to q)\wedge\cdots\wedge(p_n\to q)$에 따라 각 경우 $p_i\to q$를 따로 증명한다. 경우들이 전체를 빠짐없이 덮는지(exhaustive) 반드시 확인해야 한다.

정의. 존재 명제 $\exists x\,P(x)$의 증명은 두 방식으로 나뉜다. 구성적 존재 증명(constructive): $P(a)$가 성립하는 대상 $a$를 명시적으로 제시하거나 만드는 절차를 준다. 비구성적 존재 증명(nonconstructive): 대상을 제시하지 않은 채 존재만을 보인다 — 전형적으로 "존재하지 않는다"를 가정해 모순을 끌어내거나, 어느 쪽인지 모르는 경우 나누기로 존재를 강제한다. 셈의 기본 원리의 비둘기집 원리와 확률적 방법가 비구성적 논법의 대표적 엔진이다.

수학적 귀납법·강한 귀납법·정렬 원리

정의. 수학적 귀납법(mathematical induction): 자연수에 대한 술어 $P(n)$에 대해 다음 추론 규칙이 유효하다.

$$\big[\,P(1)\ \wedge\ \forall k\,(P(k)\to P(k+1))\,\big]\ \to\ \forall n\ge 1\,P(n)$$

$P(1)$의 증명을 기초 단계(basis step), 임의의 $k$에 대해 가정 $P(k)$(귀납 가정)로부터 $P(k+1)$을 유도하는 것을 귀납 단계(inductive step)라 한다. 시작점은 $1$이 아니어도 되며, $P(b)$에서 시작하면 결론은 $\forall n\ge b\,P(n)$이다.

정의. 강한 귀납법(strong induction): 귀납 단계의 가정을 $P(k)$ 하나가 아니라 $P(b),\dots,P(k)$ 전부로 바꾼 형태. 즉 "$b\le j\le k$인 모든 $j$에 대해 $P(j)$"로부터 $P(k+1)$을 유도한다. 정렬 원리(well-ordering principle): 자연수의 공집합이 아닌 모든 부분집합은 최소원을 갖는다. 아래 정리 7이 보이듯 이 셋(귀납법·강한 귀납법·정렬 원리)은 서로 동치인 공리적 원리다.

주요 정리

정리 1 (직접증명의 원형). $n$이 홀수이면 $n^2$은 홀수이다.

정리 2 (대우증명의 원형). 정수 $n$에 대해 $n^2$이 짝수이면 $n$은 짝수이다.

정리 3 ($\sqrt2$는 무리수 — 귀류법). $\sqrt2$는 유리수가 아니다.

정리 4 (소수의 무한성 — 유클리드). 소수는 무한히 많다.

정리 5 (합 공식 — 귀납법). 모든 정수 $n\ge1$에 대해 $1+2+\cdots+n=\dfrac{n(n+1)}{2}$이다.

정리 6 (부등식 — 시작점이 밀린 귀납법). 모든 정수 $n\ge4$에 대해 $2^n<n!$이다.

정리 7 (강한 귀납법과 정렬 원리의 동치). 자연수에 대해 정렬 원리와 강한 귀납법은 서로를 함의한다.

예제

예제 1 (경우 나누기). 모든 정수 $n$에 대해 $n^2\equiv0$ 또는 $1\pmod4$이다. 경우 1: $n=2k$이면 $n^2=4k^2\equiv0$. 경우 2: $n=2k+1$이면 $n^2=4(k^2+k)+1\equiv1$. 두 경우가 정수 전체를 덮으므로 증명이 끝난다. 따름: $x^2+y^2=4m+3$ 꼴의 정수해는 없다(두 제곱의 합은 mod 4로 $0,1,2$만 가능).

예제 2 (대우가 자연스러운 경우). "$3n+2$가 홀수이면 $n$은 홀수"를 보이려면 대우 "$n$이 짝수이면 $3n+2$는 짝수"를 취한다. $n=2k$이면 $3n+2=6k+2=2(3k+1)$로 즉시 끝난다. 원 방향의 직접증명은 $3n+2=2j+1$에서 $n=(2j-1)/3$을 다뤄야 해 번거롭다.

예제 3 (구성적 존재 증명). 임의의 $n\ge1$에 대해 연속한 $n$개의 합성수가 존재한다. 실제로 $(n+1)!+2,\ (n+1)!+3,\ \dots,\ (n+1)!+(n+1)$을 제시하면 된다 — $2\le i\le n+1$일 때 $i\mid(n+1)!$이므로 $i\mid(n+1)!+i$이고 $(n+1)!+i>i$이므로 각 수는 합성수다. 대상을 명시적 공식으로 내놓는 것이 구성적 증명의 특징이다.

예제 4 (비구성적 존재 증명). $x^y$가 유리수가 되는 무리수 $x,y$가 존재한다. $t=\sqrt2^{\sqrt2}$를 보자. 경우 1: $t$가 유리수이면 $x=y=\sqrt2$가 답이다. 경우 2: $t$가 무리수이면 $x=t,\ y=\sqrt2$에 대해 $x^y=\sqrt2^{\sqrt2\cdot\sqrt2}=\sqrt2^2=2$가 유리수이므로 답이다. 어느 경우가 실제로 성립하는지 몰라도 존재는 확정된다 — 증인을 제시하지 못하는 전형적 비구성 논법이다.

예제 5 (강한 귀납법). 모든 정수 $n\ge2$는 소수들의 곱이다(한 개의 곱 포함). 강한 귀납법: $2\le j\le k$인 모든 $j$가 소수들의 곱이라 가정하고 $n=k+1$을 보자. $n$이 소수이면 자명하다. 합성수이면 $n=ab$ ($2\le a,b\le k$)로 쓸 수 있고, 귀납 가정에 의해 $a,b$ 각각이 소수들의 곱이므로 $n$도 그렇다. 보통 귀납법으로는 $P(k)$만으로 $P(k+1)$을 말할 수 없다 — $k+1$의 약수는 $k$가 아니라 훨씬 작은 수이기 때문이며, 이것이 강한 귀납법이 필요한 전형적 상황이다.

예제 6 (강한 귀납법 — 우표 문제). $4$센트와 $5$센트 우표만으로 $12$센트 이상의 모든 우편요금을 만들 수 있다. 기초 단계로 $12=4+4+4$, $13=4+4+5$, $14=4+5+5$, $15=5+5+5$를 직접 확인한다. 귀납 단계: $n\ge15$이고 $12\le j\le n$인 모든 $j$가 가능하다고 하자. $n+1\ge16$에 대해 $n+1-4=n-3\ge12$이므로 귀납 가정으로 $n-3$을 만들고 $4$센트 우표 한 장을 추가하면 된다. 기초 단계가 네 개 필요한 이유는 귀납 단계가 $4$칸 뒤를 참조하기 때문이다.

흔한 오해와 함정

• "$n=1$부터 $40$까지 확인했으니 참이다" — 예시는 증명이 아니다. $n^2+n+41$은 $n=0,\dots,39$에서 소수지만 $n=40$에서 $40\cdot41+41=41^2$으로 합성수다. 유한 개 사례는 전칭 명제 $\forall n\,P(n)$의 반례 부재를 보장하지 못한다. 예시가 증명이 되는 유일한 경우는 존재 명제(구성적 증명)와 반례 제시(전칭 명제의 반증)다.
• "증명 도중에 증명하려는 명제를 써도 된다" — 순환 논증(begging the question)이다. 예컨대 "$n^2$이 짝수이면 $n$이 짝수"를 "$n^2=2k$이므로 $n=2l$로 쓸 수 있다"로 시작하면 결론 자체를 가정한 것이다. 각 단계가 전제·공리·기존 정리에서만 나오는지 점검해야 한다.
• "귀납 단계만 통과하면 충분하다" — 기초 단계가 없으면 전부 무너진다. $P(n)$을 "$n=n+1$"로 두면 귀납 단계($P(k)$이면 양변에 $1$을 더해 $P(k+1)$)는 흠 없이 통과하지만 모든 $P(n)$이 거짓이다. 도미노가 서로 연결되어 있어도 첫 도미노를 넘어뜨리지 않으면 아무 일도 일어나지 않는다.
• "'모든 말은 같은 색' 귀납 논증은 어디가 틀렸는지 지적하기 어렵다" — 오류는 귀납 단계의 $k=1\to2$ 전이에 있다. 말 $k+1$마리에서 첫 마리를 뺀 집합과 마지막 마리를 뺀 집합이 겹친다는 논증은 $k=1$일 때 겹치는 부분이 공집합이라 성립하지 않는다. 귀납 단계는 모든 $k$에서 유효해야 한다.
• "$p\to q$ 대신 $q\to p$를 증명해도 같다" — 역(converse)은 원 명제와 독립이다. 대우 $\neg q\to\neg p$만이 동치이며, 역과 대우를 혼동하는 것은 명제논리의 대표적 오류다. "$n^2$이 짝수 $\to$ $n$이 짝수"를 보인다며 "$n$이 짝수 $\to$ $n^2$이 짝수"를 증명하면 아무것도 한 것이 없다.
• "귀류법의 가정은 결론에 '아니다'만 붙이면 된다" — 한정기호가 있으면 부정 규칙을 적용해야 한다. "$\forall x\,P(x)$"의 부정은 "$\exists x\,\neg P(x)$"이지 "$\forall x\,\neg P(x)$"가 아니다. 부정을 잘못 세우면 모순을 끌어내도 아무것도 증명되지 않는다.

큰 그림 / 연결

이 장의 기법들은 코스 전체의 작업 언어다. 집합과 함수의 집합 등식은 상호 포함(두 방향의 직접증명)으로, 집합의 크기의 대각선 논법은 귀류법의 가장 극적인 응용으로 나타난다. 셈의 기본 원리의 비둘기집 원리는 비구성적 존재 증명의 조합론 버전이고, 그 확률적 완성형이 확률적 방법다. 귀납법은 점화식에서 점화식 해를 검증하는 표준 도구이며, 그래프와 트리의 트리 특성화와 평면그래프의 오일러 공식 $V-E+F=2$처럼 그래프 이론의 굵직한 정리들이 변의 개수에 대한 귀납으로 증명된다. 순열과 조합의 조합적 증명(양쪽에서 세기)은 이 장의 목록에 없는 또 하나의 증명 양식으로, 조합론에서 따로 만난다.

강한 귀납법과 정렬 원리의 동치(정리 7)는 "귀납이 왜 작동하는가"에 대한 답이기도 하다 — 자연수에 무한히 내려가는 사슬이 없다는 사실 자체가 귀납의 토대이며, 이 관점은 정렬 관계 위의 초한 귀납으로 일반화되어 집합론으로 이어진다.

연습문제

1. 두 홀수의 합이 짝수임을 직접증명하라.
2. 정수 $n$에 대해 $n^3+5$가 홀수이면 $n$이 짝수임을 대우증명으로 보여라.
3. $\sqrt3$이 무리수임을 귀류법으로 증명하라. 같은 논증을 $\sqrt4$에 적용하면 어느 단계가 무너지는지 지적하라.
4. $3\nmid n$인 정수 $n$에 대해 $n^2\equiv1\pmod3$임을 경우 나누기로 증명하라.
5. 모든 $n\ge1$에 대해 $1^2+2^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6}$임을 귀납법으로 증명하라.
6. 모든 정수 $n\ge5$에 대해 $2^n>n^2$임을 귀납법으로 증명하라.
7. $3$센트와 $8$센트 우표만으로 $14$센트 이상의 모든 요금을 만들 수 있음을 강한 귀납법으로 증명하라.
8. 다음 "증명"의 오류를 정확히 짚어라: "모든 $n\ge0$에 대해 $a^n=1$ ($a\ne0$). 기초: $a^0=1$. 귀납: $a^{k+1}=\dfrac{a^k\cdot a^k}{a^{k-1}}=\dfrac{1\cdot1}{1}=1$."

관련 개념

• 명제논리 — 대우 동치 $p\to q\equiv\neg q\to\neg p$, 역·이·대우의 구별
• 술어와 한정기호 — 귀류법에서 부정을 정확히 세우는 규칙
• 집합과 함수 — 상호 포함으로 증명하는 집합 등식, 이 장 기법의 첫 실전
• 집합의 크기 — 대각선 논법, 귀류법의 대표적 응용
• 셈의 기본 원리 — 비둘기집 원리, 비구성적 존재 증명의 조합론 형태
• 점화식 — 점화식 해의 귀납적 검증
• 평면그래프 — 오일러 공식의 귀납 증명, 그래프 이론 속의 귀납법
• 확률적 방법 — 비구성적 존재 증명의 현대적 확장