괴델의불완전성정리

요시나가 요시마사 지음, "괴델의 불완전성 정리", 전파과학사. (1993; 일본에서는 1992)

아무것도 모르는 사람도 읽기 쉽게 쓴 책입니다. 그렇다고 수박 겉핥기식 내용은 아닙니다. 수학기초론 논쟁부터 시작해서 페아노 공리나 대각선논법을 알기 쉽게 소개하고, 그런 식으로 한 걸음씩 나아가서 정리의 증명까지 간단히 소개하고 끝납니다. 그리고, '수학에 자신 없는 분은 안 읽으셔도 됩니다'라는 설명으로 수학적 내용은 따로 분리했습니다.

[edit]

괴델의 불완정성 정리(Goedel's Incompleteness Theorem)에 대하여 ¶

수학 잘 하시는 분이 이 정리에 대해 OpeningStatement 한 말씀?

아무리 정교한 수학 체계라도 그 자체로서 완전할 수 없다. 즉 증명불가능한 참인 명제의 예를 들어 괴델이 수학의 환원주의를 까부순 놀랄만한 정리. (환원주의는 힐버트가 수학의 모든 체계를 몇개의 공리로 다 구성하려했던 시도라고 알고 있습니다.) 더 골때리는 것은 증명되지 않은 명제가 증명이 되는지 안되는지 미리 알 수가 없다는 것입니다. 이때매 수학자들은 엄청난 딜레마에 빠져버렸다지요. 골드바흐의추측 같은 경우, 라마누잔(수학이나를불렀다참조)이 아마 거짓이지 싶다고 직관적으로 언급까지 하였으나 아무도 증명을 못하고 있고 또 덤벼들기도 겁내고 있다합니다.

--zetapai

수학사랑에서:

유클리드의 기하학의 공간은 "실제 존재하는 세계" 를 말했습니다. 즉, 기하학의 정리들은 우리 세계에 대한, 실질적인 진리라고 생각되었습니다. 그러나 18세기, 평행선 공준을 부정하고도 모순 없는 기하학이 전개될 수 있다는 것이 밝혀지자 상황은 전혀 달라졌습니다. 그 이후 수학은 공리가 참이라는 "가정"에서 출발하여 전개되는 명제들의 체계이며, 실제 세계와는 관계 없이 전개되는 것이라는 철학이 자리잡았습니다. (이것은 한편으로는, 어떤 대상들이든 공리를 참으로 한다는 것만 밝히면, 그 공리로부터 나온 모든 정리들을 즉각 그 실제적인 대상들에 적용, 참인 명제들을 만들어낼 수 있다는 말이기도 합니다.)

이제 문제는 수학이 절대적인 진리가 아니고 "공리"의 선택에 좌우되는 체계인 이상, 어떤 공리들을 택해야 내부적으로 완벽한 체계가 되는가 하는 것이었습니다. 그래서,

(1) 무모순성 - 공리들이 서로 모순된 명제들 이끌어내지 않을 것 (모순되면 그 체계는 끝장임)
(2) 독립성 - 모든 공리가 다른 공리들로부터 독립적일 것 (독립적이 아닌 공리는 필요 없음)
(3) 절대성 - 그 공리를 참으로 하는 대상이 둘 이상 있을 때 그들은 실질적으로는 동일할 것
(4) 완전성 - 모든 참인 명제를 증명할 수 있고, 모든 거짓인 명제 또한 거짓이라는 것을 증명할 수 있을 것

등등을 추구하게 되었는데, 이중 무모순성은 반드시 만족되어야 할 조건입니다. 독립성은 바람직하지만 꼭 그래야 하는 것은 아닙니다. 절대성은 완전성과 관계 있습니다. 괴델 이전의 수학자들은 내부적으로 모순이 없고 (무모순성) 모든 참인 명제를 증명할 수 있는 (완전성) 체계를 만들기 위해 많은 노력을 기울였습니다. 그런데 괴델은 1931년에,

자연수 체계를 포함하는 무모순인 공리 체계는 절대 완전할 수 없다. 즉, 증명할 수 없는 참인 명제가 반드시 존재한다.

라는, 충격적인 사실을 증명했습니다.(실제로 그런 명제를 만들었습니다.) 이것을 불완전성 정리라고 합니다. 자연수 체계를 포함한다는 말이 나온 이유는 증명에 자연수를 사용했기 때문입니다. 자연수 체계를 포함하지 않으면 완전할 수는 있겠지만 그것은 유리수, 실수 같은 어떤 종류의 수도 포함할 수 없다는 말이므로 별로 쓸모가 없는 이론이 될 것입니다. 어쨌든 이 정리는 수학을 완벽한 논리의 체계로 만들려는 노력을 영원히 잠재우고 말았습니다. 게다가 괴델은 다음과 같은 것도 증명했습니다.

자연수 체계를 포함하는 무모순인 공리 체계는 자신의 무모순성을 증명할 수 없다.

이 또한 충격적인 사실이 아닐 수 없습니다. 완전성은 커녕, 최소한의 조건인 무모순성조차 보장할 수 없다니.

http://www.wikipedia.com/wiki/Goedel's incompleteness theorem

[edit]

일반 독자들이 괴델 정리에 대해 더 찾아볼 수 있는 문헌 ¶

레이먼드 스멀리언, < 이 책의 제목은 무엇인가 >

논리적 퍼즐(특히 "기사/건달", "천사/악마" 류의 퍼즐들)을 모아놓은 책으로, 맨 뒷장은, 논리학의 기법만을 이용하여 직관적으로 괴델수의 아이디어와 괴델 정리의 내용을 이해할 수 있게 되어있다. 레이먼드 스멀리언은 마술사를 직업으로 갖다가 40대가 넘어서 논리학자가 된, 특이한 경력의 소유자로 그의 First-Order Logic은 오랫동안 표준적인 교과서로 쓰이고 있다.

지금은 퍼즐과 함께 하는 즐거운 논리라는 진부하기 짝이 없는 제목으로 바꿔서 나오고 있습니다. -_-;

제프리 & 불로스, < 계산가능성과 논리 >

기초논리학 과저을 끝낸 사람을 위한 표준적인 중급 논리학 및 수리논리학 입문서인 이 책은 논리학 및 계산이론의 중요한 정리들을 간결하게 설명해보이고 있다. 괴델 증명도 포함되어 있다. 다만, 따로 괴델 증명만을 찾아서 읽기에는 어렵다. 기초논리학을 공부한 사람이라고 하더라도 앞에 그려진 "장들간의 의존관계 도표"를 참조하며 앞에서부터 읽어가야 할 것이다.

E. Nagle & J. R. Newman, < Goedel's Proof >

괴델의 증명만을 다루는 짧은 소책자. 역시 "비전문가"들을 위해서 쓰여진 이 책은 형식논리학 및 수학기초론의 배경을 설명하고 간결하게 괴델 증명의 요점을 보여주고 있다. 이 주제에 대해서는 영어로 된 책 중에서 가장 널리 읽히는 "교양서적"이라고 할 수 있다.

Douglas Hofstadter의 <GoedelEscherBach>