23.1.16
괴델의 증명의 세번째 소개 마지막 동영상입니다. 대본은 아래에 있으며 동영상은 맨 마지막에 링크해 두었습니다.
안녕하세요. 오늘의 질문 강국진입니다. 오늘은 괴델의 증명을 세번째로 소개하겠습니다. 그리고 이게 이 시리즈의 마지막이기도 합니다. 오늘은 다른 날보다 약간 더 집중을 필요로 할 지도 모르겠습니다. 만약 중간에 이해가 안가시는 부분이 있으면 화면을 멈추고 천천히 생각해 보신다음에 따라오시면 좋겠습니다.
중요한 건 복잡한 표현이나 수식에 겁먹지 말아야 한다는 겁니다. 여기서 하는 건 실제로 수학을 한다기 보다는 할 수 있다, 존재 한다라는 가능성의 확인이 많거든요. 그러니까 이런 식으로 보자면 1+1이나 백자리 숫자 더하기 백자리 숫자나 원리적으로 같은 겁니다. 더하기를 한다는 것으로 똑같기 때문입니다. 그러니까 숫자가 길고 복잡하게 나와도 겁먹을게 없는 거죠.
자 그럼 시작해 보겠습니다.
오늘은 수학원리의 시스템을 다룰텐데요. 그래봐야 차이는 크게 나지 않습니다. 논리적 기호적 수학은 부호, 구성 규칙, 변형 규칙, 공리들로 이뤄진다는 점은 똑같습니다. 그리고 2,3,4번에 대해서는 오늘 할말이 없습니다. 지난 시간에 한 것과 같거나 딱히 알아야 할 이유가 없기 때문입니다. 다만 오늘은 더 확장된 시스템의 부호에 대해서는 아셔야 합니다.
오늘의 부호들 중에 먼저 상항 부호는 다음 처럼 12개가 있습니다. 복잡해 보이죠. 하지만 별로 그렇지도 않습니다. 다른 건 지난 시간에 한 것과 같고, 여기에는 존재한다라는 이 E가 뒤집어진 표현이 있고 0이 있습니다. 그리고 바로 다음 숫자를 말하는 s도 있으며 우리가 익숙한 +나 x가 있습니다. 그래서 이 시스템은 산술적 원리가 표현 가능한 공리계가 되는 겁니다. 이 표기법에 대해서는 뒤에서도 조금씩 더 설명드리겠습니다.
다만 복습삼아 다시 말씀드리면 여기 나오는 부호들의 의미는 이 부호 자체에서 나오는게 아니라 변형법칙과 공리들에 의해서 주어지는 관계에서 나오는 것입니다. 그러니까 0이 0처럼 행동하고 +가 +처럼 행동한다라는 것은 증명을 해야 하는 겁니다. 괴델은 이와 같이 증명할 수 있는 부호의 의미들을 원초 재귀적 진리라고 불렀습니다. 다시 말해서 우리가 구구단같은 공식을 외워서 산수를 하지 않습니까. 마찬가지로 우리가 아는 일상적 의미를 가지고 저 부호들을 쓰는 건 그런 겁니다. 그렇게 써도 된다는 걸 이미 증명해 둔 거죠.
참고로 말씀드리면 여기에는 0만 있고 1이나 5같은 숫자는 없습니다. 하지만 바로 다음 숫자라는 s가 있기 때문에 예를 들어 ss0가 2처럼 행동합니다. 그래서 s0+ss0은 sss0가 됩니다. 즉 1더하기 2는 3이 되는 것이죠. 이같은 관계가 정리로 다 증명되어 있다는 겁니다.
상항기호가 있으니까 변항기호도 있죠. 그런데 여기서는 세가지 종류의 변항기호들이 있습니다. 숫자 변항은 그 자리에 숫자를 집어 넣을 수 있는 기호입니다. 문장 변항은 그 자리에 문장을 바꿔 넣을 수 있습니다. 그리고 마지막으로 술어변항은 소수이다라던가, 1보다 크다 같은 술어가 대치될 수 있습니다.
그래서 이제 이런 표기법을 써서 수학적 문장을 만들어 봅시다. 앞에서 존재한다는 표현과 s를 소개했었는데요. 이 기호들을 쓰면 이런 문장들을 만들 수 있습니다. 먼저 앞에서 1 더하기 2는 3이다를 어떻게 쓰는지 소개했었죠. s0+ss0 이렇게 쓰는 겁니다.
조금 더 복잡하고 존재한다는 부호를 쓰는 문장도 만들 수 있습니다. 예를 들어 y의 다음 숫자인 x라는 숫자가 존재한다라는 문장을 생각해 봅시다. 이 문장은 수학적으로는 어떤 x가 존재해서 x는 sy와 같다라는 문장이 됩니다. 중요한 것은 부호들의 나열이 문장이 되는 것이고 옳은 문장들은 공리와 변형규칙을 통해서 증명을 할 수 있다는 겁니다. 지난 시간에도 말쓰드렸지만 그런 문장들을 우리는 정리라고 부르죠.
여기서 오늘의 첫번째로 중요한 주제인 괴델 수라는 것이 나옵니다. 괴델은 기호의 연속인 문장을 하나의 숫자로 암호화하는 시스템을 만들었습니다. 그래서 모든 수학 문장에 숫자를 하나 지정할 수 있게 된 겁니다. 그 방법은 간단합니다. 우리는 먼저 상항기호들에게 1에서 12까지의 괴델수를 지정할 수 있습니다. 그럼 변항기호는 어떻게 하는가. 변항기호중에서 숫자 변항은 12보다 큰 소수를 순서대로 지정합니다. 예를 들어 x는 13, y는 17 이렇게 말이죠. 문장 변항이나 서술 변항도 마찬가지입니다. 다만 문장 변항은 소수의 제곱을 지정합니다. 그리고 서술변항은 소수의 세제곱을 지정합니다.
이게 약간 복잡해 보일 수 있고 왜 소수가 나오나 싶을 수 있습니다. 하지만 이건 간단한 아이디어입니다. 소수는 자기 자신으로 밖에 나눠지지 않죠. 혼돈이 없습니다. 그리고 나중에 보면 나오지만 괴델수라는 큰 수를 주면 그걸 소인수 분해를 합니다. 그러면 그 소인수 분해는 오직 한가지 방식으로 밖에 행해지지 않습니다. 그래서 숫자 하나가 복잡한 문장을 암호화할 수 있는 겁니다.
자. 이제 부호의 괴델 수가 끝났으니까 우리는 이제 문장이 주어졌을 때 괴델 수를 정하는 방법을 생각해 볼 수 있습니다. 그 방법은 먼저 문장부호들을 다 각각의 괴델 수로 쓰는 겁니다. 그렇게 하면 여기 화면에 나왔듯이 여러개의 숫자가 수학문장을 대체하게 됩니다. 그런데 이건 하나의 수가 아니죠. 그래서 이걸 다시 소수의 지수의 곱으로 계산합니다. 그래서 8,4,13으로 나가는 이 부호에 대한 괴델 수들이 전체 문장의 괴델 수 m을 주게 됩니다. 문장의 괴델 수를 정할 때에도 우리는 순서대로 소수를 나열하고 각각의 소수의 지수로 앞에서 찾아낸 부호들의 괴델 수를 씁니다. 이렇게 해서 문장이 하나 있으면 우리는 그것에 대해서 하나의 숫자인 괴델 수를 계산할 수 있는 겁니다.
괴델 수는 여기서 끝나는게 아닙니다. 괴델 수는 심지어 연속되는 문장에 대해서도 계산할 수 있습니다. 예를 들어 여기 두개의 문장이 있다고 해 봅시다. 첫번째 문장은 y의 다음수인 x가 있다는 문장입니다. 그리고 이 문장의 괴델수는 m이라고 해 봅시다. 두번째 문장은 y자리에 0을 대체해 넣은 겁니다. 어떻게 보면 두 번째 문장은 첫번째 문장에서 증명되어져서 나오는 거죠. 대입규칙을 써서 말입니다. 이 두번째 문장의 괴델 수를 n이라고 하면 이제 n을 증명하는 과정을 하나의 괴델 수로 쓸 수도 있습니다. 그건 다시 각 문장의 괴델 수를 또 한번 소수들의 지수로 쓰고 그 수를 곱하는 겁니다. 그렇게 만들어 진 괴델 수 k는 이제 두번째 문장을 증명하는 과정에 대한 괴델 수가 되는 겁니다.
그래서 정리하면 이렇습니다. 우리가 괴델 수를 가지면 우리는 그걸 수학문장으로 번역할 수 있습니다. 그리고 그 반대도 마찬가지입니다. 그래서 누가 243000000이라는 괴델 수를 주면 우리는 그걸 소인수 분해를 합니다. 그랬더니 그 지수가 6 5 6으로 나오는 거죠. 그럼 표에 따라서 그걸 다시 부호로 번역을 합니다. 그렇게 되면 우리는 0 은 0 이라는 수학문장을 가지게 되는 겁니다.
그런데 이런 걸 왜 할까요? 이런 걸 하는게 사실 괴델의 증명의 핵심입니다. 중요한 것은 모든 수학적 문자들은 문장들의 나열인 증명까지 포함해서 괴델수로 쓸 수가 있다는 겁니다. 이 같은 과정은 마치 기하학을 좌표계를 도입해서 대수학으로 만든 데카르트의 과정과 같습니다. 그리고 그렇게 하면 전통적인 기하학 증명보다 좌표계를 가지고 기하학적 정리를 증명하는게 훨씬 쉽습니다. 괴델이 괴델수를 써서 한 것은 어찌보면 별거 아닌 간단한 일 같지만 기호의 논리학을 숫자들간의 산술학으로 바꾼 거라고 할 수 있습니다. 생각해 보면 모든 문장이 괴델 수를 가지기 때문에 우리가 증명을 할 때처럼 수학 문장을 바꿔간다는 것은 괴델수의 입장에서 보면 숫자에서 숫자로 바뀌어가는 과정이라는 거죠. 그러니까 산술과정이라는 겁니다. 그래서 우리는 괴델이 기호의 논리학을 산술화했다라는 말을 할 수가 있습니다.
여기서 중요한 것이 또 있습니다. 왜 괴델수가 괴델의 증명의 핵심인가 하는 것은 괴델 수도 수라는 사실에서 나옵니다. 좀 헛깔리수도 있는데요. 괴델이 산술화시킨 수학원리의 시스템은 산술적인 기술을 할 수 있는 즉 숫자들을 다룰 수 있는 시스템이었습니다. 그런데 괴델수도 수이기 때문에 이런 시스템은 자기 자신에 대한 말 즉 소위 메타 수학적이라고 말해지는 말을 하나의 수학적 문장으로 나타낼 수 있게 된다는 겁니다. 그럼 어떻게 되는가. 비로 이 문장은 틀렸다 같은 결정 불가능한 문장이 가능해 지게 됩니다. 이 문장은 틀렸다같은 문장이 옳다면 이 문장은 틀린 문장이 되니까 모순이 생기게 되는 것이죠.
이 부분이 중요하기 때문에 예를 하나 들어 보겠습니다. 예를 들어 0은 제 자신과 같지 않다라는 수학 문장이 있다고 해 봅시다. 이 문장은 사실이 아니지만 어쨌거나 수학입니다. 그런데 이 수학 문장의 첫번째 기호가 틸다 이다같은 문장은 수학이 아니죠. 이건 표기법에 대한 문장입니다. 더 이상 수학이 아닌 겁니다. 그래서 본래는 이런 문장을 앞에서 소개한 표기법으로는 쓸 수가 없었습니다. 기호같은 말은 없으니까요. 그런데 여기에 괴델수가 끼어들면서 이상한 일이 생기는 겁니다. 0은 제 자신과 같지 않다라는 본래의 문장은 괴델 수를 가집니다. 그 수를 a라고 합시다. a는 구체적으로 여기 아래에 써져 있는 것처럼 구할 수 있습니다.
그런데 이 a를 사용하면 첫번째 기호는 틸다이다같은 문장을 수학적으로 쓸 수가 있습니다. 그건 바로 a가 2로는 나눠지지만 2의 제곱으로는 나눠지지 않는다라는 문장입니다. 다시 말해서 a의 첫번째 소수의 지수는 1이라는 문장이죠. 1이 틸다에 대한 괴델 수 이기 때문입니다. 이 문장은 완전히 숫자에 대한 문장이기 때문에 수학적 형식문으로 쓸 수 있습니다. 이렇게 해서 본래는 표기 할 수 없었던 메타수학적 표현이 수학적으로 표현가능해 지게 됩니다. 그리고 이런 것이 가능하기 때문에 앞에서 말한 것처럼 이 문장은 틀렸다처럼 결정 불가능한 문장이 생겨나게 됩니다. 오늘 강의의 후반 핵심은 바로 이 결정불가능한 문장을 구체적으로 무엇인가 하는 것입니다.
자 이렇게 괴델 수를 써서 표현 가능해지게 된 문장의 또 다른 예를 생각해 보겠습니다. 그건 바로 괴델 수 x를 가진 문장은 괴델 수 z를 가진 문장을 증명한다라는 문장입니다. 본래 증명을 어떻게 하는가 하는 것은 산술적 관계가 아닙니다. 그런데 괴델수가 기호논리학을 산술화했기 때문에 이제 이 관계는 두 개의 숫자 즉 두개의 괴델 수 사이의 관계가 되는 겁니다. 물론 이 관계는 어마어마하게 복잡합니다.
하지만 처음 말씀드렸듯이 실제로 이 관계가 얼마나 복잡하냐 하는 것은 중요하지 않습니다. 산술적 관계가 있기만 하면 그건 수학적 문장 즉 형식문으로 쓸 수 있다는 것이 중요한 것이죠. 그리고 일단 수학적 문장으로 써지면 즉 기호들의 나열로 써지면 그 문장도 다시 하나의 괴델수로 표현 가능합니다. 이건 실제로 그 수학적 문장을 쓴다거나 그 괴델수를 구한다는 뜻이 아니라 그런 수가 존재한다는 겁니다. 사실 그 문장은 본래의 표기법으로는 절대로 인간이 쓸 수 없을 정도로 길고 복잡합니다. 그런데도 그게 존재한다는 것만 알면 우리는 그걸 대표하는 표현을 도입할 수가 있죠. 여기서는 Dem(x,z)가 그겁니다. 여기서 혼동하면 안되는게 앞에서 소문자일때는 이것은 x와 z 사이의 산술적 관계를 말하는 겁니다. 1더하기 2=3 뭐 그런 관계죠. 하지만 앞에가 대문자가 되면 Dem(x,z)는 그렇게 찾아낸 관계를 표현한 수학적 문장입니다.
그렇게 복잡하다는 Dem(x,z)를 알고 나면 이제 이런 문장도 쓸 수 있습니다. 괴델 수 z를 가진 문장은 증명 가능하다거나 증명 불가능하다는 거죠. 이건 간단한게 어떤 문장이 주어졌을 때 어떤 또 다른 문장이 하나 존재해서 그 둘 사이에 증명 관계가 성립한다. 뭐 이런 표현이기 때문입니다. 거기에 부정인 틸다 하는 붙이면 증명 불가능하다 이런 문장이 되는 것이죠. 증명 불가능하다. 우리는 이런 표현까지 왔습니다. 그래서 복잡하기만 하지 언제 괴델의 증명에 도달할까 싶지만 사실 거의 다 온거나 마찬가지입니다.
자 그럼 문제의 증명 불가능한 문장 G를 만들어 봅시다. 증명불가능한 수학적 문장 G의 뜻은 일상어로는 이렇게 됩니다. 나를 증명하는 것은 불가능 하다. 이 문장이 증명 불가능한 이유는 아마 직관적으로는 다 아실 거라고 생각합니다. 이 문장이 옳으면 이 문장을 증명 할 수 없어야 하니까요. 하지만 이렇게 직관적으로 하면 그 모순은 피할 수 있는 모순이 됩니다. 그래서 괴델은 엄밀하게 수학적 문장이 표현가능해지는 시스템을 만든 거죠.
이제 새로운 표현 하나만 익히면 G를 쓸 수 있습니다. 그 표현은 sub입니다. sub(x,17,z)라는 표현을 봅시다. 먼저 말씀 드리면 여기서 x, 17, z는 전부 숫자입니다. 그리고 17은 변항기호 y의 괴델수입니다. 그래서 sub(x,17,z)가 말하는 것은 괴델 수 x를 가진 문장 즉 형식문에서 y가 있으면 y의 자리에 z라는 숫자를 대치한 문장이라는 겁니다. 여기서도 대문자 소문자가 중요합니다. 지금 말한 것은 맨 앞이 대문자 Sub입니다. 이것도 문장이니까 우리는 그것의 괴델수를 찾을 수 있죠. 그 괴델수는 소문자 sub(x,17,z)로 씁니다.
예를 들어 봅시다. 앞에서도 나온 수학 문장이 있습니다. 그건 y의 다음수인 x가 존재한다라는 문장이었죠. 이 문장의 괴델 수를 a라고 해 봅시다. 그러면 대문자 Sub(a,17,3)은 괴델 수 a인 문장 즉 방금 말한 y의 다음수에 대한 문장에서 y를 찾아서 y 자리에 3을 넣으라는 게 됩니다. 그러면 여기 두번째에 쓴 것처럼 되겠죠. 하지만 이건 아직 완벽한 형식문이 아닙니다. 왜냐면 원래는 3이라는 기호가 없으니까요. 3은 sss0으로써야 하는 겁니다. 그렇게 나온 문장을 우리가 대문자 Sub(a,17,3)이라고 쓴다는 겁니다. 그리고 이 문장의 괴델수를 소문자 sub(a,17,3)으로 쓴다는 거죠. 사실 이게 알고 나면 별거 아니지만 혼돈이 오기 쉬운 거죠. 저도 그랬습니다. 그러니까 다음 페이지로 가기전에 화면을 잠시 멈추고 이 표현의 의미와 표기법에 대해서 다시 한번 생각해 보시는 것이 좋을 것입니다.
자 이제 드디어 증명불가능한 문장 G를 쓸 차례입니다.우리는 우선 문장 A를 씁니다. 이 문장은 괴델수 소문자 sub(y,17,y)를 가진 문장은 증명할 수 없다는 뜻을 가지고 있습니다. 기억하시겠지만 Dem이라는 것은 증명관계에 있다는 문장이죠. 여기서 당황하시는 분도 있을 수 있는게 17이 y라고 했는데 y가 이 표현안에 있다는 겁니다. 이걸 혼동하시면 안됩니다. 기호 y의 괴델수가 17이지 y가 무조건 17인게 아닙니다. 이 문장도 괴델 수를 가집니다. 그리고 그 괴델 수를 n이라고 합시다.
이 문장 A에서 y 자리에 n을 집어넣으면 우리는 증명불가능한 문장 G의 표현을 가집니다. 그리고 이 문장의 괴델 수는 바로 소문자 sub(n,17,n)입니다. 자 여기가 바로 멈출 때 입니다. 지금 뭐가 뭔지 모르겠다라고 하시거나 왜 G 문장의 괴델 수가 이렇게 나오느지 모르겠다는 분은 멈춰서 생각을 해보시기 바랍니다. n은 문장 A의 괴델 수 입니다. 그리고 그 문장의 y자리에 n을 집어넣어서 우리가 문장 G를 만들었지요. 그러니까 문장G는 대문자 Sub(n,17,n)이기도 한 겁니다.
이 문제의 문장 G는 앞에서 말한 성질을 가집니다. 즉 나를 증명하는 것은 불가능하다는 뜻이 됩니다. 그리고 모두 산술적인 표현으로 이뤄져 있는 문장이죠. 즉 수학원리의 시스템은 혹은 산술적 원리가 표현가능한 시스템은 원천적으로 증명불가능한 문장을 가지게 되는 겁니다.
그런데 여기서 우리는 한가지 사실에 주목해야 합니다. 그건 문장 G는 공리적 전개를 통해서 증명하는 것이 불가능하지만 그럼에도 사실이라는 겁니다. 즉 옳은 문장입니다. 왜냐면 증명불가능하니까요. 옳은 문장이 존재하지만 그걸 공리적으로 증명할 수 없을 때 우리는 그 시스템을 불완전하다고 합니다. 이래서 괴델의 불완전성 정리가 나오는 겁니다. 괴델의 불완전성 정리가 말하는 것은 우리가 공리를 더해도 이 문제가 사라지지 않는다는 겁니다. 그 시스템이 산술적 원리가 표현가능하면 같은 문제가 생기기 때문입니다.
괴델은 여기에 더하여 이 시스템이 정합성도 없다는 것도 보였습니다만 그건 더이상 말하지 않겠습니다. 직관적으로는 당연해 보이죠. 증명못하는 문장이 있으니까요.
자 이렇게 해서 괴델의 증명의 주요한 내용을 다 소개했습니다. 그런데 아마도 이걸 들으시는 분들은 수학자가 아니죠. 그래서 우리는 이 모든 것을 통해서 우리가 뭘 배웠는가를 생각해 볼 필요가 있습니다. 괴델의 정리가 말하는 것은 공리적으로는 혹은 논리적으로는 모든 옳은 주장을 증명할 수 없다는 겁니다. 자기 자신을 언급하는 표현이 가능하기 때문입니다. 그래서 우리는 우선 논리라는게 무한한 힘을 가진게 아니구나 하는 것을 배우게 되죠.
하지만 어떤 분들은 그래서 기계적으로 혹은 결정론적으로 움직이는 컴퓨터 같은 것이 이 괴델의 증명의 영향을 받는다고 생각합니다. 즉 컴퓨터의 한계를 보여주고 인간의 위대함을 보여주는 거라는 거죠.
이 말은 간단한 이유때문에 사실이 아닙니다. 컴퓨터 안의 프로그램은 반드시 폐쇄적이지 않기 때문입니다. 컴퓨터도 외부로부터 입력을 계속 받으면 그때마다 프로그램이 바뀔 수 있습니다. 그러면 정해진 공리만 따르는 시스템이 아니게 되는 것이죠. 이런 일을 하는 대표적인 프로그램이 바로 인공지능입니다.
이 입력이 대단한 것일 필요도 없습니다. 예를 들어 그 입력이 랜덤넘버라도 됩니다. 무작위한 입력이 들어와서 프로그램이 무작위하게 조금씩 달라지면 그때마다 프로그램은 조금씩 다른 걸 시도하는 겁니다. 물론 그 입력이라는게 새로운 데이터일 수도 있습니다. 그러면 프로그램은 이제까지의 정책을 그에 따라 조금 수정하겠죠. 이건 정해진 공리와 변형법칙을 반복하는 것과는 다릅니다. 그러니까 괴델의 증명은 인공지능의 한계를 말해주는 것은 아닙니다.
하지만 이렇게 괴델의 증명과 인공지능을 함께 생각하다 보면 그것이 인간이라던가 인간의 지능에서도 통하는 말이 아닐까 하는 생각을 하게 됩니다. 즉 인간이 자기의 한계를 넘고 지능적일 수 있는 것도 그것이 폐쇄적이 아니고 주변 환경에 개방되어 있기 때문이 아닐까 하는 생각이 드는 겁니다.
오늘은 여기까지 하겠습니다. 괴델의 증명을 다 들어주신 분들이 계시다면 대단히 감사합니다. 이제까지 강국진이었습니다. 안녕히 계세요.
댓글