PART I — 증명
수학에서 "맞다"는 말은 어떤 의미일까요? 과학자는 실험으로, 법정은 증거로, 친구끼리는 그냥 우기는 걸로 무언가를 "증명"한다고 말합니다. 이 챕터에서는 수학에서 통용되는 증명, 즉 누구도 빠져나갈 수 없도록 논리만으로 진리를 확립하는 방법을 배웁니다. 이산수학을 처음 만나는 여러분에게 가장 먼저 필요한 도구이자, 앞으로 모든 챕터의 공용어가 되는 내용입니다.
증명을 이야기하기 전에 먼저 "무엇을" 증명하는지부터 분명히 해야 합니다. 수학에서 증명의 대상은 항상 명제(proposition)입니다. 명제란 참(true)인지 거짓(false)인지가 분명히 정해지는 평서문을 말합니다. 명령문이나 의문문, 감탄문은 명제가 아닙니다. "문 좀 닫아줘"는 참도 거짓도 아니니까요.
정의 1.1.1 (명제)
참(T) 또는 거짓(F) 둘 중 하나의 진릿값을 갖는 평서문을 명제라고 합니다.
예제 1.1.2
다음 문장 중 명제는 어떤 것일까요?
여러 명제를 "그리고", "또는", "아니다", "~이면 ~이다" 같은 연결사로 묶으면 합성 명제(compound proposition)가 됩니다. 예컨대 \( P \)가 "비가 온다", \( Q \)가 "땅이 젖는다"라면, \( P \implies Q \)는 "비가 오면 땅이 젖는다"라는 새로운 명제입니다. 우리는 곧 이런 연결사들을 도구처럼 다루게 될 거예요.
노트
일상에서 우리가 "명제"라고 부르는 많은 문장들("이 영화 재밌어", "오늘 날씨가 좋네")은 사실 수학적 의미의 명제는 아닙니다. 수학적 명제는 평가 기준이 명확하고, 누가 봐도 동일한 결론에 이를 수 있어야 합니다. 이 엄격함이 답답해 보일 수 있지만, 이게 바로 수학이 "다툴 일이 없는" 학문이 되는 이유예요.
방금 본 \( x + 1 = 2 \)는 명제가 아니었습니다. 그런데 변수 \( x \)에 구체적인 값을 넣으면 명제가 되지요. 이렇게 변수가 들어가서 그 변수의 값에 따라 진릿값이 달라지는 문장을 술어(predicate)라고 부릅니다. 보통 \( P(x) \), \( Q(n) \) 같은 표기를 씁니다.
정의 1.2.1 (술어)
한 개 이상의 변수에 의존하는 문장으로, 각 변수에 구체적인 값을 대입할 때마다 명제가 되는 것을 술어라고 합니다.
예제 1.2.2
\( P(n) \)을 "\( n^2 + 1 \)은 짝수이다"로 정의해 봅시다.
패턴이 보이나요? \( n \)이 홀수일 때 \( P(n) \)이 참인 것 같죠. 이것을 모든 홀수에 대해 보이려면 곧 배울 일반적 증명 기법이 필요합니다.
술어가 중요한 이유는, 수학의 거의 모든 흥미로운 주장이 "모든 \( n \)에 대해 \( P(n) \)이 성립한다" 또는 "어떤 \( n \)이 존재해서 \( P(n) \)이 성립한다" 형태이기 때문입니다. 이 두 가지를 각각 전칭(universal) 양화와 존재(existential) 양화라고 부르고, 기호로 \( \forall n,\ P(n) \), \( \exists n,\ P(n) \)이라 씁니다. 양화 기호의 자세한 사용법은 다음 챕터에서 다룹니다. 지금은 술어가 명제의 "변수 버전"이라는 것만 기억하면 충분해요.
"증명한다"는 게 도대체 무엇일까요? 머리에 떠오르는 그럴듯한 설명을 하는 것? 그림을 그려 보는 것? 수많은 예를 확인하는 것? 셋 다 영감을 주지만, 셋 다 수학적 증명은 아닙니다. 수학에서 증명이란 이미 받아들인 사실들로부터 논리적으로 새 사실을 이끌어내는 과정입니다.
그러면 그 "이미 받아들인 사실"은 어디서 올까요? 끝없이 거슬러 올라갈 수는 없으니, 어딘가에서 멈춰야 합니다. 그 출발점을 공리(axiom)라고 부릅니다. 공리는 증명 없이 참이라고 합의하는 명제입니다. 그리고 공리로부터 논리만 사용해 증명한 명제를 정리(theorem)라 부르고, 그 과정 자체가 증명(proof)입니다.
정의 1.3.1 (공리적 방법)
몇 개의 공리에서 출발해, 오직 논리적 추론으로 새로운 정리를 만들어 가는 수학 작업의 표준 방식을 공리적 방법(axiomatic method)이라 합니다.
이 사고방식은 기원전 300년경 유클리드(Euclid)의 『원론(Elements)』에서 시작되었습니다. 유클리드는 다섯 개의 공준과 몇 개의 공통 관념에서 출발해 평면기하 전체를 쌓아 올렸어요. 2200년이 지난 후 힐베르트(Hilbert)는 유클리드의 빈틈을 메워 더 엄밀한 공리계를 제시했고, 20세기 들어 페아노(Peano), 체르멜로–프렝켈(ZF) 같은 산술/집합론 공리계가 자리를 잡았습니다.
노트
공리는 "당연히 참인 자명한 진리"가 아닙니다. 그저 게임의 규칙처럼 우리가 함께 쓰자고 약속한 시작점일 뿐이에요. 공리를 다르게 잡으면 다른 수학이 나옵니다. 평행선 공리를 살짝 바꾸면 비유클리드 기하가 태어나는 것처럼요.
이 책에서는 공리계를 처음부터 모두 형식적으로 까는 대신, 학부 1학년 수준의 수학에서 자연스럽게 사용하는 표준 사실들을 공리로 받아들이겠습니다. 즉, 다음과 같은 것들이에요.
이 공리들은 너무 친숙해서 "굳이 공리라고 부를 필요가 있나?" 싶을 정도지만, 정확히 그 친숙함이 함정이기도 합니다. 한 단계 한 단계의 추론이 정말로 이런 공리만 쓰는지 자기 자신에게 묻는 습관을 들여야 해요.
잠깐, 공리가 거짓이면?
공리계 안에 모순이 숨어 있다면 그 안에서는 어떤 명제도 "증명"할 수 있게 됩니다. 거짓에서는 무엇이든 따라 나오니까요. 그래서 공리의 일관성(consistency)을 확신하는 일은 매우 중요합니다. 다만 괴델의 제2 불완전성 정리가 알려주듯, 충분히 강한 공리계는 자기 자신의 일관성을 자기 안에서 증명할 수 없어요. 다행히 우리가 쓰는 공리계는 수천 년의 사용 경험 속에서 모순이 발견된 적 없으므로, 안심하고 사용해도 됩니다.
예제 1.4.1 (잘못된 공리, 잘못된 정리)
"모든 말은 같은 색이다"라는 우스개 정리가 있습니다. 어떤 책에서는 "말 \( n \)마리 무리에서는 모든 말의 색이 같다"를 \( n \)에 대한 귀납으로 증명하려다 \( n=1 \)에서 \( n=2 \)로 넘어가는 단계에서 공리 아닌 것을 슬쩍 가정해 엉터리 결론에 이릅니다. 시작점이 잘못되거나 한 줄이라도 정당하지 못한 추론이 끼면, 결과는 멀쩡해 보여도 무너집니다. 우리가 받아들이는 공리가 무엇인지를 분명히 의식하는 일이 중요한 이유예요.
가장 흔히 마주치는 명제 형태가 \( P \implies Q \), 즉 "\( P \)이면 \( Q \)이다" 꼴의 함의(implication)입니다. 이걸 어떻게 증명할까요? 가장 직접적인 방법은 이렇습니다.
원리 1.5.1 (함의의 직접 증명)
\( P \implies Q \)를 보이려면, "\( P \)가 참이라고 가정하자"로 시작해서, 일련의 논리적 단계를 거쳐 \( Q \)가 참이라는 결론에 이르면 됩니다.
예제 1.5.2
주장: 정수 \( n \)에 대해, \( n \)이 짝수이면 \( n^2 \)도 짝수이다.
증명. \( n \)이 짝수라고 가정하자. 그러면 어떤 정수 \( k \)에 대해 \( n = 2k \)로 쓸 수 있다. 따라서
\[ n^2 = (2k)^2 = 4k^2 = 2(2k^2). \]
\( 2k^2 \)는 정수이므로 \( n^2 \)도 \( 2 \cdot (\text{정수}) \) 꼴이다. 즉 \( n^2 \)은 짝수이다. ∎
이때 한 가지 헷갈리는 지점이 있습니다. \( P \)가 거짓일 때 \( P \implies Q \)는 무엇일까요? 수학에서는 약속에 의해 \( P \)가 거짓이면 \( P \implies Q \)는 자동으로 참이 됩니다. "전제가 무너지면 무엇이든 결론으로 삼아도 된다"라는 뜻이에요. 이걸 공허한 참(vacuously true)이라고 부릅니다.
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
한국어 학생이 자주 헷갈리는 곳
"비가 안 왔는데 땅이 젖어 있다고 해서 '비가 오면 땅이 젖는다'가 거짓이 되지는 않잖아?" 같은 식으로 생각하면 편합니다. 함의는 "전제가 참인 상황에서 결론이 참이라고 약속한 것"일 뿐, 전제가 거짓일 때까지 보장하는 게 아니에요. 그래서 \( 0 = 1 \implies \text{나는 천재이다} \) 같은 농담식 함의도 수학적으로는 그냥 참입니다.
또 한 가지, 대우(contrapositive)와 역(inverse)을 구분해야 합니다. \( P \implies Q \)에 대해
예를 들어 "비가 오면 땅이 젖는다"의 대우는 "땅이 젖지 않으면 비가 오지 않았다"이고 항상 같이 참/거짓이지만, 역인 "땅이 젖었으면 비가 왔다"는 원래 명제가 참이어도 거짓일 수 있습니다(스프링클러가 있으니까요). 시험에서 가장 자주 실수하는 지점이니 꼭 기억해 둡시다.
명제가 \( P \iff Q \) 꼴이라면, 이는 "\( P \)와 \( Q \)는 동시에 참이거나 동시에 거짓이다"라는 뜻입니다. 이걸 증명하는 방법은 두 가지가 흔합니다.
원리 1.6.1 (양방향 증명)
\( P \iff Q \)를 보이려면, \( P \implies Q \)와 \( Q \implies P \)를 각각 증명하면 됩니다. 보통 첫 번째 방향을 "(⇒)", 두 번째 방향을 "(⇐)"로 표시해요.
예제 1.6.2
주장: 정수 \( n \)에 대해, \( n \)이 짝수일 필요충분조건은 \( n^2 \)이 짝수인 것이다.
증명.
(⇒) \( n \)이 짝수이면 \( n^2 \)도 짝수임은 예제 1.5.2에서 이미 보였습니다.
(⇐) 이번에는 대우를 사용합시다. \( n \)이 홀수라고 가정하면 \( n = 2k+1 \) 꼴이고,
\[ n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 \]
이므로 \( n^2 \)도 홀수입니다. 따라서 \( n^2 \)이 짝수이면 \( n \)도 짝수예요. ∎
두 번째 방법은 동치 사슬(chain of equivalences)을 만드는 것입니다. \( P \iff P_1 \iff P_2 \iff \cdots \iff Q \)처럼 한 단계씩 동치 변환만으로 \( P \)에서 \( Q \)까지 가는 방식이에요. 단, 모든 단계가 정말로 동치 관계여야 합니다. 한 군데서 한쪽으로만 함의되면 사슬이 깨져요.
노트
"필요충분조건"이라는 한국어 표현이 처음에는 헷갈릴 수 있어요. 보통 "\( P \)는 \( Q \)이기 위한 필요조건"은 \( Q \implies P \)이고, "충분조건"은 \( P \implies Q \)입니다. 둘 다 성립하면 동치예요. 대학 시험에서 단어 함정으로 자주 등장하니 외워 두면 좋습니다.
때로는 명제를 한 번에 증명하기보다, 가능한 모든 상황을 몇 개의 경우로 나눠 각각에서 증명하는 게 훨씬 편합니다. 이걸 경우 분리 증명(proof by cases)이라 합니다.
원리 1.7.1 (경우 분리)
증명하려는 명제의 영역을 \( C_1, C_2, \dots, C_k \)로 빠짐없이 나누고(즉 적어도 하나의 \( C_i \)에는 반드시 속함), 각 \( C_i \)에서 결론이 성립함을 보이면 전체에서 명제가 성립합니다.
예제 1.7.2
주장: 모든 정수 \( n \)에 대해 \( n^2 + n \)은 짝수이다.
증명. 정수 \( n \)을 두 경우로 나누자.
경우 1. \( n \)이 짝수. 그러면 \( n = 2k \)이므로 \( n^2 + n = 4k^2 + 2k = 2(2k^2 + k) \), 짝수.
경우 2. \( n \)이 홀수. 그러면 \( n = 2k+1 \)이고
\[ n^2 + n = (2k+1)^2 + (2k+1) = (2k+1)\bigl((2k+1)+1\bigr) = (2k+1)(2k+2) = 2(2k+1)(k+1) \]
이므로 짝수. 두 경우 모두에서 \( n^2 + n \)이 짝수임을 보였다. ∎
경우 분리에서 가장 중요한 점은 모든 경우를 빠짐없이 다루었는가입니다. 한 경우라도 누락되면 그 영역에서 명제가 거짓일 가능성이 남아 증명이 무너지죠. 때문에 "이 외의 경우는 가능하지 않다"는 한 줄이라도 명시하는 습관이 좋습니다.
위트 한 줄
"모든 말이 같은 색이다"라는 가짜 정리에 대한 가짜 귀납 증명도 경우를 잘못 묶은 사례로 자주 인용됩니다. 거기에서는 두 마리 무리를 한 마리씩 두 번 보면서 "교집합이 비지 않으니 색이 같다"라고 하는데, 정작 \( n=2 \)일 때는 교집합이 빈집합이라는 사실을 빼먹어요. 경우 나누기는 자유지만, 빈자리가 있으면 결국 이런 코미디가 됩니다.
직접 증명이 막힐 때 강력하게 작동하는 무기가 모순법(proof by contradiction)입니다. 핵심 아이디어는 단순합니다. \( P \)를 보이고 싶다면, "\( P \)가 거짓이라고 가정해 보자"라고 시작해서 그 가정으로부터 명백한 모순(예: \( 0 = 1 \) 같은 것)을 끌어냅니다. 그러면 \( \lnot P \)는 받아들일 수 없고, 따라서 \( P \)가 참이어야 합니다.
원리 1.8.1 (모순법)
\( P \)를 보이려면, \( \lnot P \)를 가정한 뒤 그로부터 모순을 도출하면 됩니다.
예제 1.8.2 (\( \sqrt{2} \)는 무리수)
주장: \( \sqrt{2} \)는 유리수가 아니다.
증명(모순법). 결론을 부정해 \( \sqrt{2} \)가 유리수라고 가정하자. 그러면 서로소인 두 정수 \( a, b \)(단 \( b \neq 0 \))에 대해
\[ \sqrt{2} = \frac{a}{b} \]
로 쓸 수 있다. 양변을 제곱하면 \( 2 = \dfrac{a^2}{b^2} \), 곧 \( a^2 = 2b^2 \). 우변이 짝수이므로 \( a^2 \)도 짝수이고, 예제 1.6.2의 결과에서 \( a \)도 짝수이다. 따라서 \( a = 2c \)인 정수 \( c \)가 있다. 대입하면 \( (2c)^2 = 2b^2 \), 즉 \( 4c^2 = 2b^2 \), \( b^2 = 2c^2 \). 같은 논리로 \( b \)도 짝수이다. 그런데 \( a, b \)가 모두 짝수이면 둘 다 \( 2 \)로 나뉘므로 서로소라는 가정에 모순이다. ∎
모순법은 강력하지만 남용은 좋지 않습니다. 직접 증명이 가능한 명제를 굳이 모순법으로 쓰면, 독자가 "왜 부정에서 시작했지?" 하고 흐름을 따라가기 힘들어요. 직접 증명으로 풀리면 직접, 막히면 모순법, 정도로 생각하면 됩니다.
노트
모순법은 사실상 대우 증명의 일반화로 볼 수도 있습니다. \( P \implies Q \)를 모순법으로 보일 때 "\( P \)이면서 \( \lnot Q \)"를 가정해 모순을 얻는다고 하면, 이는 본질적으로 \( \lnot Q \implies \lnot P \)를 보이는 것과 같은 작업이에요.
지금까지 본 증명 기법들은 도구일 뿐이고, 실제로 좋은 증명을 쓰는 일은 그 도구를 어떤 태도로 다루느냐에 달려 있습니다. 정답이 정해진 일은 아니지만, 경험적으로 다음 원칙들이 도움이 됩니다.
마지막으로, 증명은 처음에 잘 안 써지는 게 정상이라는 점을 기억하세요. 실제 수학자들도 종이 한 면을 채우는 증명을 위해 십수 장의 낙서를 거칩니다. 머릿속에서 떠오른 아이디어를 정돈하고, 빈자리를 메우고, 다시 짧게 다듬는 과정이 곧 수학을 하는 일입니다. 이 책의 다음 챕터부터 우리는 이 도구들을 본격적으로 휘두르며 명제논리, 술어논리, 집합, 함수, 그래프, 이산확률에 이르기까지 이산수학의 풍경을 함께 걷게 될 거예요.
컴퓨터과학적 연결
증명은 단순히 수학 시험을 위한 것이 아닙니다. 알고리즘이 정말로 정답을 내는지(정확성), 정해진 시간 안에 끝나는지(종료성), 한정된 자원으로 동작하는지(자원 한계)는 모두 증명의 대상입니다. 자료구조의 정합성, 분산 시스템의 합의 프로토콜, 암호 시스템의 안전성도 마찬가지예요. 이산수학에서 익히는 증명 능력은, 결국 신뢰할 수 있는 소프트웨어를 만드는 능력의 다른 이름입니다.