비구성적 증명

목차

1. 소수는 무한히 많다

2. 서랍과 비둘기 집

3. 서랍원칙의 증명

 

---

 

 

---

 

 

1. 소수는 무한히 많다 

 

수학에서는 가끔 확실한 논리적 증명은 가능한데 구체적 예를 들 수가 없는 경우가 있습니다. 이럴 때 '비구성적 증명'이라는 말을 씁니다.

'소수는 무한히 많다'의 예를 가지고 이야기를 해보죠. 소수가 무한하다면 그 중에는 100경짜리 숫자도 분명히 있을 것입니다. 그러나 이런 수를 종이에 쓰거나 해서 구체적으로 보여줄 수는 없습니다. 이제까지의 소수 신기록은 '겨우' 백만 자리를 넘었을 뿐이고, 우리가 살아 있는 동안 이 사실에 근본적인 변화가 있을지도 의문입니다.

 

 

존재의 증명에서 구체적인 증거에 이르는 길은 멀고도 험합니다. 이것도 구체적 증거 제시가 가능할 때의 이야기입니다. 예를 들어 집합론의 창시자 게오르크 칸토어의 논증에 의하면 수의 세계에는 '매우 복잡한 수, 즉 초월수가 상상할 수 없을 정도로 많다고 합니다. 그러나 이렇게 증명된 내용을 구체적으로 눈앞에 제시하는 것은 무척 어렵습니다. 이것보다 더 어려운 것은 구체적인 수의 '복잡성'을 계산해내는 것입니다.

원주율 π의 경우만 해도 그렇습니다. 만일 수학자 린데만이 π가 초월수임을 증명하지 않았다면 수학의 지존으로 떠받들어졌을까요?

 

 

 

아마 '진짜' 삶에는 이런 일이 없다고 생각하는 사람도 있을 것입니다. 미 안하지만 잘 모르고 하는 소리입니다. 이번에는 좋은 예를 찾아 재즈바로 한번 가보죠. 바 안에는 100명의 사람들로 북적거리고 있으며, 분위기도 좋고 '물'이 좋은 곳입니다. 그런데 입구에서 하는 말을 들으니 입장권은 90장이 팔렸을 뿐이라고 합니다. 그렇다면? 10명은 표 없이 몰래 들어왔다는 말이 됩니다. 그러나 그 열 명 중 단 한 사람이라도 제대로 찾아낼 자신이 있나요?

 

---

 

 

2. 서랍과 비둘기 집 

 

아주 중요한 증명법 중에 서랍원칙이라고 불리는 것이 있습니다. 은유적인 이름의 이 방법은 수학적 비구성적 증명의 전형이라고 할 수 있습니다.

아이디어는 아주 간단합니다. n개의 서랍이 달린 서랍장에 n개 이상의 공을 숨겨야 합니다. 그러면 적어도 한 서랍에는 적어도 두 개 이상의 공이 들어가야 합니다. 이것은 서랍을 열어보지 않고도 장담할 수 있는 일이죠. 문제는 어느 서랍이냐 하는 것입니다.

 

 

 

이러한 것은 꼭 서랍이나 공이 아니어도 일상생활에서도 흔히 접하게 되는 문제입니다.

예를 들어 손수건 세 장을 양쪽 호주머니에 넣는다면 한 쪽에는 적어도 두 장의 손수건이 들어가야 하는 것과 마찬가지입니다.

 

---

 

 

3. 서랍원칙의 증명 

 

결과를 직접적으로 보여줄 수는 없습니다. 논리적 반대 입장의 방법을 사용해야 합니다.

셜록 홈즈가 잘 쓰는 방법으로, "X 씨가 범인이 아니라면 Y 부인이 그를 목격했어야만 한다. 그러나 그녀는 그를 보지 못했다. 그러므로 그가 범인이다." 우리의 예에서는 이렇게 말할 수 있습니다. "각 서랍에 공이 한 개씩 들어 있다면 전체 공의 수는 많아봐야 n개여야 한다. 그러나 공은 n개보다 많다. 그러므로 '한 개의 서랍에 많아 봐야 한 개의 공이 들어 있다'라는 가설은 옳지 않다."

 

 

 

 

전형적인 수학적 적용은 다음과 같습니다. 임의의 자연수 11개가 주어져 있습니다. 그렇다면 그 중 적어도 두 개는 같은 숫자로 끝납니다. ‘0', ’1‘, ..., ’9'라고 씌어진 10개의 서랍에 주어진 11개의 수를 끝자리 수에 따라 서랍 속에 정리하는 것입니다.

n마리 이상의 비둘기들이 사는 n개의 비둘기 집을 상상해도 됩니다.

적어도 한 개 이상의 비둘기 집에는 신방이 꾸며질 것이고, 영어에서는 이 로맨틱한 예에 따라 이름을 붙였습니다. 서랍원칙은 영어로 비둘기 집 원칙(pigeon hole principle)이라고 부릅니다.

 

---