괴델의 불완전성 정리

김진섭 대표는 5월 30일(목) 제주대학교 경영정보학과 산업·직무 특화 전문가 특강에 참석, 괴델(Kurt Gödel)의 불완전성 정리가 나온 배경을 소개하고 증명의 핵심 아이디어를 수학과 메타수학(meta-mathematics), 괴델수(Gödel number), 그리고 메타수학의 수학화 3가지로 나누어 설명할 예정입니다. 정리한 슬라이드와 강의록을 미리 공유합니다. 초청해주신 현정석 교수님께 감사드립니다.

요약

1. 18/19 세기 미적분학, 해석학의 발전으로, 수학은 점점 기존의 직관과 상식에서 벗어나 추상화되면서 많은 문제점들이 생겼다.

2. 특히 무한의 개념을 엄밀하게 다룰 필요성이 있었는데, 칸토어(Georg Cantor)는 집합론의 논법으로 무한을 엄밀하게 정의하고 그것들의 크기를 비교하였다.

3. 20세기 수학자들은 집합론을 이용, 수학의 기초를 구성하고 모순이 없는 수학체계를 만들 수 있다는 꿈으로 부풀어 있었으나, 러셀의 역설(Bertrand Russel’s paradox)로 대표되는 “자기언급의 역설”은 집합론의 기초를 위태롭게 하였다.

4. 힐베르트(David Hilbert)는 “자기언급의 역설” 은 수학의 명제와 메타수학(meta-mathematics)의 명제를 구분하지 않아 일어나는 것으로 판단하였으며, 이를 잘 구분하는 공리계를 세심하게 설계할 수만 있다면 모순없는 수학체계를 만들 수 있다고 보았다.

5. 그러나 괴델(Kurt Gödel)은 이 부분을 파고들어 메타수학의 명제를 수학의 명제로 바꾸는 괴델수(Gödel number) 라는 독창적인 아이디어를 제안, 메타수학의 명제를 수학 체계로 갖고 온 후 자기언급의 역설을 보여주었다. 즉, “자기언급의 역설” 을 피하기 위해 아무리 세심하게 공리계를 설계해도 그것을 피할 수는 없다는 것을 증명하였으며, 이것이 불완전성 정리이다.

6. 불완전성 정리로 인해 “참이지만 증명불가능한 명제가 존재” 하고 나아가 “수학의 무모순성을 수학 자체적으로는 증명할 수 없음” 이 증명되어 모순없는 완전한 수학체계의 꿈은 결국 산산조각이 난다.

7. 불완전성 정리를 인간 이성의 한계로만 해석하고 실의에 빠지지 말자. 어떤 기계보다도 더 복잡하고 정교한 인간의 정신구조와 능력을 긍정하며 창조적 이성의 힘을 인정할 때이다.

Slide

아래 슬라이드를 보거나 https://jinseob2kim.github.io/LectureGodel/ 를 클릭하면 볼 수 있다.

강의록

본 강의록은 과거 https://jinseob2kim.github.io/godel.html 에 정리했던 내용을 약간만 수정하였습니다.

서론

괴델의 불완전성 정리에 대한 많은 책들이 시중에 출판되어 있다. 허나 대부분이 역사와 증명의 의미에 치중되어 있고 실제 증명의 아이디어를 설명한 책은 거의 없으며, 있다고 하더라도 외국 서적을 번역하면서 난해한 표현이 많이 나와 이해하기가 어렵다. 이에 본 글에서는 불완전성 정리 증명의 핵심적인 아이디어를 크게 수학(mathematics)과 메타수학(meta-mathematics), 괴델수(Gödel number), 메타수학의 수학화의 3가지로 나누어 설명하겠다. 본 글이 불완전성정리의 아름다움을 느끼는 데 도움이 되길 바란다.

수학(mathematics)과 메타수학(meta-mathematics)

보통 불완전성 정리에 대한 책들에서는 간략하게 증명의 개요만 언급하는데 그것은 아래와 같다. \[G: G는 \:증명불가능하다.\]

만약 \(G\)가 증명 가능하다면 그것은 참이고, 내용은 “\(G\)는 증명 불가능하다.” 므로 모순이다. 따라서 \(G\)는 증명 불가능하며, \(G\)의 내용은 “\(G\)가 증명 불가능하다”는 것이므로 참이다. 따라서 \(G\)는 참이지만 증명불가능한 명제라는 것이다. 이 설명을 보고 고개를 끄덕 인 후 증명이 끝난 것 아닌가? 라는 생각을 할 수도 있을 것이다. 그러나 명제 내부에 명제 자신을 언급한 순환논리부분을 해결하지 않으면 안되고 사실 불완전성정리의 핵심부분도 이 부분이며 수학의 명제와 메타수학의 명제를 구분하는 것이 이해의 시작이 된다.

수학 명제와 메타수학 명제의 차이점

아주 간단한 수학 명제 하나를 살펴보자. \[1+1=2\]

이 표현은 수학에 속한 표현이다. 이제 다음 명제를 살펴보면 \["1+1=2"는 \:수학\: 명제이다.\] 이 진술은 앞에 나온 수학명제에 대해 무엇인가를 주장하고 있으며 따라서 수학이 아니라 메타수학의 명제라고 할 수 있다. 비슷하게 “\(x\)는 변수이다”, “\(x=1\)은 방정식이다” 들도 수학 명제가 아니라 메타수학의 명제이다. 수학과 메타수학을 구별하는 것은 몇 번을 강조해도 지나치지 않은데 이 구별에 소홀한 것이 수많은 역설이 만들어지는 이유이기 때문이다. 힐베르트를 포함한 당시의 수학자들은 이를 잘 구별하면 역설을 제거할 수 있다고 보았다. 이제 다시 처음 식을 살펴보자. \(G\)가 수학명제라면 “\(G\)는 증명불가능하다” 는 수학의 명제가 아니라 메타수학의 명제이므로, 이것이 수학명제인 \(G\)가 될 수는 없다. 따라서 자기언급의 역설은 발생하지 않는다.

그러나 괴델은 이 부분을 파고들어 메타수학의 명제를 수학의 명제로 바꾸는 괴델수(Gödel number) 라는 독창적인 아이디어를 제안, 메타수학의 명제를 수학 체계로 갖고 온 후 자기언급의 역설을 보여주었다. 괴델수부터 차근차근 알아보도록 하자.

괴델수(Gödel number)

괴델수는 모든 기호, 변수, 명제, 명제묶음(증명)들에 유일한 숫자를 부여하는 것인데 몇가지 예를 들어보면 다음과 같다.

상항기호

기호	괴델수	의미
\(\sim\)	1	아니다
\(\vee\)	2	또는
\(\supset\)	3	\(\cdots\)라면 \(\cdots\)다
\(\exists\)	4	\(\cdots\)이 존재한다
\(=\)	5	같다
0	6	영(0)
s	7	바로 다음 수
(	8	왼쪽 괄호
)	9	오른쪽 괄호
,	10	쉼표
\(+\)	11	더하기
\(\times\)	12	곱하기

위의 표에 나와있는 기호들을 상항기호라고 하며, 이와 대응되는 개념은 변항(variable)기호인데 숫자 변항, 문장 변항, 술어 변항으로 나눌 수 있다. 숫자 변항에는 12보다 큰 소수, 문장 변항에는 12보다 큰 소수의 제곱수, 술어변항에는 12보다 큰 소수의 세제곱수를 부여하게 되며 예는 아래의 표와 같다.

변항기호

	변항	괴델수	대입 예
숫자변항	\(x\)	13	0
	\(y\)	17	\(s0\)
	\(z\)	19	\(y\)
문장변항	\(p\)	\(13^2\)	\(0=0\)
	\(q\)	\(17^2\)	(\(\exists\) x)(\(x=sy\)): \(y\)의 다음 수 \(x\)가 존재한다.
	\(r\)	\(19^2\)	\(p\supset q\)
술어변항	\(P\)	\(13^3\)	\(P(x)\): \(x\)는 소수이다.
	\(Q\)	\(17^3\)
	\(R\)	\(19^3\)

이제 문장 (\(\exists x\))(\(x=sy\)) 를 살펴보자. 이것은 \(y\) 다음 수가 존재한다고 읽으며, 기본기호 하나하나의 괴델수를 살펴보면 8, 4, 13, 9, 8, 13, 5, 7, 17, 9이고 문장 전체의 괴델수는 다음과 같이 소수를 이용하여 표현한다. \[2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{17} \times 29^9\]

마찬가지로 증명에 대해서도 괴델수를 부여할 수 있는데 예를들어 증명이 두 서술로 되어 있고 각 서술의 괴델수가 \(m\)과 \(n\)이라면 증명의 괴델수는 \(2^m \times 3^n\) 으로 표현한다. 이런식으로 모든 수학적 표현에 대해서 겹치지 않고 유일하게 괴델수를 부여할 수 있다. 한가지 예를 더 들면 괴델수 243,000,000은 \(2^6 \times 3^5 \times 5^6\)으로 소인수분해 되며 지수부분인 6,5,6은 각각 0, \(=\), 0에 대응되므로 결국 \(0=0\)이라는 수학명제를 나타내게 된다.

메타수학의 수학화

괴델은 괴델수를 이용하여 메타수학의 명제를 수학의 명제로 바꾸는 데 성공하였는데 간단한 예를 들어보겠다.

\[\sim(0=0)\]

는 “0은 0이 아니다.” 라는 단순한 수학 명제인 반면

\[\text{수학 명제} "\sim(0=0)" \text{의 첫 번째 기호는 틸드}(\sim) \text{이다}.\]

는 수학명제가 아니라 메타수학의 명제이다. 그런데 이 메타수학의 명제는 적당한 과정을 거치면 수학명제로 바꿀 수 있다. 편의상 \("\sim(0=0)"\)의 괴델수를 \(a\)라고 하고 위의 상항기호 표에서 \("\sim"\)의 괴델수가 1임을 기억하자. 그렇다면 첫 번째 기호가 \("\sim"\)이라는 것은 곧 \(a\)를 소인수분해했을 때 제일 작은 소수인 2의 지수가 1임을 의미하게 되고 메타수학의 명제는

\[2 \text{는 } a \text{의 인수이지만, } 2^2 \text{ 은 } a \text{의 인수가 아니다}.\]

와 같이 수학명제로 바뀌게 된다. 기호로 표현하기 위해 표현을 바꾸면 “\(y=z\times 2\)인 \(z\)가 존재하고, \(y=z\times 2 \times 2\)인 \(z\)는 존재하지 않는다.” 가 되며 실제로 이를 기호로 표현하면 다음과 같다.

\[(\exists z) (sss\cdots sss0=z\times ss0) \cdot \sim(\exists z) (sss\cdots sss0=z\times (ss0 \times ss0))\] (\(sss\cdots sss0\)에서 \(s\)는 정확히 \(a\)번 나타난다.) 이와 비슷한 방법으로 모든 메타수학의 명제를 괴델수를 이용하여 수학의 명제로 바꿀 수 있다.

불완전성 정리

이제 불완전성 정리를 천천히 이해해보자. Dem/dem과 Sub/sub의 개념을 정의한 후 증명의 핵심 아이디어로 들어가 보겠다.

Dem

dem은 증명을 뜻하는 demonstration의 약자로 dem(\(x\), \(z\))은

\[\text{괴델수 } x \text{를 가진 문장묶음이 괴델수 } z \text{를 가진 명제의 증명이다}.\]

의 축약표현으로 정의한다. 예를 들어 “피타고라스 정리 증명”의 괴델수가 \(m\)이고 “피타고라스 정리”의 괴델수가 \(n\)이라면 dem(\(m\), \(n\))이라고 쓸 수 있는 것이다. 한편, Dem(\(x\), \(z\))은 \(x\)와 \(z\)의 관계 dem을 형식적 표기법으로 표현하는 형식문으로 정의한다.

Sub

Sub은 치환 혹은 대입을 의미하며 소문자로 표현한 sub(\(x\),17,\(x\))는

\[\text{괴델수 } x \text{를 가진 문장에 등장하는} \textbf{ 변수 } y \textbf{들에 전부 숫자 } x \textbf{를 대입} \text{해서 만들어진 명제의 괴델수}\]

로 정의한다(17은 \(y\)의 괴델수임을 기억하자). 한 편, \(s\)를 대문자로 표시한 Sub(\(x\),17,\(x\))는

\[\text{괴델수가 아닌 }\textbf{명제 그 자체}\]

로 정의한다. 이해를 돕기 위해 \(2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{17} \times 29^9\) 를 다시 살펴보겠다. (\(\exists x\))(\(x=sy\)) 는 앞서 설명했듯이 “\(y\) 다음 수가 존재한다” 고 읽을 수 있으며, 그 괴델수를 \(k\)라 하면

\[k=2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{17} \times 29^9\]

가 된다. 이제 \(y\)대신 \(k\)를 대입한다면 수정된 명제는 (\(\exists x\))(\(x=sss \cdots sss0\))이 되고(\(s\)는 \(k+1\)번 연속됨), \(s\)의 괴델수가 7임을 고려하면 \(k\)를 대입한 명제의 괴델수는 \(y\)부분에 해당되는 \(23^{17}\)부터 \(s\)로 바뀌어 아래의 식과 같이 된다.

\[2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{7} \times 29^7 \times 31^7 \times 37^7 \times \cdots (P_{k+10})^9\] (\(P_{k+10}\): \(k+10\)번 째 소수)

얼핏 보기에 문장의 괴델수를 문장 그 자체에 대입한다는 것이 순환논리같은 느낌을 주는데 이것이 바로 괴델의 핵심적인 아이디어 중 하나이다. 이제부터 본격적인 증명의 내용으로 들어가기로 하자.

불완전성 정리

불완전성 정리의 증명은 “괴델수 \(z\)를 가진 명제는 증명불가능하다”라는 메타수학의 명제를 수학의 명제로 바꾼 후, 이 명제의 특별한 경우가 증명될 수 없다는 것을 보이는것으로 이루어진다. 이제 다음의 형식문을 살펴보자.

\[\sim(\exists x)\text{Dem}(x,\text{Sub}(y, 17, y))\]

이 수학의 형식문은 “Sub(\(y\) ,17, \(y\)) 의 증명은 존재하지 않는다, 즉 증명불가능하다”는 메타수학적 의미를 갖는다. 이 형식문의 괴델수를 \(n\)이라 하고, 형식문에 포함된 변수 \(y\)를 숫자 \(n\)으로 바꾼 형식문 \(G\)를 살펴보자.

\[\text{G}: \sim(\exists x)\text{Dem}(x,\text{Sub}(n, 17, n))\]

\(G\)는 변수가 포함되어 있지 않으므로 수학명제이며, 이것의 메타수학적 의미를 살펴보면 “괴델수 sub(\(n\), 17, \(n\))을 가진 명제는 증명 불가능하다.”이다. \(G\)의 괴델수를 \(g\)라고 하고 \(g\)는 어떤 숫자일지 생각해보자. 놀랍게도 \(g=\text{sub}(n, 17, n)\)임을 알 수 있다. \(G\)는 괴델수 \(n\)을 가진 형식문에서 \(y\)에 숫자 \(n\)을 대입하여 만든 명제이므로, 이것의 괴델수 \(g\)는 정확히 sub(\(n\), 17, \(n\))의 정의와 일치하게 된다. 이제 \(G\)의 메타수학적 의미를 다시 살펴보면 “괴델 수 \(g\)를 가진 명제는 증명 불가능하다.”이고 즉, “\(G\)는 증명 불가능하다”는 의미가 된다. 맨 처음으로 돌아가면, \(G\)는 참이지만 증명 불가능한 명제가 되어 불완전성의 정리가 증명된다.

마치며

필자는 고등학생때부터 괴델의 불완전성정리를 이해해보려고 괴델의 논문원본도 찾아보고 여러 교양서적을 많이 읽어보았었다. 그러나 논문을 다 보는것은 이해하기가 어렵고 교양서적은 겉핥기식으로만 나와있어서 최근까지도 증명의 핵심을 이해하지 못했었는데 출판사 승산에서 나온 괴델의 증명을 읽으면서 한층 이해수준을 올릴 수 있었다. 이 책은 외국서적을 번역한 것으로 번역하면서 생소한 단어와 표현들이 많이나와 읽기가 어려운 부분이 있어 이번기회에 잘 풀어서 설명해볼 목적으로 글을 쓰게 되었다. 본 글이 논문과 교양서적 사이에서 가교 역할을 하여 불완전성 정리를 이해하는데 도움이 되길 기대한다.

참고문헌

1. 괴델, 에셔, 바흐 : 영원한 황금 노끈 / 지은이: 더글러스 호프스태터 ; 옮긴이: 박여성, 안병서

2. (호프스태터가 서문을 쓰고 개정한) 괴델의 증명 / 지은이: 어니스트 네이글, 제임스 뉴먼 ; 옮긴이: 곽강제, 고중숙

3. 괴델 불완전성 정리 / 지은이: 요시나가 요시마사 ; 옮긴이: 임승원