불완전성 정리

1. 개요

2. 정리

2.1. 주요 개념

3. 쉬운 증명

4. 증명 아이디어

4.1. 제1정리

• 식 '[math(Dem(x, y))]': '괴델수가 [math(y)]인 명제의 증명은 괴델수가 [math(x)]이다'
• 예. '[math(\exists x Dem(x, y))]':' '괴델수가 [math(y)]인 명제의 증명이 존재한다'
• 함수 [math(sub(n, k, n))]: 괴델수가 [math(n)]인 식의 변항 중 괴델수가 [math(k)]인 변항에 ([math(n)]을 나타내는 기호인) '[math(n)]'을 대입해서 얻은 식의 괴델수[주의]
• 예. 식 '[math(\exists x (x=y))]'의 괴델수가 [math(m)]이라고 하고, '[math(y)]'의 괴델수가[math(j)]라고 하자. [math(sub(m, j, m))]는 '[math(\exists x (x=y))]'에서 '[math(y)]'를 '[math(m)]'으로 교체한 식의 괴델수다.[주의]

• [math(G)]: '[math(\neg ∃xDem(x, sub(n, 17, n)))]'
• 의미: '괴델수가 [math(sub(n, 17, n))]인 식의 증명은 존재하지 않는다'

4.2. 제2정리

• '[math(\exists y \neg \exists x Dem(x,y))]'
• 의미: '그 증명에 해당하는 괴델수 [math(x)]가 없는 식의 괴델수 [math(y)]가 존재한다.'

5. 반응 및 영향

5.1. 수학 및 그 사례

• ZFC 공리계[14]의 선택공리(Axiom of Choice) 자신과 이를 이용해 증명한 정리들은 무모순하지만 다른 공리를 이용해서 참인지 거짓인지 증명할 수 없다.

• 연속체 가설[15]: 모든 무한집합의 원소수(기수)는 [math( \aleph_n )]꼴로 표현 할 수 있다 여기서 [math( 2 ^{\aleph_0} = \aleph_1 )] 이 성립하겠느냐는 것이 연속체 가설이고, 일반화된 것은 [math( 2^{\aleph_N} = \aleph_{N+1} )] 이 성립하지 않을까 하는 일반연속체가설. 좀 더 자세한 것은 연속체 가설과 초한기수 문서 참조.

• Word problem for groups[16]

• Whitehead[17] problem: torsion-free, total separable group 은 free 인가[18]

• 네이처 기사 번역 및 설명(불완전성 정리가 적용되는 물리학 문제.)

5.2. 계산 이론

• 그 공리계 내부의 자료만으론 기계적인 유한한 절차로 참, 거짓을 결정/증명할 수 없는 명제가 반드시 있다. 그렇지 않으면 그 공리계에는 모순이 있다.

5.3. 철학

6. 대중적 인식

• 당시에는 증명이 난해하다기보다는, 논리체계를 '이용하는' 수학이 그런 논리체계 자체를 수학적 대상으로 환원하여 연구한다는 부분을 잘 이해하지 못하여 대부분의 비수학자들은 그저 논리와 이성으로 이 세상을 완전히 설명할 수는 없다는 정도로 받아들일 수도 있을 것 같다, 는 식으로 이해했고, 지금도 비전공자들은 막연히 그 정도로만 이해한다.[23]
• 몇몇 철학자들은 '우리가 진리에 결코 도달할 수 없다'는 뜻으로 해석하기도 한다. 미셸 드 몽테뉴, 프리드리히 니체가 했던 주장의 개정판인 셈인데, 물론 잘못된 해석이다. 수학의 위치를 생각해 보았을 때 철학적으로 중요한 기획 하나가 실패를 겪었다는 것은 사실이지만, 그 이외의 영역에서까지 이를 확장하는 것은 주의해야 한다. 대부분 이런 주장들은, 불완전성 정리를 제대로 이해해서 확장했다기보다는 그냥 좋은 소재(같은 예로는 상대성 이론, 양자역학)를 물었을 뿐이다. 불완전성 정리를 이용해서 개드립을 치던 사람들은 나중에 앨런 소칼에게 걸려서 박살이 났다. 원래 진리에 결코 도달할 수 없다는 주장의 기원은 소피스트가 자기네끼리 투닥투닥하던 시절까지 거슬러 올라간다. 진리에 결코 도달할 수 없다는 것이 아니라 진짜 진리에 도달한다해도 그게 진리가 맞는지 증명할 수 없을 수도 있다고 이해하면 빠를 것이다.
• 문학에서는 어쨌거나 뜻의 난해함과 불완전성이라는 단어가 주는 포스트모던적인 강렬함 덕분에 억지를 진실로 진실을 억지로도 재정리 할 수 있는 논리체계라고 오해를 받는데, 괴델의 정리는 '참으로 증명된 정리'의 존재를 부정하지도 않고, 참인 명제를 거짓이라고 선언하지도 않는다.
• 조금 더 일찍 나온 불확정성 원리가 주는, 세상은 확률론적으로 이루어져 '참과 동시에 거짓이다'라는 식의 오해가 쓰기 더 편리하기 때문에 더 이상은 등장하지 않을 듯하다.
• 사실 오일러-가우스 시절까지의 수학에서는 단순히 주어진 수식의 연산 정도만이 관심사였고, 해당 '체계' 및 '시스템 자체'의 엄밀함에 신경쓰기 시작한 것은 코시라는 수학자가 등장한 이후부터였다.[24] 희한하게도 수학의 전체적인 시스템을 엄밀하게 증명하는 과정을 보면 뭔가가 안 된다는 결론들이 많았다. 갈루아는 5차 이상의 방정식의 해를 구하는 공식은 없다는 결론을 내었고, 위상수학에서는 조르당-쇤플리스 정리[25]가 3차원 이상의 공간에서는 성립되지 않음이 밝혀졌다. 측도론에서는 3차원 이상 실수공간의 임의의 부분집합의 넓이를 구하는 함수는 존재하지 않음[26]을 보이고, 더해서[27], 바나흐-타르스키 역설에서는 선택공리[28]를 이용해 순수하게 집합의 분할과 공간이동[29] 만의 방법을 사용해서 3차원 실수공간의 서로 다른 부피를 가진 공 2개의 조각들이 모두 서로 대응함을 보여준다.[30] 위에서 언급한 wording problem도 그 한 예시로 볼 수 있겠다. 그래도 대수학에서의 다양한 분류(classification) 문제들이 풀렸고 측도론을 기반으로 해석학이 함수해석학 등 세부 분야를 통하여 눈부신 발전을 이루어 냈으며 위상수학 등을 통하여 호모토피, 호몰로지, 더 나아가 대수기하학 등이 융성한 것을 보면 이러한 방법론이 꽤 유용하면서도 아직 할 일이 많다는 즉 돈줄이 아직 안 끊겼다는 것을 짐작할 수 있을 것이다.
• 괴델의 불완전성 정리 역시 이 연장선상에서 수학 그 자체의 불완전성을 보인 것이다. 현대수학은 매우 확고한 기초를 가진듯 보이지만, 사실 내부사정을 조금 들여다보면 이래저래 '의미적'으로도 위의 바나흐-타르스키 역설 같은 여러 가지 역설이 존재하기 때문에 공격받는 부분이 많고, 그 외에도 철학적으로 비구성적 오브젝트를 허용한데 대한 입장차이 등으로 인하여 공격받는 부분이 많아 '물 바깥에서 보기엔 우아하고 아름답지만, 안에서는 열심히 다리를 허우적대는 백조'와 같은 모양새를 띠고 있다. 괜히 러셀이 '수학의 원리'같은 책을 낸 것이 아니다.
• 골드바흐 추측과 얽혀서 "어쩌면 골드바흐의 추측도 저 "참이면서도 증명할 수 없는 명제"(참 거짓을 증명할 수 없는 문제)가 아닐까?" 하는 것을 써먹은 소설 <사람들이 모두 미쳤다고 말한 외로운 수학 천재 이야기>가 있다. 아직까지 증명도 반증도 안 되니 참으로 간주하는 것. 페르마의 마지막 정리도 증명되기 전에는 비슷한 의심을 하는 사람들이 있었다.
• 읽어보면 좋은 책으로 < 괴델, 에셔, 바흐>, <불완전성> 등이 있다. 참고로 <괴델, 에셔, 바흐>는 구판 한국어 번역본의 퀄리티는 악명이 높았지만, 2017년에 나온 개정판은 역자가 바뀌면서 번역의 질이 압도적으로 높아졌다.