괴델의 불완전성
증명할 수 없음을 증명하다
종이 위에 다음과 같은 한 문장을 또박또박 적어 보세요. “이 문장은 수학적으로 증명할 수 없다.”
만약 이 문장이 거짓이라면 증명할 수 있어야 하니 모순이고, 참이라면 증명할 수 없는 참인 문장이 됩니다. 완벽하고 빈틈없다던 수학의 성채 속에 왜 영원히 증명할 수 없는 진실이 숨어 있을까요?
이야기
Unknown authorUnknown author
Public domain · 위키미디어 공용
스무 세기가 열릴 무렵, 수학자들에게 큰 꿈이 있었습니다. 모든 참인 명제를 증명할 수 있는 규칙 체계를 만드는 것이었습니다. 힐베르트가 이끌었습니다.
1931년, 스물다섯 살의 쿠르트 괴델이 그 꿈을 끝냈습니다.
그가 보인 것은 이렇습니다. 산술을 담을 만큼 튼튼한 어떤 체계든, 참인데 그 안에서 증명할 수 없는 명제가 반드시 있습니다.
어떻게 보였을까요? 앞에서 본 거짓말쟁이 문장을 수학 안에서 만들어 낸 것입니다.
그는 먼저 모든 명제와 증명에 번호를 매기는 방법을 고안했습니다. 그러면 「이 명제는 증명할 수 있다」는 말 자체가 수에 관한 명제가 됩니다.
그리고 이런 명제를 지었습니다. “이 명제는 증명할 수 없다.”
증명할 수 있다면 그것은 거짓이므로 체계가 거짓을 증명한 셈입니다. 증명할 수 없다면 그것은 참인데 증명이 없는 명제입니다.
둘째 정리는 더 아픕니다. 어떤 체계도 자기가 모순 없음을 스스로 증명할 수 없습니다.
🚩 그런데 이 증명이 나오기 한 해 전, 힐베르트는 정반대를 선언했습니다. 1930년 쾨니히스베르크에서 그는 라디오 연설을 끝맺으며 말했습니다. 「우리는 알아야 한다. 우리는 알게 될 것이다.」 수학에 풀 수 없는 문제란 없다는 뜻이었습니다.
바로 그 학회에서, 스물넷의 괴델이 자기 결과를 조용히 발표하고 있었습니다. 힐베르트의 그 문장은 지금 그의 묘비에 새겨져 있습니다.
「완벽한 자동 검증 도구는 없다」는 것을 알려 줍니다. 어떤 체계도 자기가 옳음을 스스로 증명할 수 없습니다.
그래서 소프트웨어를 검증할 때는 늘 범위를 정해 검사하고, 「모두 확인했다」고 말하지 않습니다.
계단 넷 — 같은 사실을 네 깊이로
「나는 거짓말쟁이」를 따져 본다
“나는 지금 거짓말을 하고 있다”라고 말하는 사람을 봅니다. 이 말이 참이면 거짓말쟁이가 되고, 거짓이면 참말을 한 셈이 되어 꼬입니다.
수학에서도 자기 자신을 가리키는 문장을 만들 수 있습니다. 아무리 완벽한 규칙을 세워도 그 규칙 안에서는 맞는지 틀린지 결코 증명할 수 없는 문장이 반드시 생깁니다.
문장에 번호를 붙여 보세요
소인수분해가 유일하니 번호에서 문장을 되찾을 수 있습니다.
괴델 수로 수학이 자기를 말한다
25세의 쿠르트 괴델은 1931년 수학계를 뒤흔들었습니다. 모든 수학 기호와 명제, 증명 과정에 고유한 자연수 번호(괴델 수)를 매겨 수학이 자기 자신을 숫자로 서술하게 만들었습니다.
그리고 “괴델 수가 인 명제는 증명 불가능하다”라는 명제 자신의 번호가 정확히 가 되도록 구성했습니다. 이 문장은 참이지만 공리계 안에서 결코 증명할 수 없습니다.
체계가 자기를 말합니다
그러면 체계가 자기 자신을 가리킬 수 있습니다.
자기를 가리키는 문장 만들기
괴델의 제1불완전성 정리는 자연수 산술을 포함하는 무모순적이고 유효한 공리계는 불완전하며, 참이지만 증명할 수 없는 결정 불가능 명제가 존재함을 밝힙니다.
제2불완전성 정리는 한 걸음 더 나아가 그러한 공리계는 자기 자신의 무모순성(Consistency)을 공리계 내부에서 스스로 증명할 수 없음을 증명했습니다. 수학의 모든 참을 기계적 연역으로 증명하려던 힐베르트의 프로그램은 한계를 맞이했습니다.
첫째 정리
게다가 그것을 공리로 추가해도 새로운 것이 또 생깁니다 — 끝이 없습니다.
불완전성 정리
괴델의 불완전성 정리는 수리논리학과 형식주의 수학관의 지형을 영구히 바꾸었으며, 튜링의 계산 가능성 이론과 정지 문제 불능성 증명으로 직결되었습니다.
인간의 이성과 알고리즘적 기계의 본질적 한계를 규명하고, 현대 인공지능 철학과 메타수학, 양자 계산 이론의 인식론적 토대를 형성하는 20세기 지성사의 가장 위대한 금자탑입니다.
둘째 정리
힐베르트가 세운 프로그램이 이 한 줄에 끝났습니다 (1931).
풀어 보기
괴델의 불완전성 정리. 다음 물음에 답하시오.
(1) 산술을 포함하는 형식 체계에서 수학 기호와 논리식, 증명 전체를 고유한 자연수로 일대일 대응시키는 기법의 이름을 쓰시오.
(2) 괴델의 제1불완전성 정리가 선언하는 핵심 결론을 '참인 명제'와 '증명 가능성'의 관계 관점에서 한 문장으로 서술하시오.
(3) 체계의 무모순성을 스스로 증명할 수 없음을 밝힌 정리는 제 몇 불완전성 정리인지 쓰시오.
(1) 괴델 부호화(괴델 수)입니다. (2) 공리계 내에는 참이면서도 증명할 수 없는 명제가 반드시 존재합니다. (3) 제2불완전성 정리입니다.
답과 풀이 보기
(1) 괴델 부호화(괴델 수)입니다.
기호마다 번호를 주고, 소수의 거듭제곱을 이용해 로 묶습니다.
소인수분해가 유일하므로 이 번호에서 원래 식을 그대로 되살릴 수 있습니다.
⭐ 그러면 「이 식이 증명된다」는 말조차 수 사이의 관계가 되어, 산술이 자기 자신에 대해 말할 수 있게 됩니다.
(2) 산술을 담을 만큼 힘이 있고 모순이 없는 체계에는, 참인데도 그 체계 안에서는 증명할 수 없는 명제가 반드시 있습니다.
괴델이 만든 문장은 이렇습니다 — 「이 문장은 증명할 수 없다.」
· 증명된다면 → 자기가 거짓인 것을 증명한 셈이라 모순
· 증명되지 않는다면 → 그 문장이 말한 그대로이니 참
⇨ 참인데 증명할 수 없습니다.
(3) 제2 불완전성 정리입니다.
「어떤 체계도 자기가 모순이 없다는 것을 자기 안에서 증명할 수 없다」
⛔ 스스로 「나는 모순이 없다」고 증명해 보이는 체계가 있다면, 그것은 오히려 이미 모순이 있다는 증거입니다.
1900 년 힐베르트는 「수학의 모든 참을 몇 개의 공리에서 뽑아내자」는 큰 계획을 내걸었습니다. 그의 묘비에는 「우리는 알아야 한다, 우리는 알게 될 것이다」가 새겨져 있습니다.
1931 년, 스물다섯 살 괴델이 그 계획이 이룰 수 없는 것임을 증명했습니다.
⭐ 이것은 수학이 틀렸다는 말이 아닙니다. 어떤 울타리를 쳐도 그 밖에 참이 남는다는 말입니다. 수학에는 끝이 없습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
수학의 한계를 수학으로 증명한 사건입니다.
- 정지 문제 — 튜링이 같은 논법으로 계산의 한계를 보였습니다
- 연속체 가설 — 참도 거짓도 증명할 수 없는 실제 사례입니다
- 오해 주의 — 「수학은 믿을 수 없다」는 뜻이 아닙니다. 「한 체계로 전부를 담을 수 없다」는 뜻입니다
이어지는 장
'이 문장은 거짓이다'라는 역설의 고리를 수학적 기호로 번역해 완벽한 수학 체계란 불가능함을 증명했습니다 — 제126장 의 자기참조 역설이 수학 전체의 기초를 뒤흔든 세기의 정리로 우뚝 섭니다.
영감을 받은 곳
쿠르트 괴델(Kurt Gödel)이 1931년 오스트리아 수학 학술지 『Monatshefte für Mathematik und Physik』에 실은 논문 「『수학 원리』 및 관련 체계의 형식적으로 결정 불가능한 명제들에 관하여」에서 증명했습니다.