불완전성 정리
1. 개요
incompleteness theorems
간단히 설명하자면 우리가 사용하고 있는 수학 체계가 증명할 수 없는 논리를 가진다는 것이다.
쿠르트 괴델이 1931년에 발표한 정리이다. 19세기 해석학(수학)의 발달 및 비유클리드 기하학의 본격적인 등장으로부터 촉발된 '''수학 기초론'''의 대표적인 성과로서, 현대 논리학의 토대가 되는 동시에 20세기 수학 및 철학, 컴퓨터과학 등 많은 분야에 큰 영향을 미쳤다.
술어 논리는 일상적으로 사용되는 명제 논리라고 불리는 논리를 확장한 것으로 기호를 사용하여 논리를 표현한다. 괴델은 이런 1차 술어 논리에 대한 '''완전성 정리'''를 1929년 23세 때 제출한 박사논문에서 증명했다. 불완전성 정리는 2년 후 25세에 증명한 것.
비슷한 이름의 개념으로 하이젠베르크가 발견한 물리학의 불확정성 원리, 케네스 애로우가 증명한 경제학의 불가능성 정리, 언어철학에서 콰인이 제시한 번역 불확정성 논제 그리고 수리 논리학에서 타르스키가 증명한 타르스키의 정의 불가능성 정리가 있다. 헷갈리지 말자.
2. 정리
불완전성 정리는 "제1 불완전성 정리"와 "제2 불완전성 정리"라는 두 정리를 아우르는 말이다.
페아노 공리계란 우리가 사용하고 있는 자연수에 관한 공리를 말한다.$$1+1=2$$라는 것도 이를 통해 정의된 것이다. 그런데 이 공리를 포함하는 체계가 모순이 없다면 참인데 증명할 수 없는 명제가 존재한다는 것이다.
2.1. 주요 개념
수리 논리학에서 쓰이는 "참", "증명가능성", "귀결" 등의 개념은 자칫 오해하기 쉽다. 오해를 방지하기 위하여 관련 개념을 약술하자면 다음과 같다:
"불완전성 정리"에서 말하는 '''"완전성(completeness)"'''이란 '''"건전성(soundness)"'''과 대비되는 성질이다.[1] 임의의 형식 체계 P, 명제 집합 Γ, 그리고 명제 φ에 관하여 이들 개념은 다음과 같이 정의될 수 있다:
이때 "증명가능성"과 "논리적 귀결"은 각각 다음과 같이 정의된다:* P의 '''건전성''': P에서 Γ로부터 φ가 증명가능하다면, P에서 φ는 Γ의 논리적 귀결이다.
* P가 건전하면 P는 무모순적이다.
* P의 '''완전성''': P에서 φ가 Γ의 논리적 귀결이라면, φ가 P에서 타당하다면, P에서 명제 φ는 Γ로부터 증명가능하다.
명제 논리는 건전하며 완전하다. 더욱이 명제 논리의 경우 임의의 Γ와 φ에 대하여 φ가 Γ의 논리적 귀결인지 여부를 유한번 단계 내에 판단할 수 있게끔 해주는 절차가 있으므로 결정가능하다.* P에서 φ는 Γ로부터 '''증명가능하다''' iff Γ의 원소들 및 P의 공리들에 P의 도출 규칙을 유한번 적용하여 φ를 얻을 수 있다.
* P에서 φ는 Γ의 '''논리적 귀결이다''' iff P에서 Γ의 모든 원소들이 참인 경우 φ도 반드시 참이다 iff Γ의 모든 원소들이 참인 임의의 모형에서 φ는 참이다.
1차 술어 논리는 건전한 동시에 완전하지만, 결정가능하지는 않다. 따라서 만약 φ가 Γ의 논리적 귀결이라면 그 사실은 유한 번 단계 내에 판단할 수 있지만, φ가 Γ의 논리적 귀결이 아니라면 그럴 수 없다. 1차 술어 논리의 완전성 또한 괴델이 증명한 것이다.
자연수 산술을 가능케 하는 페아노 공리계를 포함하는 형식 체계는 1차 논리보다 강력하다. 괴델의 불완전성 정리는 이런 논리 체계가 '''완전성'''을 띠지 않는다는 점을 보여주는 것이다. 곧 설령 참이라 한들 그에 대한 증명도, 그 부정에 대한 증명도 불가능한 문장들이 있다는 것이다. 밑에서도 나오겠지만 연속체 가설을 비롯한 몇몇 명제들이 바로 그 사례다.
3. 증명 아이디어
아래 증명 아이디어는 어니스트 네이글과 제임스 뉴먼의 고전적인 대중서, 『괴델의 증명』에서 따온 것이다.
3.1. 제1정리
제1불완전성 정리 증명의 실질적인 첫 단계는 임의의 식을 자연수로 번역하는 절차를 만드는 것이다.[2] 그 방식은 다양하나, 요체는 모든 식 각각에 고유한 자연수를 부여하는 것이다. 이처럼 그 식과 일대일로 대응하는 자연수를 그 식의 괴델수(Godel number)라고 부른다.
산술식 '1+0=1'를 예로 들어보자. 이 식에 등장하는 기호의 유형은 '1', '+', '0', '='로 네 가지다. 이때 각 기호의 유형마다 고유한 자연수를 부여하자. 그 예는 다음과 같다.[3]
이때 식 '1+0=1'은 5개의 기호로 이루어져 있으므로, 그 길이가 5라고 할 수 있다. 그 길이에 해당하는 최초의 소수들, 즉 가장 작은 소수 5개는 2, 3, 5, 7, 11이다. 이 소수들은 각 기호의 위치를 나타낸다. 이에 의거하여 각 위치마다 놓인 기호는 다음과 같이 지수를 사용해 표현가능하다.
예컨대 '1+0=1'의 첫 자리에 나타나는 '1'은 24= 16으로 번역가능하다. 그리고 이렇게 번역된 각 자연수들을 다 곱함으로써 식 전체를 그 괴델수로 번역할 수 있다. 이를테면 '1+0=1'의 괴델수는 24 × 35 × 53 × 76 × 114 = 837134518374000이 된다.(위치를 나타내는 소수)(기호 유형에 상응하는 괴델수)
이처럼 임의의 식에 상응하는 괴델수를 계산해낼 수 있다. 그리고 똑같은 원리에 의거하여 여러 식들의 나열, 이를테면 증명에 해당하는 괴델수 또한 계산하는 것이 가능하다.
이를 토대로 다음과 같은 개념을 정의하자:
- 식 '$$Dem(x, y)$$': '괴델수가 $$y$$인 명제의 증명은 괴델수가 $$x$$이다'
- 예. '$$\exists x Dem(x, y)$$':' '괴델수가 $$y$$인 명제의 증명이 존재한다'
- 함수 $$sub(n, k, n)$$: 괴델수가 $$n$$인 식의 변항 중 괴델수가 $$k$$인 변항에 ($$n$$을 나타내는 기호인) '$$n$$'을 대입해서 얻은 식의 괴델수[주의]
- 예. 식 '$$\exists x (x=y)$$'의 괴델수가 $$m$$이라고 하고, '$$y$$'의 괴델수가$$j$$라고 하자. $$sub(m, j, m)$$는 '$$\exists x (x=y)$$'에서 '$$y$$'를 '$$m$$'으로 교체한 식의 괴델수다.[주의]
- $$G$$: '$$\neg ∃xDem(x, sub(n, 17, n))$$'
- 의미: '괴델수가 $$sub(n, 17, n)$$인 식의 증명은 존재하지 않는다'
그러므로 $$G$$의 의미는 '괴델수가 $$g$$인 식의 증명은 존재하지 않는다'라고도 볼 수 있다. 그런데 괴델수가 $$g$$인 식은 바로 $$G$$다. 따라서 '''$$G$$의 의미는 '$$G$$의 증명은 존재하지 않는다'는 것이다.''' 먼저 $$G$$의 증명이 존재한다고 가정해보자. 그러면 명제 $$G$$는 거짓인데, 이로부터 $$G$$의 부정의 증명 또한 있음을 보일 수 있다. 하지만 이는 무모순성을 위반한다.[4] 역으로 명제 $$G$$의 부정에 대한 증명이 존재한다고 가정할 경우에도 무모순성이 위반된다.[5]
즉 대우를 취할 경우, 주어진 증명 체계가 무모순적이라면 $$G$$와 그 부정 둘 중 어느 것도 증명할 수 없으므로 불완전하다는 점이 도출된다. 그리고 $$G$$의 의미상 $$G$$는 참이 된다. 따라서 참이지만 증명할 수 없는 명제가 있다.
3.2. 제2정리
모순적인 공리계로부터는 어떠한 명제든지 증명할 수 있으므로, 무모순적인 공리계는 증명불가능한 명제가 있는 공리계다. 따라서 '페아노 공리계는 무모순적이다'라는 문장은 괴델수 번역 등을 통해 페아노 공리계 안에서[6] 다음과 같은 형태로 기술될 수 있다.
- '$$\exists y \neg \exists x Dem(x,y)$$'
- 의미: '그 증명에 해당하는 괴델수 $$x$$가 없는 식의 괴델수 $$y$$가 존재한다.'
4. 반응 및 영향
4.1. 수학 및 그 사례
현대의 표준적 집합론인 ZFC는 페아노 공리계의 모형을 제공할 뿐 아니라 뭇 수 체계를 포괄한다는 점에서 표준 수학의 '기초'가 된다. 그런데 페아노 공리계를 해석할 수 있다는 그 점으로 인해 ZFC 또한 불완전성 정리에서 피해갈 수 없다. 결국 ZFC를 기초로 삼는 한 참임에도 불구하고 증명할 수 없는 명제가 존재하며, ZFC의 무모순성은 ZFC에서 증명할 수 없다.
관건은 수학적으로 충분히 "흥미로운" 명제 가운데서도 하필이면 증명불가능한 명제가 있느냐는 점. 공교롭게도 힐베르트의 23가지 문제 중 하나로도 꼽혔던 연속체 가설이 ZFC와 독립적이라는 점을 쿠르트 괴델과 폴 코언이 증명함으로써 불완전성 정리가 적용되는 흥미로운 사례가 입증되었다. 불행인지 다행인지 힐베르트는 연속체 가설이 참이라는 것만 보고 죽었지만....
아래는 그 대표적인 사례들이다.
- 연속체 가설[9]: 모든 무한집합의 원소수(기수)는 $$ \aleph_n $$꼴로 표현 할 수 있다 여기서 $$ 2 ^{\aleph_0} = \aleph_1 $$ 이 성립하겠느냐는 것이 연속체 가설이고, 일반화된 것은 $$ 2^{\aleph_N} = \aleph_{N+1} $$ 이 성립하지 않을까 하는 일반연속체가설. 좀 더 자세한 것은 연속체 가설과 초한기수 문서 참조.
- Word problem for groups[10]
- Whitehead problem: torsion-free, total separable group 은 free 인가[11]
4.2. 계산 이론
계산 이론에 의해 불완전성 정리는 자연수론을 포함한 임의의 공리계에 대해서 다음과 같은 함축을 갖는다:
- 그 공리계 내부의 자료만으론 기계적인 유한한 절차로 참, 거짓을 결정/증명할 수 없는 명제가 반드시 있다. 그렇지 않으면 그 공리계에는 모순이 있다.
핵심은 수학의 경우에는 무모순하다는 것에 대한 증명을 '''그 체계 자체에서''' 증명될 수 없다는 것이다. 그보다 상위 체계를 동원한다면 가능할 수 있는 것. 게르하르트 겐첸은 '''유한한 기계적 절차가 아닌''' 초한귀납법이라는 방법을 동원해서 수체계의 무모순성 증명을 증명하기도 했다.
증명과정 중 사용한 원시 재귀함수는 컴퓨터과학을 탄생시키는 계기가 되기도 하였다. 하지만, 괴델은 이것을 실제 계산기와 같은 기계 쪽에 응용할 생각은 하지 않았고 후에 튜링이 원시 재귀함수를 보다 기계친화적인 튜링 기계로 바꾸어 표현하면서 컴퓨터의 아버지라는 이름은 튜링이 가져가게 되었다.
그리고 위 조건을 만족시키는 다양한 기계적인 유한한 절차들마다[13] 그에 해당하는 튜링 기계가 있으며 그 역 또한 성립함이 증명되었다. 이를 보다 확장하여 모든 계산가능한 함수마다 그에 상응하는 튜링 머신#s-6이 존재한다는 주장이 유명한 '''처치-튜링 명제'''이다.[14]
4.3. 철학
불완전성 정리에 대한 잘못된 해석 한 가지는 "참도 거짓도 아닌 수학적 명제가 있다"는 것이 불완전성 정리를 통해 증명되었다는 것이다. 이 해석이 잘못된 이유는 '''참임에도 불구하고''' 증명이 불가능한 명제 $$G$$가 있다는 것이 바로 제1정리이기 때문이다. 참도 거짓도 아닌 명제, 참이면서 동시에 거짓인 명제 등을 인정하는 비고전 논리학이 존재하는 것은 분명하지만, 이는 불완전성 정리로부터 곧장 따라나오는 것이 결코 아니다.
수학철학에서 괴델 본인은 오히려 플라톤의 견해를 그대로 받아들였다고 해도 과언이 아닐 정도의 강경한 실재론을 옹호했다. 즉 우리가 원리적으로 알 수 있건 없건 수학적 명제의 참거짓은 객관적으로 존재한다는 것. 괴델은 오히려 1951년 Gibbs 강연에서 (특정 조건이 만족된다는 가정 하에서) 불완전성 정리는 오히려 수학적 참이 객관적이라는 근거가 된다는 논변을 제안하기도 했다.
제2불완전성 정리가 확실히 직격한 수학 기초론은 다비트 힐베르트의 이른바 '힐베르트 프로그램'이다. 왜냐면 힐베르트 프로그램의 핵심은 형식화된 수학 이론의 무모순성을 유한한 절차에 의거하여 증명하려는데 있었기 때문이다.
괴델은 힐베르트학파 수학자들의 맹렬한 반론을 예상하여 이에 대응하기 위한 후속 논문을 불완전성 정리를 발표하는 논문에서 이미 예고했다. 그러나 힐베르트 및 그 제자들은 불완전성 정리에 아무런 반론을 제기하지 않았으며, 이 때문에 예고했던 후속 논문은 나오지 않았다. 힐베르트는 그 대신 '유한의 과정'에 대한 제한조건을 일부 포기하고 초한귀납법을 받아들임으로써 불완전성 정리의 장벽을 우회하려고 시도했으며, 이러한 무모순성 증명은 힐베르트의 조수였던 게르하르트 겐첸에 의해 달성되었다.
프레게와 버트런드 러셀, 그리고 논리 실증주의자들이 개진했던 논리주의 프로그램 또한 불완전성 정리 등장 이후 대대적인 수정이 불가피하게 되었다. 루돌프 카르납은 괴델 본인이 제안한 철학적 비판에 맞서 1930년대 이후 많은 이론적 수정을 가해야했으며, 1980년대 이후 진행되는 신논리주의 프로그램은 아예 고전적 논리주의의 여러 전제들을 포기하고 진행중이다.
심리철학에서 불완전성 정리가 언급되는 유명한 떡밥은 다음과 같다:
괴델 자신 또한 그 가능성을 지나가면서 언급한 적은 있으나, 현대에도 이런 떡밥을 꾸준히 대중적으로 미는 학자로는 로저 펜로즈가 있다.불완전성 정리에 따르면 기계적인 절차에 근거하여 참을 보일 수 없는 명제가 있다. 그런데 우리 인간은 그 참을 보일 수 있다. 따라서 인간의 마음은 계산 기계가 아니다
5. 대중적 인식
- 당시에는 증명이 난해하다기보다는, 논리체계를 '이용하는' 수학이 그런 논리체계 자체를 수학적 대상으로 환원하여 연구한다는 부분을 잘 이해하지 못하여 대부분의 비수학자들은 그저 논리와 이성으로 이 세상을 완전히 설명할 수는 없다는 정도로 받아들일 수도 있을 것 같다, 는 식으로 이해했고, 지금도 비전공자들은 막연히 그 정도로만 이해한다.[15]
- 몇몇 철학자들은 '우리가 진리에 결코 도달할 수 없다'는 뜻으로 해석하기도 한다. 몽테뉴, 니체가 했던 주장의 개정판인 셈인데, 물론 잘못된 해석이다. 수학의 위치를 생각해 보았을 때 철학적으로 중요한 기획 하나가 실패를 겪었다는 것은 사실이지만, 그 이외의 영역에서까지 이를 확장하는 것은 주의해야 한다. 대부분 이런 주장들은, 불완전성 정리를 제대로 이해해서 확장했다기보다는 그냥 좋은 소재(같은 예로는 상대성이론, 양자역학)를 물었을 뿐이다. 불완정성 정리를 이용해서 개드립을 치던 사람들은 나중에 앨런 소칼에게 걸려서 박살이 났다. 원래 진리에 결코 도달할 수 없다는 주장의 기원은 소피스트가 자기네끼리 투닥투닥하던 시절까지 거슬러 올라간다.
- 문학에서는 어쨌거나 뜻의 난해함과 불완전성이라는 단어가 주는 포스트모던적인 강렬함 덕분에 억지를 진실로 진실을 억지로도 재정리 할 수 있는 논리체계라고 오해를 받는데, 괴델의 정리는 '참으로 증명된 정리'의 존재를 부정하지도 않고, 참인 명제를 거짓이라고 선언하지도 않는다.
- 조금 더 일찍 나온 불확정성 원리가 주는, 세상은 확률론적으로 이루어져 '참과 동시에 거짓이다'라는 식의 오해가 쓰기 더 편리하기 때문에 더 이상은 등장하지 않을 듯하다.
- 사실 중세 및 근대초기, 오일러-가우스 시절까지의 수학에서는 지금의 고교수학 같이 단순히 주어진 수식의 연산정도만이 관심사였고, 해당 '체계' 및 '시스템 자체'의 엄밀함에 신경쓰기 시작한 것은 코시라는 수학자가 등장한 이후부터였다.[16] 그러나 수학의 전체적인 시스템을 엄밀하게 증명하는 과정에서 제대로 좋은 결과를 보여준 적은 거의 없다. 갈루아는 5차 이상의 방정식의 해를 구하는 공식은 없다는 결론을 내었고, 측도론에서는 3차원 이상 실수공간의 임의의 부분집합의 넓이를 구하는 함수는 존재하지 않음[17]을 보인데 더해서, 바나흐-타르스키 역설에서는 선택공리[18]를 이용해 순수하게 집합의 분할과 공간이동[19] 만의 방법을 사용해서 삼차원 실수공간의 서로 다른 부피를 가진 공 2개의 조각들이 모두 서로 대응함을 보여준다.[20]
- 괴델의 불완전성 정리 역시 이 연장선상에서 수학 그 자체의 불완정성을 보인 것이다. 현대수학은 매우 확고한 기초를 가진듯 보이지만, 사실 내부사정을 조금 들여다보면 이래저래 '의미적'으로도 위의 바나흐-타르스키 역설 같은 여러 가지 역설이 존재하기 때문에 공격받는 부분이 많고, 그 외에도 철학적으로 비구성적 오브젝트를 허용한데 대한 입장차이 등으로 인하여 공격받는 부분이 많아 '물 바깥에서 보기엔 우아하고 아름답지만, 안에서는 열심히 다리를 허우적대는 백조'와 같은 모양새를 띠고 있다. 괜히 러셀이 '수학의 원리'같은 책을 낸 것이 아니다.
- 골드바흐 추측과 얽혀서 "어쩌면 골드바흐의 추측도 저 "참이면서도 증명할 수 없는 명제"(참 거짓을 증명 할 수 없는 문제)가 아닐까?" 하는 것을 써먹은 소설 <사람들이 모두 미쳤다고 말한 외로운 수학 천재 이야기>가 있다. 아직까지 증명도 반증도 안 되니 참으로 간주하는 것. 페르마의 대정리도 증명되기 전에는 비슷한 의심을 하는 사람들이 있었다.
- 읽어보면 좋은 책으로 <괴델, 에셔, 바흐>, <불완전성> 등이 있다. 참고로 <괴델, 에셔, 바흐>의 구판 한국어 번역본의 퀄리티는 악명이 높았지만, 2017년에 나온 개정판은 역자가 바뀌면서 번역의 질이 압도적으로 높아졌다.
[1] 비슷한 맥락에서 중요한 성질로 콤팩트성 정리가 있다. 이는 위상수학의 compact 개념을 적용한 것으로, "φ가 명제들의 집합 Γ의 귀결이면, Γ의 유한한 부분집합 Γ'이 존재해서 φ가 Γ'의 귀결이다"가 성립한다는 것이다.[2] 나중에 튜링(Turing)도 이 방법을 차용하여 튜링머신을 만들었다.[3] 서로 다른 기호들에는 다른 양의 정수가 부여되면 되니까 산술명제들과 그것들을 이루는 기호들의 집합에서 양의 정수로 가는 단사함수(injection)로 이해해도 상관 없다. 또한 굳이 괴델이 보인 방식만 있는건 아니고 다른 방식들을 얼마든지 정할 수 있다. 위키백과에서는 기초적인 10개의 '불변부호', 즉 '('나 '0', 's' 같은 것들에 미리 1~10을 할당하고, 나머지 경우에는 변수마다 종류를 나눠 n번째 종류의 k번째 변수에 해당하는 괴델수를 (10 이후의 k번째 소수)^n으로 제시했다. 이렇게 하면 모든 기호들마다 동일한 수가 겹칠 일이 없다.[주의] A B C $$n$$을 나타내는 기호를 '$$n$$'라고 적기하는 것은 엄밀하지 않다. 변수 $$n$$을 나타내는 기호는 변항이 아닌 $$n$$을 나타내는 숫자일 것이기 때문이다. 마찬가지로 '$$Dem(x, sub(n, 17, n))$$'라는 표현은 엄밀하지 않다. $$sub(y, 17, y)$$는 함수값이며, $$Dem$$의 두번째 변항은 기호가 되어야 하기 때문이다.[4] 그냥 모순을 받아들이면 안 되나 싶을 수도 있지만 모순을 받아들이는 순간 모든 게 참으로 귀결되는 쓸모없는 공리계가 되어버린다. 이를 '''폭발 원리'''(Principle of Explosion)라고 하는데, 직관주의 논리체계에서는 추론규칙으로 사용하며, 스탠다드 논리체계에서는 다른 공리들에 의해 연역된다. 이 논리학 법칙에 대해 자세히 알고 싶다면 위키백과 영문판 참조. 나무위키의 명제 논리 문서에도 간략한 설명과 증명이 실려 있다.[5] 괴델의 최초의 증명에서는 $$\neg G$$의 부정으로부터 ω-모.ㅏ순성, 즉 산술을 해석하는 이론 T 안에 자연수에 대한 논리식 P가 있을 때, T로부터 논리식 P(0), P(1), P(2), ... 라는 식으로 P(n)의 성립을 모두 증명가능한 동시에 "∃n: ~P(n)"도 증명가능하다는 것을 보였다. 보다 일반적인 모순성을 도출시킨 것은 존 버클리 로써(John Barkley Rosser)이며, 이때문에 제1불완전성 정리는 괴델-로써 정리라고도 한다.[6] 보다 엄밀하게 말하자면 페아노 공리계를 포괄할 수 있는 증명 체계 하에서[7] Zermelo-Fraenkel Set Theory + Axiom of Choice[8] 여러 개의 집합이 있을 때, 각각의 집합에 그 집합의 원소를 하나씩 대응시키는 함수가 엄밀하게 따져도 가능하고 존재한다는 공리. 여러 개의 집합이라고 했는데, 유한 개의 집합이 있는 경우와 무한 개의 집합이 있는 경우 둘 다 허용하는데, 유한 개의 집합의 경우는 이 공리가 없어도 가능은 하다. 결론적으로 바로 앞의 함수를 이용하면 여러 개의 집합에서 하나씩 원소를 뽑아서 집합을 만들 수 있게 된다.[9] 선택 공리와 연속체 가설이 증명 불가능하다는 것은 모두 폴 코언(Paul Cohen)이 증명했고 반증이 불가능하다는 것은 괴델이 증명했다.[10] 공리계에 관한 내용은 아니지만, Undecidability 에 관한 문제라, 불완전성 정리와 가까운 문제라 볼 수 있다. 유한집합인 임의의 알파벳 A 의 문자로 생성된 group G 가 있다고 하자. 역시 A 의 문자들로 구성된 임의의 word 2개를 만들어, 그것이 G 에서 같은 원소인지 아닌지 구분하는 알고리듬이 존재하는가 하는 문제인데, Higman 에 의하여 불가능하다고 증명되었다.[11] ZFC 에서 증명도 반증도 불가능하다. ZFC에 V=L(이 역시 괴델이 제시한것으로, 괴델 공리라고도 불린다.) 공리를 추가하면 free 가 맞고, MA(Martin's axiom) 와 연속체가설의 부정을 추가하면 free 가 아니다. [12] 불완전성 정리를 증명하는 방법 중에 정지 문제로 환원하여 증명하는 방법도 존재한다.[13] μ-연산자가 추가된 class of recursive functions, λ-대수, unlimited register machine(URM), while-programming 등과 같은 여러 가지 다른 공리계들이 존재한다.[14] 알고리즘이 수학적 혹은 논리적으로 명확히 정의된 개념이 아니라서 이 공리체계들이 모든 알고리즘을 포함하는지는 증명 불가능하다. Church's thesis는 사실 수학보다 철학이나 물리학, 인공지능 분야에서 '인간의 사고를 알고리즘으로 표현이 가능한가'와 같은 문제와 관련이 깊다.(사실 집합론과 카테고리 이론 정도를 제외한 대부분의 수리논리학 분야는 일반적으로 대학교 수학과에서 다루는 내용과는 큰 관련이 없다.)[15] 그러나, 사실 그렇게 난해하지만은 않으며, 이해하기 위해 필요한 사전지식도 그나마 적은 편이다. 실제로, 복잡한 정도로만 따지자면 완전성 정리가 더 복잡하다. 관련학과를 들어가면 대학원도 아니고 학부 때 수리논리를 택하면 배울 수 있다. 사실, 수리논리 전공에서 불완전성 정리는 입문정도에 해당한다. 외국대학교들에서 쓰는 논리학 교재들에서는 거의 끄트머리에 나오기는 하지만...[16] 그래서, 오일러 이후로 수학은 끝난 줄 알았는데 가우스가 등장했고, 오일러-가우스 이후로 수학이 끝난 줄 알았는데 코시가 등장했다라는 말도 있다.[17] 바나흐는 n-공간에서 임의의 부분집합에 대해 "부피"(1, 2차원에서는 각각 길이, 넓이와 같다)라는 값을 주는 함수가 만족해야 할 성질을 만족하는 함수를 찾고자 했고, 1,2차원에서 그러한 함수가 존재한다는 것을 발견했지만, 하우스도르프라는 수학자는 3차원 이상에서는 그러한 함수는 존재할 수 없음을 보였다. [18] 요약하자면 공집합이 아닌 어떤 집합들을 원소로 갖는 집합족에 대하여, 원소인 집합에서 원소를 하나씩 골라 새로운 집합을 만들 수 있다는 것이다. 언뜻 보면 자명해 보이지만, 사실 무한개의 원소를 가진 무한개의 집합들에서 원소를 하나씩 골라낸다는 것은 아주 자명하지는 않다. 또, 이 공리를 받아들이면 반직관적인 정리들을 여럿 얻게 된다. [19] 물론 공간을 왜곡하는 이동이 아니라 유클리드 운동이다.(즉, 평행이동, 회전, 반사 등 거리를 보존하는 이동이다)[20] 다만 이는 모순은 아닌데, 위에서 말했듯이 모든 집합에 대해서 부피가 정의되지는 않기 때문이다. 그래서 부피를 가지는 집합을 정의하여 그 집합에 대해서만 부피를 다루게 되는데, 바나흐-타르스키 역설에서는 부피를 가지지 못하는 집합으로 분할하는 과정을 거쳤기 때문이다. 그리고 부피를 가지지 못하는 집합들로 분할한다는 점에서 그냥 자르는 것만으로는 불가능하다.