<괴델, 에셔, 바흐> 제1부 : GEB - 서론 (2) page ~ 31

본 포스트의 내용은 괴델, 에셔, 바흐를 읽으며 기록한 것으로, 직접 인용하거나 요약한 내용임을 밝힙니다.

서론 : 음악-논리학의 헌정(A musico-logical offering) (2)

괴델

바흐와 에셔의 이상한 고리에 ‘유한과 무한 사이에 갈등이 있어서’ 역설이 있는 것 같은 느낌이 있는데, 여기서 수학적인 것이 개입되어 있음을 느낄 수 있다.

괴델의 이상한 고리는 에피메니데스 역설을 수학언어로 번역한 것이다.

이 명제는 거짓이다.

이는 1단계로 된 이상한 고리이고, 자기 지시를 통해 역설을 만든다. 마찬가지로 괴델은 수학적 추론을 사용해서 수학적 추론 자체를 탐구하고자 했고, 이를 통해 불완전성 정리(Incompleteness Theorem)라는 결과를 얻어냈다.

ω-무모순인 귀납적인 모든 논리식의 집합 κ에 대하여 귀납적인 집합식 r이 상응하며 그 결과 ν Gen r이나 Neg(ν Gen r) 그 어느것도 Flg(κ)에 속하지 않는다. (이때 ν는 r의 자유변수이다.)

너무 어려운데, 우리말로 풀면 다음과 같다.

수론의 무모순인 공리체계들은 반드시 결정 불가능한 명제를 포함한다.

불완전성 정리는 진주와 같은 결과물이고, 그 자체에서 이상한 고리를 찾기는 어렵다. 이상한 고리는 진주조개에, 즉 불완전성 정리를 증명하는 과정에 있다.

에피네미데스의 역설이 언어의 자기-지시적인 진술인 것 처럼, 괴델의 불완전성 정리의 증명은 자기-지시적인 수학적 명제의 작성에 의존하고 있다. 그러나 언어에 대해서 언어로 말하는 것에 비해, 수에 대한 명제가 어떻게 자신에 대해서 말할 수 있는지를 알아내는 것은 무척 어려운 일이다.

간단하게 정리하면 아래와 같다.

(정수론에 국한하면) 수학적 명제는 정수의 속성에 대해 어떤 주장을 한다. 그러나 정수 자체는 명제가 아니며, 정수의 속성도 명제가 아니다. 즉, 수론의 명제는 수론의 명제에 대해서 아무것도 주장하지 않는다. 수론의 명제는 다만 수론의 명제일 뿐이다.

괴델은 여기서 표면적인 사실 아래의 것을 탐구한다. 수가 어떤 방식으로든 명제를 나타낼 수 있다면, 수론의 명제가 수론의 명제에 대한 명제가 될 수 있을 것이라고 생각했다. 이를 괴델은 “괴델 수 매기기(Gödel numbering)”이라는 코드를 통해 접근한다. 괴델 수에서 숫자는 기호 또는 기호열을 나타내고, 수론의 명제는 기호열이므로 괴델 수로 표현된다. 즉, 수론의 명제는 숫자에 대한 명제인데 이는 곧 괴델 수라는 숫자로 표현될 수 있으므로, 수론의 명제에 대한 명제라는 해석으로 이어질 수 있다. 즉, 상이한 두 층위에서 해석할 수 있게 하고, 이는 곧 자기-지시적이며, 이상한 고리를 발생시킨다.

여기서 괴델은 영리하게 “이 수론의 명제는 거짓이다”가 아니라 “이 수론의 명제는 어떤 증명도 가지지 않는다”를 초점으로 삼았다. 증명의 개념은 모호하기에, 괴델은 러셀과 화이트헤드의 <수학 원리>의 체계 위에서의 증명으로 범위를 좁혔다. 즉, 괴델 문장 G는 아래와 같이 표현할 수 있다.

이 수론의 명제는 <수학 원리>의 체계 안에서 어떤 증명도 가지지 않는다.

괴델 문장 G는 <수학 원리> 내에서 증명할 수 없지만 참이 되고, <수학 원리>의 불완전성을 공격한다. 그러나, 이는 비단 <수학 원리> 뿐만이 아닌 그 어떤 공리체계에도 적용되고, 어떤 공리체계이건 증명가능성이 참보다는 약한 개념임을 보여준다.

수리논리학 : 개괄

수리논리학 = 추론이라는 사고 과정을 기계화하려는 시도

집합론의 여러가지 역설 중 가장 유명한 것은 러셀의 역설(Russell’s paradox)이다.

자신을 원소로 가지지 않는 평범한 집합과 자신을 원소로 포함하는 집합이 존재할 때, “모든 평범한 집합들의 집합” R은 어느것도 될 수 없다.

R이 평범한 집합이라면? 모든 평범한 집합들의 집합인 자기 자신에 포함되므로 R이 평범한 집합이 될 수 없다.

R이 자신을 원소로 포함하는 집합이라면? R이 모든 평범한 집합들의 집합이므로 R이 평범한 집합이 되어야만 한다.

이와 같이 직관을 형식화된 또는 공리화된 추론 체계와 조화시키려고 하는데서 문제가 발생한다.

그렐링의 역설은 언어에서 비슷한 문제가 발생한다. 형용사를 자기-기술적인 형용사와 자기-기술적이 아닌 형용사로 구분하자. 예를 들면 pentasyllabic(다섯 음절의)라는 형용사는 자기-기술적이고, bisyllabic(두 음절의)라는 형용사는 자기-기술적이 아니다 (놀랍게도 영어와 한국어 모두).

그렇다면 “자기-기술적이 아닌” 이라는 형용사는 어느 부류에 속하는가?

자기-기술적이 아니라면? “자기-기술적이 아닌”이라는 스스로의 의미를 나타내고, 자기-기술적이게 된다.

자기-기술적이라면? “자기-기술적이 아닌”이라는 본래의 의미에 반하게 된다.

이러한 역설들에는 자기-지시(self-reference) 또는 “이상한 고리”의 속성이 존재하는데 이를 추방하고자 하는 시도가 다음 문단에서 이어진다.

다음의 문장은 거짓이다. 앞의 문장은 참이다.

앞서서 설명한 “자기-기술적이 아닌”이라는 단어와 달리, 위의 두 문장에서는 여러 단계로 이상한 고리를 형성한다.

중요한 것은, 각각의 문장은 전혀 문제가 없다는 것이다. 즉 문장에 문제가 있어서 역설이 발생하는 것이 아니라, 두 문장이 서로를 “지시하는” 방식, 즉 형식에서 자기-지시가 발생한다.

이상한 고리 제거하기

러셀과 화이트헤드는 <수학 원리>에서 유형 이론을 통해 이상한 고리를 제거하고자 했다. 그들은 계층 질서를 도입하여 어떤 유형의 집합이 더 낮은 유형의 집합이나 대상들만을 포함할 수 있도록 했다. 이는 R과 같은 집합을 집합에서 배제하고, 역설을 성공적으로 제거했다. 그러나 이는 직관에 반하는 결과이며, 동시에 언어에서는 더욱 이상한 일이 된다.

언어에서 계층화를 수행하면 최하위에는 대상 언어가 존재하고 그 언어를 표현하는 메타언어 (대상언어의 문법 규칙이나 문장들을 설명하는) 가 존재한다. 그렇다면 메타메타언어, 메타메타메타언어 등도 존재하게 되는데, 이와 같이 모든 언어나 문장은 특정한 계층에 속하게 되고 그렇지 못한 발화는 무의미한 것으로 판단된다.

그런데 이는 결국 그 이론을 토론하는 행위 자체를 무의미한 것으로 바꿔버린다. 예컨대, “이 책에서 나는 유형이론을 비판한다”와 같은 평범한 문장이 있다고 생각하자. 이 문장은 두 가지 이유로 무의미한데, “이 책에서”는 오직 “메타책”에서만 언급할 수 있는 말이고, 이는 “메타책”의 경우에는 “메타메타책”에서 언급할 수 있는 말이 되는 연쇄적인 문제를 발생시킨다. 또한, 나는 “나”를 절대 언급할 수 없다.

결국 계층화, 또는 성층화(stratification)를 통해 이상한 고리를 해결하려는 시도 자체는 적어도 그 맞춤 체계 안에서는 성공적으로 보이지만, 직관에 반하며 체계 외부에서는 말해주는 것이 거의 없다.

무모순성, 완전성, 힐베르트 프로그램

다비트 힐베르트는 <수학 원리>에서 정의된 체계가 무모순이면서 완전하다라는 것을 <수학 원리>를 사용하여 증명하라”라는 도전과제를 제시하였다. 이는 늪에 빠진 자신이 자신의 신발끈을 잡아당겨 끌어올리는 격이지만, 힐베르트는 적어도 제한적인 상황에서는 효과적일 것으로 희망했다. 그러나 이는 괴델의 불완전성 정리를 통해 붕괴되었다. 괴델은 어떤 공리체계라도 무모순이면 수론의 모든 참을 산술할 수 없음을 드러냈다. 즉 어떤 체계 A를 사용하여 A가 무모순임을 증명하면, A가 모순이 된다.