증명이란 무엇인가
증명은 수학 전체의 주춧돌이다. 증명 덕분에 돌멩이 몇 개만으로 피라미드 전체를, 그것도 거꾸로 세울 수 있다.
증명의 의미
수학에서 증명이 의미 있는 이유는 여러 가지이다. 가장 큰 이유는 증명 없이는 떠오른 생각이나 가설을 하나도 확인할 수 없다는 것이다. 예를 들어 소수가 유한개라고 믿을 수도 있지만, 증명이 없으면 그런 믿음은 공허한 주장일 뿐이다. 한편 증명되지 않은 명제도 수학(과 그 밖의 분야)에서 의미가 있다. 이럴 때는 “소수가 유한개라는 가정이 성립한다면 … 다른 어떤 이론이 성립한다”라고 말한다.
그런데 그렇게 하면 시간이 지나 누군가 소수가 무한히 많다는 것을 증명하고(뒤에서 이 증명을 살펴본다), 이론 전체가 카드로 만든 집처럼 무너져도 놀랄 일이 아니다. 증명이 있으면 절대 무너지지 않는 카드 집을 지을 수 있다.
학교에서 증명을 배우는 이유는 증명을 이해하는 사람이 그 내용도 이해하기 때문이다. 증명을 이해하지 않고 그 내용을 깊이 이해하기는 보통 어렵다. 여기서 “이해한다”는 말을 강조하는 데에는 이유가 있다. 시험 전날 증명을 통째로 외웠다가 다음 날 시험지에 그대로 쏟아 내기만 한다면, 그 내용을 이해하는 데 조금도 가까워지지 않는다.
즉 무언가를 배울 때 증명은 “왜 그렇게 되는가?”라는 물음에 답한다. 어떤 것이 왜 그렇게 되는지 이해하면 더 쉽게 기억할 수 있고, 시간이 지나면 벼락치기로 외운 사람보다 그 내용을 훨씬 잘 이해하게 된다. 물론 그것이 목표인지는 각자 판단할 문제이다.
증명이란 무엇인가
증명이 무엇인지는 수리 논리에서 예를 들어 구문론적 귀결을 써서 형식적으로 정의한다. 하지만 여기서는 훨씬 간단한 정의로 충분하다.
모든 증명의 출발점에는 증명하려는 주장이 있어야 한다. 이 주장을 마법의 기호 ϕ로 나타내자. “피”라고 읽는 그리스 문자이다. 또 주장 ϕ를 증명하는 데 쓸 공리와 가정의 집합이 필요한데, 이를 Ax로 나타낸다. 공리의 집합은 이미 알고 있는 것, 성립한다고 가정하는 것이다. 예를 들어 “모든 짝수는 2로 나누어떨어진다” 같은 것이다. 또 이 집합에는 다른 곳에서 이미 증명되어 성립한다고 가정하는 식의 변형 공식도 들어 있을 수 있다. 예를 들면 다음과 같다.
이제 집합 Ax의 주장을 차례로 변형해 주장 ϕ를 얻는다. 모든 변형은 논리적으로 올바르고 기본적인 명제 논리에 맞아야 한다. 예를 들어 위의 공식을 증명하려면 다음 식을 동치 변형하여 우변의 식을 얻으면 된다.
직접 해 보자.
첫 번째 단계에서는 거듭제곱을 곱으로 풀어 쓰고, 두 번째 단계에서는 괄호를 풀고, 세 번째 단계에서는 같은 항을 더하고, 마지막 단계에서는 곱을 거듭제곱으로 썼다. 각 단계는 해도 되는 기본적인 변형이었고, 이런 기본 변형은 모두 집합 Ax에 들어 있다고 가정한다.
중요한 것은 모든 변형이 타당해야 하고, 이미 아는 것에서 출발해야 한다는 점이다. 수학적 증명은 진화와 비슷하다. 작은 변형을 차례로 거쳐 한 식에서 다른 식을 얻는다.
자명한 증명
자명한 증명(뻔한 증명)이란 칠판에 다 들어가지 않아서 건너뛰고, 학생이 교재를 보며 숙제로 익히는 증명을 가리키는 전문 용어이다. :-) 진지하게 말하면, 자명한 증명은 보통 어떤 정의에서 한 단계 만에 자명하게 따라 나오는 증명이다.
예를 들어 보자. 자연수 전체의 집합, 즉 ℕ = {1, 2, 3, …}인 집합을 생각하자. 이제 다음 꼴의 분수는 모두 올바른 분수라고 말할 수 있다.
즉 이 분수가 의미를 잃는 수의 쌍 q, p는 없다. 이것을 어떻게 증명할까? 먼저 분수가 언제 의미를 잃는지 알아야 한다. 분모가 0이면 분수는 의미가 없다(0으로 나눌 수 없다). 따라서 가능한 모든 p에 대해 p ≠ 0임을 증명해야 한다. 그런데 p는 자연수에서 고르고, 자연수 전체의 집합은 앞에서 정의한 대로 ℕ = {1, 2, 3, …}인 집합이다. 자연수 전체의 집합에는 0이 없으므로 수 p는 항상 0이 아니다.
이것으로 증명이 끝났다. 분자와 분모가 모두 자연수이면 분수는 올바르다는 것을 알 수 있다.
자명한 증명은 대개 정말로 자명하지만, 주변 맥락을 알 때에만 그렇다. 예를 들어 집합이라는 개념을 모르거나 p가 집합 ℕ의 원소라는 것이 무슨 뜻인지 모른다면, 이 증명도 자명하지 않았을 것이다. 따라서 자명한 증명의 특징은 쉽다는 것보다는 짧고, (얼마든지 어려울 수 있는) 어떤 맥락에서 간단히 따라 나온다는 것이다.
반례
반례는 주어진 명제가 참이 아님을 보이는 가장 간단한 방법일 것이다. 중요한 것은 “아님”이라는 말이다. 반례는 주어진 명제가 성립하지 않는 경우를 보여 줄 수 있다. 그러나 확인해야 할 원소가 무한히 많을 때에는 아무리 많은 예를 들어도 명제가 참임을 보이기에는 부족하다.
예: “모든 자연수는 10보다 크다.” 이것이 참이 아님은 어떻게 보일까? 예를 들어 5가 이 주장의 반례이다. 5는 자연수이고 10보다 크지 않다. 반대로 10보다 큰 자연수를 몇 개 늘어놓는 것으로는 이 주장을 증명할 수 없다. “자연수 11, 12, 13, 123, 5345는 10보다 크므로 이 명제는 참이다”라고 할 수는 없다. 그렇게 하면 주장이 성립하는 예를 몇 개 골랐을 뿐, 언급하지 않은 나머지 수에 대해서는 아무것도 말해 주지 않는다.
두 번째 예: 키가 2 m보다 큰 남자는 모두 눈이 갈색이거나 파란색이다. 반례를 찾을 수 있는 사람은 거의 없을 것이다. 이것이 이 명제에 대해 무엇을 말해 줄까? 아무것도 말해 주지 않는다. 반례를 찾지 못했다고 해서 명제가 반드시 참인 것은 아니다. 반례가 어딘가에 있는데 아직 찾지 못했을 수도 있다. 반례를 찾지 못했다는 사실은 주장이 참임을 증명하지 않는다.
직접 증명
가장 기본적인 증명은 직접 증명이다. 정의에 따라 담담하게 처음 명제를 변형해서 얻고자 하는 명제에 이른다. 보통 증명하려는 명제는 조건문 A ⇒ B 꼴이다. 여기서 A는 출발점인 가정이고, B는 이끌어 내려는, 즉 증명하려는 명제이다. 명제 A가 성립하면 명제 B가 성립한다. 증명하려는 명제 B만 주어지고, 명제 A는 직접 알맞게 골라야 하는 경우도 많다.
그다음 조건문을 이용해 명제를 차례로 이끌어 내어 마지막에 명제 B에 이른다. 이를 도식으로 나타내면 다음과 같다.
예로 다음 명제를 증명해 보자.
단계별로 살펴보면 다음과 같다.
- a>1이므로 당연히 a>0이고 a ≠ 0이다(사실상 조건을 약하게 한 것뿐이다).
- a는 0이 아니고 양수이므로 부등식의 양변에 문자 a를 안심하고 곱할 수 있다. a가 0이면 등호를 포함하지 않는 부등호가 유지되지 않고(0>0을 얻는다), 음수이면 부등호의 방향을 바꿔야 한다. 양변에 a를 곱하면 a2>a를 얻는다.
- 이제 a>1이고 a2>a임을 안다. 두 식을 합치면 a2>a>1을 얻는다.
- 여기서 가운데 식을 없애면 a2>1을 얻는다. a가 1보다 크고 a2이 a보다 크므로 이렇게 해도 된다. a2이 a보다 크고 a가 1보다 크면 a2은 당연히 1보다 크다.
기호로는 다음과 같이 쓸 수 있다.
간접 증명
간접 증명은 조건문의 성질을 더 적극적으로 이용한다. A ⇒ B 꼴의 주장을 증명해야 할 때, 그 대우를 이용해 다음을 증명할 수 있다.
여기서 ¬ 기호는 부정을 나타낸다(한국 교과서에서는 ∼B처럼 쓴다). 이 방법이 직접 증명보다 편리할 때가 있다. 귀류법도 비슷한 방법을 쓰며, 모든 간접 증명은 귀류법으로 바꿀 수 있다. 다음 주장을 간접 증명으로 증명해 보자.
먼저 대우를 만든다.
a ≠ b이면 b를 합 b = a + x로 나타낼 수 있다. 여기서 x는 수 b와 수 a의 차를 나타낸다. 식은 다음과 같이 바뀐다.
뺄 수 있는 a를 빼면 다음과 같다.
x ≠ 0이므로 −x ≠ 0이고, 따라서 조건문이 성립한다. 주장이 증명되었으므로 다음 원래 명제도 성립한다.
다른 증명 방법으로는 앞에서 말한 귀류법이나 수학적 귀납법 등이 있다.