Incompleteness Theorem

수리논리학에서 불완전성정리는 1930 년에 Kurt Gödel 이 증명하여 두차례에 걸쳐 발표되었다. 단순화 시키면, 첫 번째인 제 1 불완전성 정리는 다음과 같다.

기초적인 산술을 충분히 강력하게 허용하는 어떤 무모순의 수학 형식 시스템에서도, 그 시스템내에서 증명될 수도 없고 반증될 수도 없는 자연수에 대한 문장을 만들 수 있다. (in any consistent formal system of mathematics sufficiently strong to allow one to do basic arithmetic, one can construct a statement about natural numbers that can be neither proven nor disproven within that system.)

이러한 맥락에서, 수학의 형식 시스템은 공리의 recursive set 을 가지는 공리계이다. 마찬가지로 그 시스템의 정리들은 튜링머신에 의해 생성될 수 있다. 그 시스템에서 증명되거나 반증될 수 없는 문장은 실제로 자연수에 대해 주장하는 것을 가진다는 의미에서 더더욱 참이다 (The statement which cannot be proven nor disproven in the system is furthermore true in the sense that what it asserts about the natural numbers in fact holds). 그 시스템이 참인 문장을 증명하는데 실패한다면  그것은 불완전 (incomplete) 이라고 말해진다. 달리 말하면, 괴델의 제 1 불완전성 정리는 어떤 충분히 강력한 수학 형식 시스템도 inconsistent 이거나 incomplete 하다는 것이다.

괴델의 제 2 불완전성 정리는 시스템 자체내에서 최초의 증명을 형식화하여 증명된 (proved by formalizing part of the proof of the first within the system itself) 것으로서 다음과 같다.

어떠한 충분히 강력한 무모순 시스템도 그 자신의 무모순성을 증명할 수는 없다. (any sufficiently strong consistent system cannot prove its own consistency)

이것은 Hilbert 의 두 번째 문제 ("수학은 모든 수학적 진리여부가 유도될 수 있는 공리의 consistent set 으로 환원될 수 있다" 는 것을 증명하는 문제) 에 대한 답변이다. ............... (Wikipedia : Gödel's incompleteness theorems)

컴퓨터는 세상의 모든 문제를 풀 수 있다고 생각하십니까? 아마도 당장 부정적인 대답이 돌아올 법 합니다. 그렇습니다. 우리가 일상 생활에서 끊임없이 만나는 정서적 문제가 컴퓨터에 의해 해결될 수 있으리라고는 생각되지 않습니다. (설령 먼 미래라고 하더라도 말이죠.) ...... 그러면 문제의 정의를 다소 제한해 봅시다. 수학적으로 엄밀히 기술되는 문제들은 예외없이 컴퓨터에 의해 풀 수 있을까요? 질문이 이렇게 되면 앞서의 질문보다는 대답하기가 훨씬 신중해질 것 같습니다. ....... 답을 말씀드리지요. "풀 수 없습니다!" 이러한 결론이 내려지기까지의 역사를 살펴보는 것이 아마 도움이 될 것입니다. ...... 컴퓨터 능력의 한계에 관한 많은 연구 결과는 20 세기초에 수리논리학 (mathematical logics) 분야에서 수행된 것입니다. 따라서 우리가 지금 사용하는 컴퓨터의 능력은 컴퓨터가 발명되기 전부터 충분히 예견되고 있었습니다. ..... 20 세기가 시작될 무렵, 수학자 Hilbert 는 어떤 수학적인 명제가 입력으로 주어질 때 이의 참과 거짓을 알아내는 알고리즘을 찾고자 하는 일종의 `수학 자동화' 연구를 시작하였습니다. 그후 1931년에 이 방면의 연구에서의 금자탑이라고 할 수 있는 쿠르트 괴델 (Kurt Godel) 의 논문이 발표되었습니다. 즉 그러한 알고리즘은 존재할 수 없음을 증명한 유명한 `불완전성 정리(Incompleteness Theorem)' 를 발표한 것입니다. 그의 결과를 간단하게 설명하면, 모든 수학적인 논리 체계에는 그 논리 자체로써는 증명할 수 없는 참인 명제들이 존재한다 는 것입니다........ ( 김도형 )

term :

불완전성 정리 (Incompleteness Theorem)   수학 (Mathematics)   논리학 (Logic)   수리논리학 (Mathematical Logic)   계산가능성 이론 (Computability Theory)   완전성 정리 (Completeness Theorem)   David Hilbert   Kurt Gödel

site :

인공지능과 컴퓨터의 한계 : 김도형

paper :

괴델의 정리 : Rudy Rucker, 김량국 옮김, 열린책들

괴델 불완전성정리에서 유도 안될 수도 있는 명제 (A Proposition also Non-derivable from Goedel's Incompleteness Theorem) : 김상문, 철학연구회, 1987

타르스키 정리, 처치 정리, 그리고 괴델 정리 : 김영정, 한국철학회, 1987

괴델의 불완전성정리와 수학적 진리 : 김영남, 김용국, 한국수학사학회, 1984

괴델의 불완전성정리 : 증명된 신화? (Godel`s Incompleteness Theorem : A Proven Myth?) : 홍성기, 한국논리학회, 2002

불완전성 정리

video :

확실한 수학, 불완전한 수학 : 윤태웅, 2013/06/01