소수: 수학자들이 사랑한 수 (3)

귀류법

당신은 수학 법정의 초임 재판관이며 오늘은 당신의 첫 재판일이다. 당신은 긴장을 잔뜩 머금은 채 법정에 들어섰다. 다행히 당신의 좌측과 우측에는 당신의 판결을 도와줄 조력자 '변호인'과 '검찰'이 있었다. 둘은 현명하고 합리적이지만, 늘 대립되는 주장을 펼치기로 유명했다. 오늘 맡게 된 재판의 소는 이러했다.

소수가 무한히 많은지 아닌지 판별해 주시오.

개정이 선언되자, 예상대로 둘은 팽팽한 공방을 펼쳤다. 

검찰 측 주장: 소수는 무한히 많지 않다.

“존경하는 재판장님, 에라토스테네스의 체를 그리는 과정에서 살펴보셨듯, 숫자가 커질수록 소수의 빈도는 확연히 줄어듭니다. 이 빈도는 계속 줄어들 것이며, 언젠가는 0에 다다르게 될 것입니다.” 

변호인 측 주장: 소수는 무한히 많다.

“존경하는 재판장님, 자연수는 무한히 많으며, 산술의 기본정리에 의해 이들은 모두 유일한 방법으로 소인수분해가 가능합니다. 만약 소수의 개수가 정해져 있다면, 이들로 무한히 많은 자연수들을 만들어내기는 어려워 보입니다." 

검찰 측 반론: “변호인 측의 주장에는 비약이 있습니다. 예컨대 하나의 소수만으로도, 2, 2×2, 2×2×2, … 등 얼마든지 다양한 자연수를 만들어낼 수 있습니다. 자연수가 무한히 많다는 사실이 소수가 무한히 많다는 주장의 근거가 될 수 없습니다.” 

변호인 측 반론: “검찰 측의 주장에도 비약이 있습니다. 빈도가 줄어드는 것이 꼭 빈도가 0이 된다는 것을 의미하진 않습니다. 1, 4, 9, 16, 25, … 등 제곱수들을 보십시오. 제곱수의 빈도도 굉장히 빠르게 줄어들지만, 제곱수는 무한히 많습니다.” 

양측의 주장과 반론을 모두 경청한 당신은 깊은 고민에 빠졌다. 각각의 논리는 나름의 설득력이 있었다. 하지만 또 각자의 이유를 물고 늘어진다면 반박할 여지가 있어 보였다. 당신은 한참을 고심하다 문득 근본적인 의문이 들었다. 애초에 ‘무한히 많다’는 것은 무엇일까? 그리고 무한히 많다는 사실을 어떻게 증명할 수 있을까? 이 의문을 먼저 해결하지 않고선 판결을 내릴 수 없다. 당신은 지혜로운 판사답게 엄숙하고 근엄한 목소리로 말한다. “휴정을 선언합니다.” (각주 [1] 참고.) 

어떻게 하면 무언가가 무한히 많음을 보일 수 있을까? 가장 먼저 떠오르는 방법은 '하나하나 헤아려보는 것'이다. 모두 다 셀 수 있다면 그것은 유한한 것이고, 모두 다 셀 수 없다면 무한한 것이라고 말이다. 하지만 이 방법에는 치명적인 결함이 있다. 그 방법은 오로지 무언가가 ‘유한히 많음’만을 보여준다는 사실이다.

예를 들어보자. 당신이 자연수의 무한성을 증명하기 위해 평생을 바쳐 숫자를 세기로 했다고 가정해 보자. 옹알이를 시작할 때부터 "일, 이, 삼..."을 세기 시작해서, 80년의 삶 동안 쉼 없이 세어 10억까지 도달했다. 그리고 10억을 세는 순간, 당신의 숨이 다했다. (각주 [2] 참고) 그렇다면 당신은 무엇을 증명한 것일까? 당신은 두 가지 사실을 증명했다. 하나는 "자연수는 적어도 10억 개보다 많다"는 것이고, 다른 하나는 "인생은 유한하다"는 것이다. 당신은 평생에 걸친 노력에도 불구하고, 자연수가 무한히 많다는 사실을 증명하지는 못했다.

그렇다면 자연수가 무한히 많음을 증명하기 위해서는 어떤 방법을 써야 할까? 우리는 먼저 그 주장의 반대 주장을 상정해야 한다. 그리고 그 주장을 충실히 따르며 논리를 전개해야 한다. 그 논리에 끝에 반드시 모순에 다다라야 한다. 모순은 그 자유로운 수학 안에서 절대로 허용될 수 없는 단 하나의 금기이기 때문이다. (각주 [3] 참고) 

이 증명 방법은 수학사에서 가장 영리한 전략 중 하나다. 마치 적진에 침투하는 밀정처럼, 반대편의 진영으로 들어가 그들의 주장을 무너뜨린다. 그렇다면 우리도 그런 밀정이 되어 자연수가 무한히 많음을 증명해 보자. 우리는 "자연수가 무한히 많지 않다"는 주장의 충실한 지지자로 위장할 것이다. 하지만 빈 손으로 적진에 뛰어들 순 없다. 우리는 다음의 암수, 곧 '사실'을 우리 소매 속에 숨겨둘 것이다.

x가 자연수라면, x+1도 자연수이다. (각주 [4] 참고.)

자연수가 무한히 많지 않다고 가정하자. 오름차순으로 자연수를 배열하면, 그 수열은 언젠가 끝을 맞이해야 한다. 이때 가장 큰 자연수를 N이라고 하자. 여기서 무기를 사용한다. N이 자연수면, N+1도 자연수이다. 또한 N+1은 N보다 크다. 이는 N이 가장 큰 자연수라는 가정과 모순된다. 즉, 자연수가 무한히 많지 않다는 가정은 모순을 낳는다. 그러므로 자연수는 무한히 많다.

이러한 증명 방법을 수학자들은 '귀류법(歸謬法)', 영어로는 proof by contradiction이라 부른다. 종종 철학자들은 이를 reductio ad absurdum이라고 부르곤 하는데, 이는 ‘모순으로의 환원’으로 번역할 수 있다. 영화 속 주인공이 홀로 적진에 뛰어들어 폭탄을 설치하고 돌아오듯, 귀류법은 증명하고자 하는 명제의 반대를 가정했다가 그 안에서 모순이라는 폭탄을 터뜨린다. 이 귀류법의 매력에 빠진 것은 비단 나뿐만이 아니다. 영국의 저명한 수학자 고드프리 하디는 자신의 책 "어느 수학자의 변명"에 다음과 같이 고백했다. 

유클리드가 그토록 사랑했던 귀류법은 수학자의 가장 우아한 무기 중 하나다. 이는 어떤 체스 전략보다도 뛰어난 수이다. 체스 기사는 폰이나 기물 희생할 수 있지만, 수학자는 게임 전체를 걸기 때문이다.(각주 [5] 참고.)

[1] 이러한 식의 ‘양측주장논의’가 의미가 있는 이유는 그것이 수학에 대한 더 깊은 이해를 가져다주기 때문이다. 필자도 수학 논문을 몇 편 작성해 봤지만, 이렇게 양측의 가능성을 열어두는 편이 더욱 풍성한 설명과 따름 연구의 가능성을 가져오곤 했다. 물론 논문 중에서는 이러한 양측 주장을 법정의 상황으로 재현하지는 않는다. 법정의 상황으로 재현한 이유는 순전히 필자가 ‘역전재판’이라는 게임의 팬이어서이다.

[2] 일반적으로 수가 커질수록 그 수를 발음하는 데 필요한 음절 수도 늘어난다. 1초에 2음절씩 발음한다고 해도 ChatGPT의 계산에 따르면, 80년 동안 쉬지 않고 숫자를 세어도 5억을 넘기기는 어렵다고 한다.

[3] 독일의 수학자 게오르그 칸토어는 다음과 같이 말했다. “수학의 본질은 그 자유로움에 있다.”

[4] 이 사실은 자연수의 정의에 기반한다. 앞서 자연수는 1, 2, 3, 4, 등 사물을 세는 수라고 정의하였다. 하지만 자연수를 엄밀하게 정의하려면 다음과 같은 재귀적인 방법을 사용해야 한다. "1은 자연수이다. x가 자연수라면, x+1도 자연수이다."

[5] “Reductio ad absurdum, which Euclid loved so much, is one of a mathematician's finest weapons. It is a far finer gambit than any chess play: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game.”