스압) 블루아카로 알아보는 수학 이야기 - 불완전성 정리

[시작전 유의사항]

https://bbs.ruliweb.com/community/board/300143/read/66828656

이 글 한번만 읽고 와주세요...

이 글을 읽고 왔단 가정하에 썼읍니다

뉴턴(대역: 호시노):
으헤~ 아저씨 굉장한 거 만들었다고?
바로 미적분이야~

다른 사람(대역: 세리카):
그래서 이거 어떻게 써요 선배?

뉴턴:
으헤~ 미분이란건 말이지? 아저씨가 하는 거 잘 따라해보라고?

이렇게 무한소(위 사진에서 오메가)란걸 넣어서 계산한 다음에, 이 무한소를 0으로 떼우면 함수를 미분한 게 된다고?

다른 사람:

근데 무한소가 뭐에요 선배?

뉴턴:

그냥 아주아주아주 작은 수라고 퉁치자고... 으헤~

거기에 수가 곱해져 있으면 0이라고 퉁치고...

다른 사람:
그렇게 되는...건가?

코시(대역: 아야네):
크아악! 선배! 왜 무한소를 어떨땐 0 취급하고 어떨땐 아주 작은 수 취급하는 건데요!
그러면 0.99999...랑 1이랑 다른 수냐고 누가 물어보면 어떻게 답할건데요!

*실제로는 0.9999...=1 문제가 아닌, 저 무한소 처리법이 좀 비논리적이라 당시에도 비판이 많이 나왔다고 합니다

뉴턴:
아저씨는~ 그런거 대충 쓰는거야~

코시:
안되겠어요! 무한소로 미분을 정의하면 큰일나니, 다른 정의를 만들거에요!
... 무엇이 좋을까...
...볼차노 선배랑 바이어슈트라스 선배가 만든걸 보고 만들어야지...!

볼차노 (대역: 시로코):
응, 그거 잘 써.

바이어슈트라스 (대역: 노노미):
응응, 코시짱 열심히 하는 거에요!

*실제로 엡실론-델타 논증은, 볼차노-바이어슈트라스 정리에서 기반해 코시때 완성되었습니다

그렇게 해서 나온 게 바로 엡실론-델타 논법.

하지만 수학은 이것 이외에도, 모호하게 서술해서 논란이 된 부분이 많았으니...

지금부터 다룰 이야기는,
이 모호하게 서술한 걸 엄밀하게 증명하던 20세기 초의 이야기를 다루고자 해.

시작하기 전에, 2000년전 고대 그리스로 잠시 시선을 돌리자.

유클리드(대역: 타카네):

제가 발견한 수학적 정리를 책으로 집대성해서 내놓았사와요. 이걸 이라 부르겠사와요!

*동인지가 아님에 유의하자

유클리드는 기하학 원론을 통해 

23가지의 정의와, 5개의 공준를 정리했는데,

*실제로 수학에서의 규칙은 공리라고 따로 부르는 말이 있는데, 가끔 공준이랑 공리랑 섞어쓰는 경우가 종종 보이는데 엄연히 다른 말이니 주의해야 한다

...근데 유클리드 기하학 원론에서 한해서는 사실 편의상 동의어로 자주 쓰긴 한다

정의는 다들 알다시피...

justice?

어 츠루기야 그거 아니야, 돌아가

...

아무튼 기하학에서 자주쓰는 대상을 정의(definition)를 했고,

공리, 쉽게 말해서 수학에서의 규칙을 만들어서 그 규칙에 따라 풀어낸 결과물들을 정리한 게 기하학 원론 되시겠다 이 말이다

간단한 예로...

삼각형 내각의 합이 180도인 걸 보이는데

기하학 원론은 이걸 어떻게 보였냐면

먼저 각을 정의하고, 다각형을 정의한 다음,

이렇게 평행선의 성질을 이용해 각을 이동시킨 뒤에 세각의 합이 수평이 됨을 보여줬어

유클리드의 기하학 원론은 이런 증명 과정을 최초로 보여주는 자료라는 점에서 가치가 큰데, 문제가 하나 있었어.

유클리드:

암만 생각해도 5번째 공준이 진짜 공리가 맞는지 모르겠어...

이 5번째 공준(공리)이 뭐였냐면,

"임의의 직선이 두 직선과 교차할 때, 교차되는 각의 내각의 합이 두 직각(180도)보다 작을 때, 두 직선을 계속 연장하면 두 각의 합이 두 직각보다 작은 쪽에서 교차한다"

이렇게 돼.

이걸 평행선 공리라고 부르는데,

얼핏 생각해도 삼각형의 합이 180도인걸 생각하면 맞겠거니 싶겠지만, 

이런 문제가 있어:

"사냥꾼이 집에서 나와 남쪽으로 1km를 가니 곰을 만나 잡았다.

서쪽으로 1km를 쫒아가 곰을 잡고, 북쪽으로 1km를 가니 집이 나왔다.

이때 곰의 색깔은?"

키리노라면 이 문제의 답을 알겠지?

... 흰색.

집이 북극점이면 남쪽으로 1km를 간뒤 서쪽으로 1km를 가면 원 호 따라서 돈거니까.

이런 게 가능한 곳이 지구상에 두곳 있는데

남극엔 곰이 없으니 집은 북극점이겠지.

칸나가 말했듯이, 북극점에서 출발해 남쪽으로 1km, 서쪽으로 1km, 북쪽으로 1km 이동하면 다시 북극점으로 돌아오는 걸 생각해보자고.

이걸 평면상에서 그리면 그냥 U자 비스무리한 형태가 되지만, 우리는 지구상에 살고 있으니 저 모양도 결국 삼각형을 이룬다고.

근데 아까 5번째 공리를 다시 보면 "임의의 직선이 두 직선과 교차할 때, 교차되는 각의 내각의 합이 두 직각(180도)보다 작을 때, 두 직선을 계속 연장하면 두 각의 합이 두 직각보다 작은 쪽에서 교차한다" 라고 되어있는데, 두 직선의 각의 내각의 합은 둘다 직각이니 180도가 되는데

...이 경우는 한 점(=북극점)에서 만나네?

뭔가 이상하단 생각이 들었으면 정상이 맞단다.

실제로 수학자들이 이 평행선 공리가 참임을 입증하기 위해

저게 거짓이라 가정하고 기하학 원론에 있는 나머지 4개의 공준만으로 기하학이 성립되는 지 알아봤는데,

놀랍게도 모순이 없다는 결론에 도달했지.

그래서 만들어진 게 바로 비유클리드 기하학이란다.

리만 (대역: 토키)

비유클리드 기하학을 집대성한 리만입니다 뿅

그래서 리만 기하학이라고도 부릅니다 뿅

*리만 가설도 제가 제안했습니다 뿅(이 주석은 토키가 달고 도망갔습니다)

리만은 잠시 들어가 있고... 지금은 좀 설명이 필요하니...

아무튼 이 일로 미분기하학이 시작되기도 했지만,

공리라는 게 절대적인 게 아니란 걸 시사하게 되었지.

그리고, 미적분을 만든 뉴턴의 이야기에서도 봤듯이 엄밀하게 정의되지 않은 부분이 많기도 해서,

그래서 수학자들이 수학 체계를 공고히 하기 시작했단다.

이게 19세기 말의 일이란다.

 

오늘 하고자 하는 이야기는, 이 수학 체계를 공고히 하고자한 수학자들의 노력을 한번에 쪽박낸, 엄청난 사건을 이야기 해보려고 한단다.

때는 1874년...

칸토어 (대역: 마코토):
키키킥... 이 몸이 집합이란 개념을 만들었다!
이걸 이용해서... 일대일 대응을 만들면...! 자연수의 집합과 짝수의 집합의 크기는 같다! 그리고 정수의 집합과 자연수의 집합의 크기는 같다!

푸엥카레 (대역: 히나):
뭐래

크로네커 (대역: 이로하):
말이 되는 소리를 하세요, 칸토어...

그도 그럴 것이,
유클리드 시절부터 내려온, 전체는 부분보다 더 크다는 내용이랑, 칸토어가 증명했다는 내용이랑

서로 들이받는 상황인데,

당연히 논란에 휩싸였던 것이지 

유게이 친구들도 자연수 개수랑 짝수 개수랑 같다고 생각하면 동의하겠어?

 

칸토어:

...아무튼 1대1 대응으로 자연수 집합이랑 짝수 집합이랑 크기가 같단걸 보일 수 있지... 후 힘들다..

*자세한 건 위에 미리 읽고 오라는 글 읽고 오면 좋읍니다 꼭 읽고 오세요

칸토어:

이걸 또 해보니... 자연수 집합의 크기랑 유리수 집합의 크기는 같군. 실수 집합은 유리수 집합보단 크고. 그리고 실수 집합의 크기는 자연수 집합의 멱급수 집합의 크기랑 같군.

칸토어:

근데...
자연수 집합보다 크고 실수 집합보다 작은 집합이 존재했었...나?

연속체 가설(대역: 아리스): 

여기서 연속체 가설 등장입니다! 뽜밤뽜밤~
자연수 집합의 크기보다 크고, 실수 집합의 크기보다 작은 크기의 집합이 존재할까요?

그리고 칸토어는 이 연속체 가설을 풀지 못하고 결국 죽었지

마코토:

잠깐 난 여기서 퇴장이라고?

*실제로 칸토어가 못 푼 건 맞지만, 절대 이 분이 마코토처럼 바보라서 그런 건 아니니 참고

힐베르트 (대역: 리오):

(...친구가 뭔가 이상한 거 같지만...)
...아무튼 친구 칸토어의 문제니 일단 23가지 문제의 첫번째에 넣어서 풀어달라고 해야지.

연속체 가설:

저는 이제부터 힐베르트의 23가지 문제의 1번 문제입니다! 뽜밤뽜밤~

힐베르트:

아무튼 이거도 문제에 올려뒀으니, 나는 이제 다른 수학의 영역에 있는 것들도 공리로 설명하는 세계를 만들어야지... 

프레게(대역: 치히로):

힐베르트, 그 공리로 수학을 설명하는 세계 말인데, 내가 근본법칙이란 책을 내놨는데 한번 볼래?

산수를 논리학으로 설명할 수 있다는게 내 생각인데.

???:
잠깐만요, 저기서 주장한 공리 자체에 문제가 있는데요?

힐베르트:

당신은 누구...?

러셀 (대역: 히마리):
초천재병약미소녀수학자인 러셀이랍니다, 후후

*실제로는 아닙니다

화이트헤드 (대역: 에이미):
그리고 나는 화이트헤드, 뭔가 고증이 이상한 거 같지만 넘어가줘
아무튼 나랑 러셀이랑 같이 수학 원리를 썼어...

*실제로는 러셀이 화이트헤드의 제자로 있었기 때문에, 고증대로면 저 둘의 포지션이 반대가 되야 하지만, 그냥 넘어가는 걸로 합시다

그리고 화이트헤드는 대머리였다고 합니다

러셀:
아무튼, 힐베르트 씨, 이런 문제가 생각났는데 한번 풀어보실래요?
[세비야의 한 (남자) 이발사는 다음과 같이 선언했다.
"앞으로 나는 자기 수염을 '스스로 깎지 않는' 모든 사람들의 수염을 전부 깎아줄 것이오. 다만 '스스로 깎는' 사람은 깎아주지 않겠소."
이때 이 이발사의 수염은 누가 깎아줘야 하는가?]

유게이들은 귀찮아서 문제를 안 풀테니, 설명을 해주자면...

만약 다른 사람이 이 이발사의 수염을 깎아주는 경우 이 이발사는 수염을 '스스로 깎지 않는' 사람에 속하므로, 선언한 바에 따라 자신의 수염을 깎아야 해.

하지만 스스로 수염을 깎는다면 이 이발사는 수염을 '스스로 깎는' 사람에 속하므로, 선언한 바에 따라 자신의 수염을 깎을 수 없게 되지.

결국 이발사는 이러지도 저러지도 못하게 되는 거지

프레게는 러셀의 역설을 보자마자 이랬다는 말이 전해져:

프레게:

내 원고가아아아아아아!

*실제로 프레게가 러셀의 역설 소식을 듣고 인쇄소에 가서 근본법칙 2권 출판을 그만두라 하려고 했다가 포기하고 서문을 따로 추가했다고 합니다

아 물론, 이발사가 사람이 아니거나 여자면 가능하다고 외칠 유게이들이 있을 거야.

...그렇다고 퍼리 이발사라던가 여자 이발사에게 박는다고 댓글 달지 말고...

아무튼 이 문제는 간단히 설명하자면

집합에 진짜 아무거나 집어넣어서 생긴 참사여서,

특정한 성질들을 모아넣은 건 따로 분류하는 등 지금 집합론은 저 역설만큼은 피하도록 구성이 되어있지.

...그러니까 "뭐든지?" 이 말은 함부로 하는 게 아니란다.

러셀:

이 역설을... 간신히... 피할 수 있었군요.

힐베르트:

하...

아무튼 한숨 돌리나 싶었던 수학자들에게, 폭풍이 한차례 더 찾아왔지.

러셀과 화이트헤드가 수학 원리를 1913년 출간하고 20년도 채 되지 않아서,

1931년 한 수학자가 이런 논문을 냈어.

???:

실례합니다... 혹시... 논문... 받아주시나요...?

한 수학자가 교수 임용 자격 시험 논문으로 이런 제목을 가진 논문을 발표해.

그 논문의 이름은 바로...

"『수학원리』와 관련 체계들의 형식적으로 불가능한 명제들에 관하여"

뭔가 거창해보이지만, 이 논문이 다루고 있는 내용이 바로 불완전성 정리, 바로 오늘의 핵심 주제야.

사실 나무위키를 보면 그나마 이해는 되겠지만,

그래도 설명이 어려우니 유게이들을 위해 쉬운 말로 최대한 바꿔 설명하자면...

수학에 있는 어떤 규칙을 갖고 와도, 맞는 말인데도 왜 이게 맞는 말인지 틀린 말인지 설명할 수 없는 문장이 항상 존재한다는 말이지.

수학의 논리 자체는 탄탄하지만, 그 탄탄한 논리로도 이게 참인지도, 거짓인지 설명할 수 없는 "참인 문장"이 있다니, 이 얼마나 무서운 이야기겠어, 안 그래?

이런 문장의 대표적인 예시로 하나 들자면...(물론 실제로 1대1 대응은 안되겠지만)

나는 거짓말쟁이다

만약 내가 거짓말쟁이면, 그러니까 위 문장이 참이라면,

내 말이 모두 거짓말이니 내가 거짓말쟁이라는 말 자체가 거짓이 되야 하고

만약 위 문장이 거짓이라면.

내가 거짓말쟁이가 아니니 내 말이 모두 참말이 되고, 그러니까 다시 위 문장이 참말이 되고...

뭔 내용이 머리가 아파요...

괴델의 불완전성 정리는 이 "나는 거짓말쟁이다"라는 명제에서 출발해.

수학에서 공리로 만든 논리 체계를 공리계라고 불러.

*실제로는 해당 내용을 다루는 수리논리학에서는, 형식체계라는 말을 더 많이 씁니다.

어떤 공리계가 있다고 가정하자.

이걸 공리계 B라고 하고, 문장 A를 이렇게 쓰자고.

A: 이 문장은 공리계 B에서 증명이 불가능하다

아까의 거짓말쟁이 문장이랑 많이 비슷한 구조지?

근데 이제 여기에, 공리계 B의 조건이 추가되는 거지.

바로, 공리계 B에는 모순이 존재하지 않는다고 말이야.

그럼 이 문장이 참인지 거짓인지 따져보자고.

먼저 문장이 거짓이라고 생각하면,

그러면 문장 A는 증명 가능하다는 말이 되버리지. 

이러면 무슨 일이 일어나냐면, 

증명 불가능함이 증명가능하단 이야기가 되버리거든.

그러니 문장 A는 참이 되어야 하는데,

이 경우 문장 A는 말그대로, 증명 할 수 없게 되버린단 말이지.

그러니, 문장 A는 참이지만, 증명불가능하게 되버린다는 결론에 도달해.

근데, 논리학에서 증명할때는 보통 반대의 경우도 생각을 해줘야 해.

한마디로 말해서, 부정의 경우도 봐야한단 말이지.

위 문장의 부정형인 A는 모순이 없는 공리계 B에서 증명 가능하다는 문장의 참 거짓 유무도 따져야 한단 말이야.

근데 만약 A의 부정형이 증명 가능하다면, A도 증명가능하고, 다시 말해서 부정형이랑 원형 문장 둘다 증명가능하다는 말이 나와.

둘중 하나는 증명이 불가능해야 하는데 둘다 증명이 가능하다는 말에서 모순이 생기는 거지.

그렇게 해서,

모순이 없는 공리계 B에서, 참이지만 결정 불가능한 문장이 존재하게 된다는 말이지.

여기서 괴델은 한 발 더 나아가, 문장 C를 하나 더 제시해.

C: 공리계 B가 모순이 없다면, A이다.

아까 우리가 A는 공리계 B에서 증명이 불가능하다고 했어.

이거는 아까 우리가 본 내용이기 때문에, C는 증명 가능하다고 생각할 거야.

그런데, C를 다시 보면, C는 두 구조를 갖고 있어.

"공리계 B에 모순이 존재하지 않는다면"/"공리계 B에서 증명 불가능하다" 이런 식으로 나눌 수 있겠지.

C가 증명 가능하다고 앞에서 결론을 내렸기 때문에, 앞이 증명 가능하다면, 뒤도 증명이 가능할거야.

하지만, 앞에서 우리는 증명 불가능하단 결론을 이미 내렸기 때문에, 그 앞도 증명이 불가능해져.

그렇기 때문에, 모순이 존재하지 않는 공리계 B의 논리만으로, 공리계 B가 모순이 존재하지 않음을 보이는 건 증명 불가능이 되는 거지.

이렇게 불완전성 정리가 이루어져 있는거야.

실제로는 논리식을 수로 바꾸는 절차를 걸쳐, 그걸 기호로 바꾼 다음 곱해서 보이는 괴델 수란 걸 이용해서 증명했지만, 이건 여기서 설명하면 듣는 사람들 전부 속터져 나가거나, 머리가 터져 나가거나, 아니면 그냥 뒤로가기 할테니 그냥 그런 게 있다고만 알아둬.

증명 이해하는 거도 머리 아픈데...

그런 문장이 존재한다면 머리가 더 아플 거 같은데요...

힐베르트:

제발 그런 게 없다고 해줘, 제발

없을리가.

괴델:

연속체 가설은... 집합론 공리계와... 무모순이에요...

*1938년 괴델이 연속체 가설은 집합론 공리계, 정확히는 ZFC 공리계와 무모순임을 증명했다.

참고로 ZFC는 현대 집합론에서 주로 쓰이는 공리계 정도로만 알면 된다.

코헨 (대역: 미도리):

연속체 가설이 거짓이라고 가정해도 집합론 공리계와 무모순이에요.

*1963년 폴 코헨은 연속체 가설의 부정이 ZFC 공리계와 무모순임을 증명했다.

연속체 가설:

그럼 저는 증명 불가능 한건가요... 연속체 가설은 슬픕니다...

괴델:

그래도... 이건 공리계가... 좀 부족한게 많으니... 공리계를 차차 수정하면... 될거라고... 봐...

*실제로 괴델이 이런 말을 한 적이 있습니다

코헨:

무엇보다 연속체 가설도 결국은 수학인걸?

연속체 가설:

그래도 인정 받아서 기분 좋습니다! 뽜밤뽜밤~

여담이지만, 저 불완전성 정리 때문에, 

기존의 논리학은 전면적으로 재수정되어야 했어.

위에서 봤던, 힐베르트, 프레게, 러셀을 비롯해 수많은 사람들의 목표를 박살낸 정리이기도 하니까.

 

힐베르트;

내 꿈이...

아무튼 이 불완전성 정리는, 기존 논리학을 무너뜨리기도 했지만,

나중에 앨런 튜링이 이 정리를 증명하는 과정을 이용해 튜링 머신이란 개념을 도입하는데 사용했지. 실제로 튜링이 이 개념을 1936년에 제시했으니까.

그래서 튜링이 컴퓨터의 아버지라고 불리는 게 괜히 그런 게 아니지.

의외겠다 싶지만, 생각보다 컴퓨터의 탄생에 기여한 정리가 바로 불완전성 정리야.

오늘의 수업, 끝!

*번외:

힐베르트 대역으로 리오를 쓴 김에 생각난 썰 하나

1900년 파리 수학자 대회에서...

힐베르트: 

제가 살아있는 동안 리만 가설은 증명될 것이며,

힐베르트:

페르마의 마지막 정리는 여기 앉아계신 관중들의 아이들이 죽기 직전에 증명될 것이며,

힐베르트:

2의 루트 2제곱이 초월수인지 아닌지는 우리의 몇세대가 지나서라도, 증명되긴 어려울 것입니다.

알렉산드르 겔폰트(대역: 나기사):

2의 루트2 제곱은...

테오도어 슈나이더(대역: 미카):

초월수였대~

*1934년 겔폰트-슈나이더 정리로, 원래 힐베르트의 문제 뿐만 아니라 그 일반화한 문제도 해결되었다.

힐베르트:

그래도... 리만 가설은 나 죽기 전에 증명되겠...

러셀:

나 죽기전까지도 증명이 되지 않았답니다?

*힐베르트는 1943년에, 러셀은 1970년에 사망했다. 

앤드루 와일즈 (대역: 모모이):

페르마의 마지막 정리, 증명했다고?

*1995년 페르마의 마지막 정리 증명

그래도 페르마의 마지막 정리는 맞췄네요? 한잔해요.

힐베르트:

리만:

리만 가설 만든 리만입니다 뿅

아직도 안 풀렸습니다 뿅

와일즈: 리만 가설... 7대 밀레니엄 문제...

==============================================

다음은 있을지 모르겠음

근데 유게이 반응 괜찮으면 주제 적어서 요청해주면 하나 쪄오도록 하겠음

사실 리오 놀려먹으려고 생각한 뻘글인건 함정

+ 중간에 일부 비문이 보여서 수정함