수학 기초론 논쟁(Debate on the foundations of mathematics)

1900년 무렵의 수학은 스스로를 가장 확실한 지식이라 여겼습니다. 19세기 동안 코시와 바이어슈트라스는 미적분⁠(calculus)⁠의 극한⁠(limit)⁠을 엄밀한 말로 다시 적었고, 데데킨트와 칸토어는 실수⁠(real number)⁠를 유리수⁠(rational number)⁠로, 유리수를 정수⁠(integer)⁠로 짓는 방법을 보였습니다(수 체계⁠(number system)⁠). 그러면 남는 것은 자연수⁠(natural number)⁠와 집합⁠(set)⁠뿐이었고, 칸토어의 집합론은 무한의 크기까지 다룰 수 있게 해 주었습니다(집합의 크기⁠, cardinality⁠). 그런데 바로 그 집합론의 밑바닥에서 모순이 나왔습니다. 그 뒤 1931년 무렵까지, 수학의 확실성을 무엇 위에 세울지를 둘러싸고 이어진 논쟁을 수학 기초론 논쟁이라 부릅니다. 1921년 독일의 수학자 헤르만 바일은 이 상황을 '기초⁠(basics)⁠의 새로운 위기'라 불렀습니다.

역설. 1897년 이탈리아의 체사레 부랄리포르티가, 1899년 무렵 칸토어 자신이 '가장 큰 것'을 모으려 하면 모순이 생기는 예를 찾았고, 1901년 러셀이 가장 단순한 형태를 찾았습니다. 자기 자신을 원소⁠(element)⁠로 갖지 않는 집합을 모두 모은 집합 R은 자기 자신의 원소일까요? 원소라면 R의 조건에 따라 원소가 아니고, 원소가 아니라면 조건에 맞으니 원소입니다(러셀의 역설⁠(Russell's paradox)⁠). 어떤 조건이든 그 조건을 만족하는 것을 모으면 집합이 된다는, 아무도 의심하지 않던 원리가 모순을 낳은 것입니다. 1902년 6월 러셀의 편지를 받은 프레게는 산술을 논리에서 이끌어 내려던 『산술의 기본 법칙』 2권의 부록에서 자기 체계가 무너졌음을 인정했습니다. 논리로 수학을 세우려는 흐름을 못마땅해하던 푸앵카레는 1906년 '기호 논리⁠(symbolic logic)⁠는 더는 열매 없는 학문이 아니다. 모순을 낳고 있으니까'라고 비꼬았습니다.

대답은 크게 셋으로 갈렸습니다.

논리주의: 수학은 논리다. 프레게와 러셀은 수학의 개념을 모두 논리의 개념으로 정의하고, 수학의 정리를 모두 논리의 법칙에서 증명하려 했습니다. 예컨대 수 2는 '원소가 둘인 모든 모임들의 모임'으로 정의됩니다. 여기서 '둘'은 수를 쓰지 않고 '서로 다른 x와 y가 있고, 그 밖의 것은 없다'로 말합니다. 러셀은 역설을 피하려고 대상을 층층이 나누어 자기 층의 모임만 원소로 삼게 하는 타입 이론⁠(type theory)⁠을 만들고, 영국의 알프레드 노스 화이트헤드와 함께 『수학 원리』(1910–1913) 세 권에 담았습니다. 그러나 이 체계에는 대상이 무한히 많다는 공리(무한 공리⁠, axiom of infinity⁠)와 환원 가능성 공리⁠(axiom of reducibility)⁠처럼, 논리의 법칙이라 부르기 어려운 가정이 필요했습니다. 러셀의 제자였던 비트겐슈타인은 『논리철학 논고』(1921)에서 논리의 명제는 세계에 대해 아무것도 말하지 않는 항진명제⁠(tautology)⁠라고 주장했고, 램지는 이 생각을 받아들여 1926년 러셀의 체계를 단순하게 다듬었습니다.

형식주의: 수학은 규칙이 분명한 기호의 체계이고, 그 체계에 모순이 없음을 증명하자. 힐베르트는 무한을 버리지 않으려 했습니다. '칸토어가 만든 낙원에서 아무도 우리를 쫓아낼 수 없다'(1925). 그의 계획은 이랬습니다. 먼저 수학의 각 분야를 공리⁠(axiom)⁠와 추론 규칙이 분명한 형식 체계⁠(formal system)⁠로 적어, 증명을 낱말의 뜻과 상관없이 기호열을 규칙대로 바꾸는 일로 만든다. 그다음 그 체계에서 0 = 1 같은 모순이 결코 나오지 않음을, 누구도 의심할 수 없는 유한한 방법(기호를 세고 견주는 정도의 논증)으로 증명한다. 무한한 대상에 관한 수학은 뜻을 묻지 않는 도구로 두고, 그 도구를 안심하고 써도 된다는 보증만 유한한 방법으로 얻겠다는 것입니다. 산술의 무모순성⁠(consistency)⁠은 1900년 그가 파리에서 내놓은 23개 문제의 두 번째이기도 했습니다.

직관주의: 수학은 마음이 지어 가는 것이다. 네덜란드의 브라우어르는 1907년 박사 논문부터 반대쪽 끝에 섰습니다. 수학의 대상은 사람의 마음이 시간 속에서 하나씩 지어 가는 것이고, 무엇이 있다고 말하려면 그것을 지어 보일 수 있어야 한다는 것입니다. 그러면 무한한 모임에 대해서는 '모든 명제는 참이거나 거짓이다'라는 배중률⁠(law of excluded middle)⁠을 함부로 쓸 수 없습니다. 끝없는 목록을 다 훑어볼 수는 없으니, 증명도 반증도 없는 명제를 두고 '둘 중 하나는 참'이라고 말할 근거가 없기 때문입니다. 브라우어르는 칸트에게서 시간의 직관만 이어받고 공간의 직관은 버렸다고 스스로 말했습니다. 헤르만 바일은 1921년 '브라우어르, 그것이 혁명이다'라고 쓰며 한동안 그를 따랐습니다.

배중률이 무슨 일을 하는지 작은 예로 봅시다. a^b이 유리수인 무리수⁠(irrational number)⁠ a, b가 있다. 증명: $\sqrt2^{\sqrt2}$가 유리수라면 a = b = √2로 끝입니다. 무리수라면 $a = \sqrt2^{\sqrt2}$, $b = \sqrt2$로 두면 $a^b = \sqrt2^{\sqrt2 \cdot \sqrt2} = \sqrt2^{\,2} = 2$입니다. 어느 경우든 성립하니 증명은 끝났습니다. 그런데 이 증명은 두 경우 가운데 어느 쪽이 맞는지, 곧 그런 a가 실제로 무엇인지 알려 주지 않습니다. 고전 수학은 이것을 완전한 증명으로 받아들이고, 직관주의는 받아들이지 않습니다. (답은 나중에 따로 나왔습니다. 1934년의 겔폰트–슈나이더 정리⁠(Gelfond–Schneider theorem)⁠에 따라 $\sqrt2^{\sqrt2}$는 무리수이고, 심지어 초월수⁠(transcendental number)⁠입니다.)

브라우어르가 즐겨 든 예는 원주율⁠(pi)⁠ π의 소수 전개⁠(decimal expansion)⁠였습니다. '0123456789라는 숫자열이 π의 소수 전개 어딘가에 나온다'는 명제를 생각합시다. 찾으면 참임이 증명되지만, 아무리 오래 찾아도 못 찾았다는 사실은 '없다'의 증명이 되지 않습니다. 직접 찾아보세요. 찾을 숫자열: . 소수점 아래 자리까지 찾습니다. 끝까지 찾기

찾은 경우에는 유한한 계산이 곧 증명입니다. 못 찾은 경우에는 할 말이 없습니다. 고전 수학은 그래도 '나오거나 나오지 않거나 둘 중 하나'라고 말하고, 직관주의는 어느 쪽인지 보일 수 있을 때까지 그 말을 하지 않습니다. 브라우어르의 0123456789는 오늘날 컴퓨터가 소수점 아래 170억 자리 너머에서 찾아냈지만, 같은 모양의 질문은 얼마든지 만들 수 있습니다. 예컨대 쌍둥이 소수⁠(twin primes)⁠가 끝없이 많은지는 아직 아무도 모릅니다. 끝없이 찾아야만 하는 이런 명제의 모양은 뒤에 정지 문제⁠(halting problem)⁠에서 다시 나타납니다. 프로그램이 멈추면 멈춘 것을 볼 수 있지만, 멈추지 않는다는 것은 기다려서는 알 수 없습니다.

힐베르트는 이것을 받아들이지 않았습니다. '수학자에게서 배중률을 빼앗는 것은 천문학자에게서 망원경을, 권투 선수에게서 주먹을 빼앗는 것과 같다'(1927). 논쟁은 개인적인 다툼으로 번져, 1928년 힐베르트는 브라우어르를 학술지 『수학 연보』의 편집진에서 내보냈습니다.

괴델의 답. 결말은 뜻밖의 곳에서 왔습니다. 1930년 9월 쾨니히스베르크의 학회에서 스물네 살의 쿠르트 괴델이 짧게 알리고 1931년 논문으로 낸 불완전성 정리⁠(incompleteness theorem)⁠입니다. 자연수의 덧셈과 곱셈을 담고, 무엇이 공리인지 기계적으로 가릴 수 있는 무모순⁠(consistent)⁠ 형식 체계에는 참이지만 그 안에서 증명할 수 없는 문장이 있고, 그런 체계는 자기 자신의 무모순성을 스스로 증명할 수 없다. (공리 목록을 기계적으로 가릴 수 있어야 한다는 조건이 빠지면, 참인 문장을 모조리 공리로 삼는 쓸모없는 체계가 반례가 됩니다.) 힐베르트가 바란 두 가지, 곧 모든 참을 증명하는 완전한 체계와, 그 체계 안에서 할 수 있을 만큼 약한 방법으로 얻는 무모순성 증명은 바란 모습 그대로는 불가능해졌습니다. 공교롭게도 힐베르트는 괴델이 발표한 다음 날 같은 도시에서, 명예시민이 되는 자리의 연설을 '우리는 알아야 한다. 우리는 알게 될 것이다'라는 말로 맺었습니다. 학회에 있던 폰 노이만은 곧바로 결과의 무게를 알아차렸고, 스스로 제2 정리에 이르러 괴델에게 편지를 썼지만 괴델은 이미 그것을 증명해 두었습니다.

그 뒤의 수학은 세 흐름을 조금씩 물려받았습니다. 일하는 수학자 대부분은 공리적 집합론⁠(axiomatic set theory)⁠ ZFC를 바탕으로 삼고 배중률을 자유롭게 씁니다. 1936년 처치와 튜링은 힐베르트의 또 다른 물음, 곧 주어진 논리식이 논리 법칙만으로 증명 가능한지를 기계적으로 판정하는 방법이 있는가(결정 문제⁠, decision problem⁠)에 '없다'고 답하면서, 계산이란 무엇인지를 정의했습니다(튜링 기계⁠(Turing machine)⁠, 람다 계산⁠(lambda calculus)⁠, 처치–튜링 논제⁠(Church–Turing thesis)⁠). 같은 해 독일의 게르하르트 겐첸은 유한한 방법보다 조금 강한 초한 귀납법⁠(transfinite induction)⁠을 쓰면 페아노 산술의 무모순성을 증명할 수 있음을 보여 힐베르트의 계획을 일부 살렸습니다. 직관주의의 '지어 보여야 있다'는 생각은 직관주의 논리⁠(intuitionistic logic)⁠로 다듬어진 뒤, 증명을 프로그램으로 읽는 커리–하워드 대응⁠(Curry–Howard correspondence)⁠을 거쳐 컴퓨터 과학의 전통으로 이어졌고, 오늘날 컴퓨터가 증명의 모든 단계를 검사하는 증명 보조기⁠(proof assistant)⁠의 논리적 바탕 가운데 하나가 되었습니다.

이어지는 곳. 역설과 불완전성과 정지 문제를 한 줄로 꿰는 대각선의 구조는 자기 참조⁠(self-reference)⁠와 대각선과 칸토어의 대각선 논법⁠(Cantor's diagonal argument)⁠에서, 공리가 무엇이고 무모순과 독립⁠(independence)⁠을 어떻게 증명하는지는 공리와 공준⁠(axioms and postulates)⁠에서 볼 수 있습니다. ZFC에서도 결정되지 않는 명제의 예는 연속체 가설⁠(continuum hypothesis)⁠입니다. 참과 거짓의 계산은 불 대수⁠(Boolean algebra)⁠로, 무한을 대하는 태도의 차이는 무한을 다루는 법으로 이어집니다. 브라우어르 자신의 가장 유명한 정리인 고정점⁠(fixed point)⁠ 정리는 공교롭게도 비구성적 증명의 대표입니다. 논쟁의 무대였던 곳으로는 괴팅겐과 20세기 초 케임브리지가 있습니다. 배중률 없이 하는 수학이 어떤 '우주'에서 참인지에 대해서는 범주론⁠(category theory)⁠의 토포스⁠(topos)⁠가 한 가지 답을 줍니다. 토포스 안에서 성립하는 논리는 일반적으로 직관주의 논리입니다. 집합의 세계는 진릿값⁠(truth value)⁠이 참과 거짓 둘뿐이라 고전 논리까지 성립하는 특별한 토포스입니다.