궁금한 것이 있다면 대학에 가서 공부하면 된다. 시험을 봐야 하고, 등록을 하고, 수강신청을 해야 한다. 어느 세월에.
체계는 없지만 그냥 궁금한 것이 있으면 찾아서 공부할 수 있는 세상이 되었다. 영상이 있다. 오늘의 궁금증은 괴델과 괴델의 불완전성의 정리 incompleteness theorem다.
쿠르트 괴델 Kurt Gödel에 대해서는 mbc의 '서프라이즈'와 위키백과를 섞어서 정리했다. 1906년에 태어나 8살때부터 류머티즘을 앓는 등 병약했으나, 18세에 빈대학 물리학과에 입학하여 24세때 박사학위를 받고, 1931년에 불완전성의 정리 incompleteness theorem을 발표한다. 1930년부터 10년 동안 빈대학의 강사로 활동했다.
이혼녀이자 댄서였던 아델을 1928년에 만났으나 가족들의 반대로 간신히 10년만에 결혼하고, 1940년에 미국의 프린스턴 고등연구소 IAS에 가서 아인슈타인을 만난다. 아인슈타인은 편지에서 "괴델과 함께 집으로 돌아오기 위해 연구소에 간다"라고 했을 정도로 친밀한 관계를 유지한다. 아인슈타인은 1955년 사망한다.
말년에는 피해망상에 빠져 아델이 만들어주는 음식 이외에는 아무것도 먹지를 않았고, 두문불출한다. 아인슈타인도 암살되었으며, 자신도 누군가에 의해 죽임을 당할 것이라는 불안증에 시달렸다. 1978년 1월, 아델이 병원에 입원해 있는 동안 병원 치료식 조차 거부하며 굶어죽었는데, 168cm의 키에 30kg인 상태였다고 한다.
1. 불완전성 정리와 등장 배경
1) 힐베르트 프로그램 : 내용과 의미가 명확한 수학문제는, 아무리 어려운 문제라도, 시간이 지나면 언젠가는 반드시 풀리게 된다. 1900년 파리에서 열린 세계수학자대회에서 10개의 문제를 제시하고 - 나중에 발표된 문제까지 총 24문제, 20세기 수학의 과제를 제시하였다.
2) 수학의 무모순성을 증명하기 위해 추진했던 프로그램의 일부로 연구되었는데, 오히려 수학이 증명할 수 없는 참인 명제가 있다는 것이, 괴델에 의해 증명되었다.
3) 제1정리 : 참이지만 증명할 수 없는 명제가 존재한다.
4) 제2정리 : 공리계의 무모순성을 해당 공리계에서는 증명할 수 없다.
2. 제1정리의 쉬운 증명
* 유튜브를 참고해서 다시 정리해 봤다 : https://www.youtube.com/watch?v=g-ci_O86_VY
1) 명제 G : 명제 G는 증명할 수 없다.
2) 명제 G의 증명이 가능한지를 살폈더니,
ㄱ) 증명 가능 : "명제 G는 증명할 수 없다"고 했는데, 증명을 했으므로 모순이 발생한다. 모순인 주장은 버린다.
ㄴ) 증명 불가능 : "명제 G는 증명할 수 없다"고 했는데, 실제로 증명이 불가능했으므로, 명제 G는 참이다.
ㄷ) 모순인 주장을 버리고나면, "참인 명제 G는 증명할 수 없다"는 결론에 도달한다.
ㄹ) 괴델의 제1정리가 맞다.
그렇다면, 과연 명제G가 존재하는가? 즉, 증명할수 없는 참인 명제 G가 존재하는지를 보여라.
증명의 첫단계는 괴델수를 이해하는 것이다.
3) 괴델수 : 모든 것을 소수로 순서대로 표현할 수 있다. 그리고 문장도 서로 다른 괴델수를 표현할수 있다.
ㄱ) 괴델수 2 : 철수
ㄴ) 괴델수 3 : 짜장
ㄷ) 괴델수 5 : 짬뽕
ㄹ) 괴델수 7 : 좋아한다
ㅁ) 괴델수 11 : 먹는다
ㅂ) 괴델수 13 : 증명가능하다
ㅅ) 괴델수 17 : 없다
ㅇ) "철수는 짜장을 좋아한다"의 괴델수 : 2 x 3 x 7 = 42
ㅈ) 괴델수 42 = 철수는 짜장을 좋아한다 = 2 x 3 x 7
4) 위 설명은 잊고, 다음과 같이 괴델수를 다시 정의해 보자.
ㄱ) 괴델수 2 : 아니다
ㄴ) 괴델수 3 : 존재한다
ㄷ) 괴델수 5 : =
ㄹ) 괴델수 7 : 0
ㅁ) 괴델수 11 : x
ㅂ) 괴델수 13 : y
ㅅ) Sub(x, 13, x) : 괴델수 x 를 가진 문장에서 13을 괴델수 x 로 대체한다.
ㅇ) 명제 P : Sub(y, 13, y)는 증명불가능하다 -> 괴델수 n
: 괴델수가 n이면, 명제 P이고, 'Sub(y, 13, y)는 증명불가능하다'라는 메타수학의 문장이다.
ㅈ) 명제 G : Sub(n, 13, n)는 증명불가능하다 -> 괴델수 g
ㅊ) Sub(n, 13, n) ≡ 괴델수 n인 문장에서 13를 괴델수 n으로 대체한다
(왜냐하면, 괴델수 n인 명제는, 명제 P다. 명제 P에서 y를 n으로 대체한 것이기 때문에)
≡ 괴델수 n인 문장에서 변수 y를 괴델수 n으로 대체한다
(왜냐하면, 괴델수 13 = 변수 y)
≡ 괴델수 g
ㅋ) Sub(n, 13, n)의 괴델수는 g이고, 명제 G의 괴델수도 g이다.
ㅌ) 두 명제의 괴델수가 같으므로, 명제 G = Sub(n, 13, n)이다. 즉, 존재한다.
ㅍ) Sub(n, 13, n)은 증명할수 없다고 했으니,
명제 G가 존재하는데, 증명할수 없다.
모든 수학명제는 증명할 수 있다는 힐베르트의 생각은 틀렸고,
증명할 수 없는 참인 명제가 존재한다는 괴델의 정리가 맞다.
3. 무슨 소리인가?
1) 세마science는 원인이 있으면 결과가 있고, 결과를 보고 원인을 유추할 수 있다.
2) 그러나 불완전성의 정리에 의해, 수학이나 논리학에는 증명할 수 없는 참인 명제가 존재한다.
3) 그러므로 수학의 방법론을 따르는 세마에도 증명할 수 없는 참인 명제가 존재한다.
4. 좀 더 어려운 제1정리 증명
1) Dem(n, m) : n은 m의 증명이다. / Dem : Demonstration / n, m, Dem(n, m)은 각각 어떤 문장의 괴델수
1-1) n이 존재하면, m은 증명가능하다
1-2) n이 존재하지 않으면, m은 증명불가능하다
2) Sub(n, m, x) : 괴델수, n의 부분인 m을 x로 대체한다는 명제의 괴델수
Sub : Substitution / n, m, Sub(n, m, x)은 각각 어떤 문장의 괴델수, x는 미지수
3) 명제 P : ~(∃x) Dem[x, Sub(y, a, y)]
ㄱ) ∃x : x가 존재한다 -> ~(∃x) : x가 존재하지 않는다
ㄴ) y, a, Dem[x, Sub(y, a, y)], ~(∃x) Dem[x, Sub(y, a, y)] : 각각 어떤 문장의 괴델수
ㄷ) y : 미지수
ㄹ) Sub(y, a, y) : '괴델수 y의 명제에서 미지수 y의 괴델수인 a를 미지수 y로 대체한다'는 명제의 괴델수
: 이게 왜 괴델수 y인지 모르겠다. 여담이라고 하니까 그냥 넘어가자.
4) 명제 P : ~(∃x) Dem[x, Sub(y, a, y)] ≡ 괴델수 n
4-1) 명제 P : Sub(y, a, y)를 증명하는 x가 존재하지 않는다
4-2) x가 존재하지 않으므로, Sub(y, a, y)를 증명할수 없다
5) 명제 Q를 명제 P에서 만들자. 명제 P에서 y를 n으로 대체한다
5-1) 명제 Q ≡ ~(∃x) Dem[x, Sub(n, a, n)]
5-2) 명제 Q≡ Sub(n, a, n)을 증명하는 x가 존재하지 않는다.
6) '명제 Q가 참이다' 라는 문장과 같은 값을 갖는 문장을 만들어보자.
명제 Q가 참이다
≡ ~(∃x) Dem[x, Sub(n, a, n)]가 참이다.
≡ 'Sub(n, a, n)을 증명하는 x가 존재하지 않는다'가 참이다
≡ 'Sub(n, a, n)을 증명할수 없다'가 참이다
≡ Sub(n, a, n)을 증명하는 x가 존재하지 않는다.
https://youtu.be/FbHowuEuYk8?feature=shared(to be continued if I would understand)
≡ ~(∃x) Dem[x, m]가 참이다.
≡ '괴델수 m을 증명하는 x가 존재하지 않는다'가 참이다.
5-3) Sub(n, a, n) ≡ 괴델수 m
5-4) 괴델수 n의 문장(명제 P)에서 y를 n으로 대체한 것이 명제 Q
