괴델의 증명 2

23.1.11

 

아래는 괴델의 증명을 소개하는 두번째 동영상의 대본입니다. 동영상은 맨 아래에 있습니다. 

 

안녕하세요. 오늘의 질문 강국진입니다. 오늘은 지난 시간에 이어서 괴델의 증명을 소개해 보겠습니다. 지난 시간에는 논리적 기호적 수학이 어떤 형식을 가지고 있는가를 소개한 적이 있습니다. 논리적 기호적 수학은 다음으로 이뤄지죠. 부호 또는 어휘, 구성에 대한 규칙, 변형 규칙 그리고 공리들입니다. 

 

여기서 부호는 체스의 말과 같은 것이고, 구성 규칙은 체스판과 같은 것이며, 변형 규칙은 말들이 움직이는 규칙이었습니다. 마지막으로 공리는 체스를 시작할 때의 장기판의 모습이었죠. 

 

자 그럼 오늘은 수학원리 시스템의 일부인 간단한 수학적 공리계에서 출발해 보겠습니다. 왜 이렇게 하는가. 여기에는 두가지 이유가 있습니다. 하나는 이보다 더 복잡한 수학원리의 공리계를 말하기 위한 사전준비입니다. 또 하나는 모순이 없는 즉 정합적으로 완전한 수학 시스템이라는게 뭔가를 더 구체적으로 소개하기 위해서입니다. 

 

여기서 중요한 것은 여러분이 봐야 할 것은 대부분이 구조이지 세부사항이 아니라는 겁니다. 우리는 그걸 메타 매스매티컬 사고 즉 상위수학적 사고라고 부릅니다. 우리는 어떤 정리를 증명하려고 하는게 아니니까 수식이 복잡해 보인다거나, 왜 이 수식이 이렇게 생겼을까 같은 것은 대개 중요하지 않습니다. 게임으로 말하자면 축구는 축구일 뿐입니다. 왜 축구의 규칙은 이런가를 고민하는 건 다른 문제입니다. 물론 수학을 만드는 수학자는 어떤 공리를 선택해야 할까라던가 어떤 표기법을 써야 할까를 고민해야 하겠지만 그건 우리의 일이 아닙니다. 

 

자 그럼 시작해 보겠습니다. 수학원리 시스템의 일부인 이 간단한 수학적 공리계에서 부호는 변항 기호와 상항 기호가 있습니다. 변항기호는 p,q,r로 나가는 기호인데 나중에 보면 나오지만 이 기호들은 그 자리에 다른 문장을 대체해 넣을 수 있습니다. 상항기호는 연결사와 구두점입니다. 연결사에는 not, or, and 그리고 subset이 있습니다. 구두점에는 괄호가 있습니다. 

 

이게 전부입니다. 이걸 나열해서 우리는 수학적 문장을 만드는 겁니다. 하지만 모든 조합이 전부 유효한 문장이 되는 것은 아닙니다. 우리는 구성에 대한 규칙이 있습니다. 예륻 들어서 여기에 소개한 것처럼 p or q는 제대로된 문장이지만 p subset은 제대로 된 문장이 아닙니다. 왜냐면 문장 연결사 subset의 앞뒤에는 모두 문장이 와야만 하기 때문입니다. 

 

그리고 이제까지는 문장이라는 말을 썼는데 이 말은 형식문, formula, 두름, string같은 말로도 씁니다. formula의 번역이 형식문이고 string의 번역이 두름입니다. 중요한 것은 앞에서 소개한 기호들을 나열하면 문장이 되는데 모두가 다 유효한 문장이 되는 것은 아니라는 겁니다. 체스판에서 체스말이 체스판 위에 있어야 하는 것처럼 말입니다. 

 

자. 이미 슬슬 복잡하다고 여기실 분들도 있을지 모르겠습니다. 그런데 여기서 여러분들이 기억해할 것이 있습니다. 그건 or같은 이름은 본래는 의미가 없다는 겁니다. 단지 이 수학적 공리계에서 or가 우리가 일상적으로 아는 or처럼 행동할 뿐입니다. 그리고 우리는 나중에 나오는 변형규칙이나 공리를 통해 사실은 그걸 증명해야 합니다. 그리고 나면 안심하고 or를 우리가 일상적으로 아는 의미처럼 쓸 수 있는 것이죠. 

 

이건 사실 옳다 그르다같은 표현도 그렇습니다. 본래 이 수학 시스템 내부에는 옳다 그르다같은 일상의 의미가 없습니다. 단지 이 시스템에 존재하는 문장들을 두 개의 집합으로 분류를 하는 규칙을 더할 수가 있는 겁니다. p나 q중의 하나가 집합 1에 속하면 p or q는 집합 1에 속한다는 식으로 말이죠. 그러면 올다 그르다같은 표현을 쓸수 있습니다. 이를 좀 더 자세히 알고 싶으신 분은 항진성에 대한 책의 부록 3을 참조하시면 되겠습니다. 

 

자 그럼 계속 해 봅시다. 우리는 이제 변형 규칙과 공리가 남았습니다. 변형규칙에는 대입규칙과 분리규칙이 있습니다. 대입규칙은 앞에서 소개한 변항기호의 자리에는 다른 문장을 대체해 넣을 수 있다는 겁니다. 그렇게 해서 새로운 문장을 만들 수 있다는 거죠. 분리 규칙은 연역법칙입니다. 이건 p 이고 p subset q이면 q라는 규칙입니다. 일종의 삼단 논법같은 규칙인데요. 이를 통해서 우리는 이미 증명된 정리들로 연역을 해서 새로운 정리를 증명할 수 있는 겁니다. 

 

마지막으로 공리입니다. 여기에는 4개의 공리만 있는데요. 복잡해 보이지만 사실 여기서 왜 이런 공리가 선택되었는지를 신경쓸 건 없습니다. 단지 이게 장기판의 처음 모습처럼 우리의 출발점이 되는 문장들이라는 것만 기억하면 되죠. 

 

자 그래서, 이제까지 소개한 걸 종합해 보면 이렇게 됩니다. 이 수학적 공리계는 부호, 구성법칙, 변형규칙 그리고 공리들을 가지게 되었습니다. 일단 이런 것이 정해지면 지난 시간에 말씀 드린대로 우리는 공리에서 출발해서 문장을 변형해 가면서 새로운 문장을 만들 수 있습니다. 그리고 그렇게 만들어진 문장을 우리는 정리라고 부릅니다. 이 과정은 기계적이기 때문에 컴퓨터가 임의적으로 수없이 많은 정리들을 양산할 수 있습니다. 이건 컴퓨터로 하기가 쉬운 일입니다. 

 

이 반대의 과정인 증명은 기계적이 아닙니다. 하지만 우리는 바둑같은 게임을 컴퓨터가 하는 걸 보고 있죠. 마찬가지로 증명하는 과정도 그래서 인공지능 같은 프로그램에게는 반드시 불가능한 영역은 아닙니다. 

 

이러한 시스템에서 우리는 다음을 증명할 수 있습니다. 그건 어떤 문장 A가 있을 때 A와 A의 부정이 동시에 옳을 수는 없다는 겁니다. 이걸 영어로 consistency라고 하는데 한국말로는 정합성, 일관성이라고 합니다. 이걸 증명하는 과정을 대충 말하자면 이렇습니다. 

 

먼저 step 1에서는 p subset 괄호 틸타 p subset q 괄호가 정리라는 것을 증명합니다. 앞에서 소개한 공리들을 조합하면 이걸 만들 수 있다는 거죠. 

 

그 다음의 증명순서는 소위 말하는 귀류법 혹은 배리법이라는 건데요. 우리가 증명하려는 것이 틀렸다면 모순이 생긴다는 걸 보이는 거죠. 

 

그래서 우리는 A와 A의 부정이 모두 옳은 문장 A가 있다고 해보는 겁니다. 그럼 방금 증명한 정리에 대입규칙과 분리규칙을 써서 우리는 새로운 정리를 증명할 수 있습니다. 그 정리가 여기 step 2의 끝에 있는 not A 혹은 틸다 A subset q라는 정리입니다. 

 

그런데 이 A의 부정이 옳다는 것과 이 정리를 써서 분리 규칙을 적용하면 우리는 그냥 변항기호 q가 옳다는 결론에 도달합니다. 그리고 변항기호에는 모든 문장을 대입할 수 있거든요. 그래서 이 과정이 보여주는 것은 모든 유효한 문장이 모두 옳다는 게 되는 겁니다. 하지만 이는 사실이 아닙니다. 따라서 이 시스템의 정합성이 증명되는 겁니다. 즉 이 시스템 안에서는 A와 A의 부정이 동시에 옳을 수는 없다는 거죠. 

 

그런데 어쩌면 어떤 분들은 이거 너무 당연한거 아니냐. 이걸 왜 증명하냐. A와 A의 부정이 어떻게 다 옳을 수가 있냐고 할 겁니다. 그런데 이게 바로 괴델이 증명한 거였습니다. 러셀의 수학공리 시스템 안에는 그런 문장이 있다는 겁니다. 좀 더 정확히 말하면 자연수의 산술적 성질을 기술할 수 있을 정도로 복잡한 시스템에서는 정합성은 증명될 수 없습니다. 이 말은 우리가 공리들을 더해서 더 복잡한 문제를 만들어 이걸 고칠 수 없다는 뜻이죠. 더 복잡한 시스템도 여전히 자연수의 산술적 성질을 기술할 수 있기 때문입니다. 

 

자. 그런데 괴델의 불완전성 정리라는 이름은 뭔가 하는 질문이 있을 수 있습니다. 수학적 시스템에 있어서 완전성이란 어떤 문장이 옳다면 그 문장은 공리적 전개로 모두 증명될 수 있다는 것을 의미합니다. 즉 우리가 충분히 강력한 수학적 공리 시스템을 가지고 있기 때문에 옳은 정리는 모두 공리적으로 전개할 수 있다는거죠. 방금 소개한 단순한 시스템에서는 이 완전성을 증명하는게 가능합니다. 그런데 러셀의 수학공리 시스템은 충분히 복잡하기 때문에 이게 안됩니다. 

 

자 그렇다면 이게 놀라운 거냐. 사실 수학을 하나도 배우지 않은 사람은 그래서 뭐 라고 할지도 모르겠습니다. 하지만 수학을 배운 사람은 좀 다르죠. 고등학교 때 벡터 같은 거 배우신 분들은 기억나는지 모르겠습니다. 3차원 공간의 벡터는 3개의 벡터들로 전개될 수 있죠. 

 

유클리드 기하학에서도 5개의 공리가 있습니다. 그리고 사람들은 이 5개의 공리만 가지면 기하학에 관련된 모든 옳은 정리들은 증명될 수 있다고 믿었습니다. 사실 5번째 공리는 필요없는 거라고 해서 오히려 공리의 수를 줄이려고 많이 노력했지요. 

 

그런데 괴델의 결과가 말하는 것은 유한한 수의 공리를 가지고는 모든 옳은 정리를 다 증명할 수 있는 시스템을 만들 수 없다는 겁니다. 사실 수학계에는 유명한 난제들이 있습니다. 그 중의 하나가 골드바흐의 정리라는 건데 아주 간단합니다. 모든 짝수는 두 개의 소수의 합으로 쓸 수 있다. 이건 경험적으로는 틀린 적이 없는 법칙입니다. 컴퓨터로 하면 수백조까지 이게 맞는 말이라는 것을 증명할 수 있습니다. 그런데도 아직 증명이 없습니다. 괴델의 결과를 생각하면 우리는 혹시 이게 애초에 공리적으로는 증명 불가능한 거 아닌가 하는 의심이 들수도 있겠죠. 

 

 

자. 오늘은 여기까지 하겠습니다. 이제 본격적으로 괴델의 증명을 소개하기 위한 준비가 다 끝났습니다. 남은 건 괴델 수란 무엇인가 하는 것이고 결정불가능한 형식문 G는 어떻게 만드는가 하는 겁니다. 이건 다음 시간에 하겠습니다. 지금까지 오늘의 질문 강국진이었습니다. 안녕히 계세요.