우선 스크롤의 압박 죄송합니다 m(_ _)m 만날 웃대에서 놀다가 할 일이 없어 디씨에 왔습니다. 참고로 디씨는 처음입니다 ^^;; 저도 와봐야지 와봐야지 하다가 빠져버리는 것이 두려워서~ 여기저기 돌아다니다가 과학갤러리에 왔는데, 괴델이 화제가 되어있는 걸 보고 참새가 방앗간을 그냥 지나갈 수 없어서 글을 써봅니다^^ 괴델의 정리...정말 매력적이죠! 괴델은 \'자연수를 다루는 수론체계에서 증명 불가능한 명제가 있다\'라는 것을 보였는데요, 괴델 뿐만 아니라 폴란드의 철학자 타르스키가 \'어떠한 체계의 실태는 그 체계 자체로부터는 결코 연역불가능하다\' 것을 보이기도 했죠. 아란 츄링이라던가 비교적 근년의 그레고리 챠이틴등이 더욱 발전시켰고요. 아무튼 이것이 중요한 이유는 인간의 사고가 그 당시에 생각되던 것보다 훨씬 복잡하고 비기계적이라는 것을 보여주었기 때문이라 생각합니다. 간단하게 논리적으로 설명해보겠습니다. 솔직히 이거 쓰는 본인도 제대로 이해하지 못하고 그냥 넘어갔던 부분이 많으니, 그냥 이런 느낌이구나~하고 생각해주세요^^ 그러므로 불확실한 부분이 많더라고 양해를;;;; 따지고 드시면 저도 모른다고 할 수 밖에 없습니다ㅡ.ㅡ 원래 증명은 조금 더 엄밀하고 복잡한데, 간단히 하기 위해 변수가 하나일때, 그리고 몇 가지 사항은 엄밀히 따지지 않고 사용하겠습니다. 이것만으로도 맛보기는 가능할 듯.... 변수가 x 하나인 논리식을 P(x)라고 쓰기로 합시다. 그리고 자연수만 생각합시다. 의미는 \'변수 x는 P라는 성질을 가지고 있다\'라고 합시다. 예를 들어 \'2는 어떠한 자연수의 제곱이 아니다\'라는 식에서는 x=2, P:어떤 자연수의 제곱이 아니다.....이런 식입니다. 이걸 기호로 나타내면 ~Ea:(a*a)=SS0 가 됩니다. 참고로 저 E는 뒤집어진 E입니다. 아시죠? \'존재한다\'를 의미하는 그 기호입니다. 그리고 ~는 부정을 의미합니다. 0은 0이고, S는 그 다음 수를 의미합니다. S0=1, SS0=2..... 풀이하면 \'제곱하여 2(=SS0)가 되는 a는 존재하지 않는다\'입니다. 여기서 괴델의 천재성이 들어납니다. 임의의 기호를 그 기호의 고유의 자연수에 대응시킬 수 있습니다. 어차피 기호는 유한하니까요. 그 고유의 자연수를 \'괴델넘버\'라고 합니다. 예를 들어 더글라스 호프스태터는 그의 저서 \'괴델, 에셔, 바하(GEB)\'에서 ~:223, E:333, S:123 등을 이용했습니다. 호프스태터식으로는 위의 논리식은 223 333 262 636 362 262 236 262 323 111 123 123 666 이 됩니다. 자, 논리식을 저렇게 바꿔 놓으면 그냥 수입니다. 즉, 크기를 비교할 수 있죠. 그리곤 작은 것부터 차례대로 써나갑니다. 물론 무한개가 있지만, 가산무한에 대한 토론으로 끌고가긴 싫으니, 신경쓰지 말아주세요~ 칸톨에 대해 자세히 아시는 분은 지금부터 하는 방식에 대해 친근감을 많이 느끼실 것이라 봅니다. 이제부터가 괴델이 증명한 것입니다. (1) 모든 논리식P를 순서대로 세워, 번호 n을 붙여 P_n(x)라 나타낸다. ;첨부한 그림의 모양대로 표 안에 나란히 정리합니다. 논리식을 괴델넘버로 나타내면 순서대로 정리하는게 가능합니다. 즉, 여기엔 변수가 하나인 모든 논리식이 망라되어 있습니다. (2) 빨간색으로 그려놓은 방향으로 P_n(x)를 스캔해 나간다. ;대각선상에 있는 항들은 0번째, 4번째, 12번째....이런 식으로 출현합니다. 왜 0부터인지는 곧 나옵니다. P_n(n)은 2n*n+2n번째에 나오겠죠.(제곱을 ^2라고 쓰기 싫어서 풀어씁니다 ^^;;) (3) 이 논리식 표에 \'n번째 논리식은 증명가능하다\'라는 의미의 논리식 prove(n)이 이 표 안에 있다고 하자. (4) ~prove(2x*x+2x)라는 논리식을 생각하자. ;물론 의미는 2x*x+2x번째 논리식은 증명불가능하다 입니다. 게다가 일단 논리식이므로 이 표안에 들어있겠죠. 다시 강조하지만 이 표 안에는 일변수의 \'모든\' 논리식이 다 들어있습니다! 이 ~prove(2x*x+2x)가 m행의 P_m(x)라고 합시다. 중요(5)!!!여기서 조금 얍삽하지만 정말 감탄스런 조작을 합니다!!             P_m(x)의 변수에 m을 대입한다. ;P_m(m)이 나타납니다. 이 논리식은 표의 대각선 상에 존재하고, 2m*m+2m번째에 등장합니다. 즉, P_m(m)과 ~prove(2m*m+2m)은 같은 식입니다. 이제 슬슬 수상해지죠?? 뜻은 자기 자신은 증명불가능하다...입니다. (6) 이제 마무리 지읍시다. ~prove(2m*m+2m)이 참이라 증명되었다고 가정합시다. 이 논리식은 P_m(m)와 같기 때문에 P_m(m)도 참이라 증명되었습니다. 자, 그럼 (3)에서 준비해두었던 prove(n)을 꺼내봅시다. 의미는 n번째 논리식은 증명가능하다..였습니다. 방금 위에서 P_m(m)이 증명가능하다고 했습니다. P_m(m)은 2m*m+2m번째 나오는 논리식이니까 prove(2m*m+2m) 이 논리식 또한 참이군요! 즉, 어떤 논리식과 그 부정이 동시에 참이라는 결과가 나왔습니다. 이건 수론의 체계가 모순되어 있다는 걸 의미하죠! (7) 참고로 ~prove(2m*m+2m)가 거짓이라 증명되었을 때도 생각해봅시다. 즉, ~~prove(2m*m+2m)이 증명된 경우입니다. 이 때도 마찬가지로 모순이 나타납니다. 흥미있으신 분 생각해보시길^^ (8)결론 수론체계가 모순을 용납하지 않는다 하면, ~prove(2m*m+2m)가 참임을 보이는 것도 거짓임을 보이는 것도 불가능하다. 여기서 명제의 의미를 다시 생각해보면 ~prove(2m*m+2m)는 P_m(m)은 증명불가능하다....를 의미한다. 그리고 그것을 증명하지 못했으니까, 이 명제는 분명히 옳다. 이 명제가 옳다는 것은 이 체계보다 높은 곳(바깥)에서 바라볼 수 있는 인간에게는 판단가능하다. 이상 괴델의 제1불완전성정리에 대한 간단한 설명을 마칩니다. 참고로 여기서 쓰인 논법은 \'대각선논법\'이라 불리는데, 매우 유용합니다. 바이러스 백신 매주 업데이트하시기 귀찮으시죠? 하지만 어쩔 수 없습니다. 그 프로그램이 장차 바이러스로 활동할 것인지 판단하는 완전무결한 백신프로그램은 만들 수 없거든요... 이것도 괴델의 불완전성정리의 확장판이라고 볼 수 있습니다. 대각선논법으로 증명할 수 있고요. 허접한 글 끝까지 읽어주신 것에 대해 감사드립니다. 만약 이상한 점이 있어도 너무 뭐라 하진 말아주세요~