타르스키의 증명에 관한 노트

[TheNewHegel]

타르스키의 글 「진리와 증명」 중 ‘진리와 증명의 관계’ 절에서 타르스키가 수행하는 증명은 보다 상세하게는 다음처럼 정리될 수 있다.

1. 명확한 구문론적 규칙과 형식적 증명 규칙을 포함하는 자연수의 산술에 관한 이론 N을 대상언어로 하고, 이를 설명하는 형식화된 메타이론을 M이라 하자.

2. M의 모든 증명 규칙은 N의 산술 규칙으로 번역될 수 있다.

3. 역으로 N의 모든 산술 규칙은 M의 증명 규칙으로 번역될 수 있다.

4. 따라서 N의 모든 증명 가능한 문장은 M으로 번역 가능하며, M의 모든 증명 가능한 문장은 N으로 번역 가능하다.

5. 따라서 N와 M에서 증명 가능한 문장의 수는 같다.

6. 그런데 M의 모든 참인 문장들이 N으로 번역 가능한 것은 아니다.

7. 따라서 N과 M에서 증명 가능한 문장의 수와 참인 문장의 수는 같지 않다.

8. 그런데 모든 증명 가능한 문장은 참이다.

9. 따라서 모든 증명 가능한 문장의 수는 모든 참인 문장들의 수보다 많을 수 없다.

10. 그러므로 증명 불가능하면서 참인 문장이 존재한다.

타르스키는 글에서 명시적으로 언급하지 않지만, 이 “증명 불가능하면서 참인 문장”은 메타언어에 속한다. 이를 위의 추론으로부터 도출할 수 있다.

11. 6에 의해, M에서 참이면서 N에 속하지 않는 문장이 존재한다.

12. 따라서 증명 불가능하면서 참인 문장이 M에 존재한다.

결국 「진리와 증명」에서 타르스키는 대상언어를 이용해 메타언어 내 증명 불가능하면서 참인 문장의 존재를 증명한 셈이다.

한편 타르스키가 언급하는 괴델의 정리인 제1불완전성 정리가 증명한 것은 다음의 명제이다.

자연수 체계를 포함하는 모든 체계에는, 증명 불가능하면서 참인 명제가 적어도 하나 존재한다.

이는

자연수 체계를 포함하는 모든 체계에서, 모든 참인 명제는 증명 가능하다.

를 부정함으로써 얻어진다.

자연수 체계를 포함하는 하나의 체계(S라 하자) 내에서 모든 참인 명제가 증명 가능하다고 가정하자. 각각의 식에 일대일 대응하는 괴델수를 부여함으로써, 증명 개념을 포함하는 S의 문장을 자연수 체계의 문장으로 번역할 수 있다. 이때 S에 있는 다음의 문장 G도 괴델수 g를 통해 자연수 체계로 번역할 수 있다.

G: ~(∃x)Dem(x, Sub(y, 17, y))=g

G는, 괴델수가 g인 식의 증명은 존재하지 않는다는 의미이다. 그런데 G가 거짓이라고 가정할 경우, G가 거짓이라는 점으로부터 ~G에 대한 증명이 있음을 보일 수 있다. 그런데 이는 ~G와 모순이다. 마찬가지로 G가 참이라고 가정할 경우, G에 대한 증명이 있음을 보일 수 있다. 이는 G와 모순이다. 결국, 하나의 체계 내에서 모든 참인 문장이 증명 가능하다고 가정할 경우, 체계 S는 모순적이라는 결론을 얻게 된다.

결국 증명 체계가 무모순적이라면, G와 ~G 중 어떤 것도 증명할 수 없다. 그리고 G의 의미상 G는 참이다. G가 증명 불가능하면서 참이므로, 증명 불가능하면서 참인 문장이 존재한다.

이제 타르스키의 불완전성 증명은 괴델의 증명과는 무엇이 유사한가?

(1) 두 증명이 이끌어내는 결론이 같다.

(2) 한 쪽이 다른 한 쪽을 포함하는 두 개의 체계가 등장한다. 괴델에서 이는 자연수 체계 N과 N을 포함하는 임의의 체계 S였으며, 타르스키에서 이는 대상언어 N과 N을 포함하는 메타언어 M이었다.

그러면 두 증명은 어떤 점에서 차이가 있는가?

(1) 괴델은 거짓말쟁이 역설 문장에 해당하는 G를 끌어들임으로써 귀류법적으로 증명을 수행한다. 반면 타르스키는 애초에 역설이 발생하지 않도록 여러 가지 제한 조건을 마련했다. 특히 메타언어의 모든 참인 문장들이 대상언어의 문장들로 번역될 수는 없다는 조건이 여기에 해당한다. 그리고 타르스키는 역설이 발생하지 않는 조건들을 바탕으로 제1불완전성 정리에 해당하는 결론을 이끌어낸다.

타르스키의 용어를 빌리자면, 괴델은 대상언어와 메타언어에서 모든 참인 문장들의 집합과 모든 증명 가능한 문장들의 집합이 일치한다고 가정한 후, G를 통해 모순을 이끌어냄으로써 이 가정의 거짓을 증명했다. 한편 괴델의 정리를 빌리자면, 타르스키는 자연수 산술 체계 N과 이를 포함하는 임의의 체계 S를 구분한 후, 두 체계의 관계에서 역설이 발생하지 않는 몇 가지 조건들을 부여한다. 그리고 결론에 대해 귀류법이 아닌 증명을 수행한다.

(2) 타르스키의 증명은 “증명 불가능하면서 참인 문장”이 존재한다는 점은 말해주지만, 이 문장이 무엇인지는 말해주지 않는다. 한편 괴델은 “증명 불가능하면서 참인 문장”의 구체적인 실례인 G를 이미 갖고 있다.

타르스키는 다음처럼 말한다. “그러나 우리는, 이론의 언어 내에 정식화되어 있으면서 참이지만 증명 불가능한 문장들이 있다는 사실을 의식하고 있으며, 우리가 관심을 가지고 증명하려 시도하는 것들 가운데 그러한 문장들이 발생할 가능성을 무시할 수 없다.”(Tarski, 1969: 77) 그리고 타르스키의 말을 방증하듯 증명 불가능하면서 참인 문장의 실례가 G 말고도 존재한다. 예컨대 괴델과 코헨(J. Cohen)은 칸토어(G. Cantor)가 제시한 연속체 가설이 증명 불가능하면서 참인 명제임을 증명했다.

[YOUN]

메타언어가 '증명 규칙’을 포함한다는 설명은 잘못되었다고 생각해요. 타르스키가 말하는 증명은 순전히 '형식적 증명(formal proof)'이잖아요. 이런 증명은 애초에 메타언어의 영역에서 논의되는 주제가 아니에요. 대상언어에서 공리에 연역 규칙을 반복적으로 적용하여 획득되는 게 '형식적 증명’이니까요. 타르스키의 논문에서 메타언어는 '진리 조건’을 정의하기 위해 제시될 뿐, '증명’이나 '증명 가능성 조건’과는 무관해요. 다만, 증명 가능한 문장이 모두 '참’이라는 점에서 증명 가능한 문장과 그 문장 사이의 관계를 메타언어로도 표현할 수 있을 뿐이지, 메타언어 사이에 대상언어와 구별되는 별도의 증명 규칙이 성립하지는 않아요.

아래 문단의 내용을 아마 오해하신 것 같아요.

“I t was pointed out in the first section that the metalanguage which enables us to define and discuss the notion of truth must be rich. It contain s the entire object-language as a part, and therefore we can speak in it of natural numbers, sets of numbers, relations among numbers, and so forth. But it also contains terms needed for the discussion of the object-language and its components; consequently we can speak in the metalanguage of expressions and in particular of sentences, of sets of sentences, of relations among sentences, and so forth. Hence in the metatheory we can study properties of these various kinds of objects and establish connections between them.”(Tarski, 1969: 76)

이 문단은 메타언어 문장 사이에, 산술학의 규칙과 구별되는, 별도의 증명 규칙이 성립한다는 내용이 아니에요. 단순히 산술학의 문장 사이의 관계를 메타언어를 사용하여 나타낼 수 있다는 의미에요. 즉, (1) 메타언어는 대상언어보다 풍부하다. (2) 메타언어는 대상언어를 모두 포함한다. (3) 그래서 대상언어로 말해질 수 있는 모든 것은 메타언어로도 말해질 수 있다. (4) 게다가 메타언어는 '대상언어’와 '대상언어의 요소들’에 대해 논의할 때 필요한 용어까지도 포함한다. (5) 따라서 우리는 메타언어를 가지고서 [대상언어의] 표현, 문장, 문장의 집합, 문장의 관계에 대해서도 말할 수 있다.

그러니까, 여기서 말하는 표현, 문장, 문장의 집합, 문장 사이의 관계란 ‘대상언어’ 내부의 것들이에요. 대상언어에서 제시되는 '형식적 증명’이 바로 문장과 문장 사이의 관계로 성립하니까요. 그리고 우리는 대상언어 내부의 그 관계를 '메타언어’로도 표현할 수 있다는 거에요. 메타언어가 별도의 증명 규칙을 갖고 있는 게 아니라, 단지 대상언어의 증명 규칙이 메타언어로도 표현된다는 의미인 거죠. '형식적 증명’은 순전히 대상언어 내부의 공리와 정리 사이의 관계에서 성립하고, 메타언어가 별도의 증명 규칙을 갖지는 않는 거죠.

[TheNewHegel]

지적해주신 점에 대해 골똘히 생각해 봤습니다만, 저는 여전히 N과 관계하는 M이 형식적 증명을 구비한 형식화된 이론이어야 한다고 생각합니다.

일단 문헌적 전거는 다음과 같습니다.

진리와 증명가능성의 정의 양자 모두, 메타언어 내에서 정식화되었으며 특히 형식화된 산술학과 그 언어에 대한 우리의 연구를 위해 고안된 새로운 이론에 속한다. 이 새로운 이론은 메타이론 또는, 보다 구체적으로 메타산술학이라고 일컬어진다. 메타이론의 공리들, 정의되지 않은 용어들 등등 메타이론이 구성되는 방식에 대해서 상세히 설명하지는 않을 것이다. 우리는, 증명 가능한 문장들의 집합이 참인 문장들의 집합과 일치하는지의 문제를 정식화하고 해결하는 일은 메타이론의 틀 내에서라는 점만 지적한다.(Tarski, 1969: 75-76)

증명 불가능한 참인 문장을 이끌어내기 위해 타르스키가 사용하는 두 체계는 메타언어와 대상이론이 아니라 메타이론과 대상이론입니다. 위 문장에서 타르스키는, 메타언어 자체를 대상이론과 관계 지우기보다, 메타언어 내에서 진리와 증명가능성을 정의하는 이론을 정립한 후 이를 대상이론을 해석하는 도구로 사용합니다. 여기서 진리뿐만 아니라 증명가능성의 정식화된 정의도 메타이론에 속합니다. (물론 여기서 증명가능성이란 문맥상 다름 아닌 ‘형식적 증명’에 의한 증명 가능성일 것입니다.) 다만 위 구절에서 타르스키가 메타이론의 정확한 구성 방식을 명시하지 않기 때문에, 저로서도 텍스트에서 결정적인 전거를 제시하기는 어렵습니다.

그런데 나아가 저는 타르스키의 증명이 성립하기 위해서는 메타이론 또한 형식적 증명 개념을 구비한 형식화된 이론으로 해석되어야 한다고 생각합니다. 왜냐하면 말씀하셨듯 증명 불가능한 참인 문장은 애초에 대상이론이 아닌 메타이론에 속하기 때문입니다. 타르스키의 증명이 “대상이론에서는 증명될 수 없지만 메타언어에서는 증명 가능할 수도 증명 불가능할 수도 있는 문장이 있다”가 아닌 “대상이론(N)을 포함하는 모든 이론 내에는 반드시 증명 불가능한 참인 문장이 있다”를 결론으로 가지려면, 해당 문장은 메타이론에서 증명 불가능해야 합니다. 이때 메타이론이 증명 규칙을 구비하지 않는 비형식적인 이론이라고 한다면, 대상이론이 아닌 메타이론에 속하는 이 문장의 증명 불가능성 개념이 무엇인지 이해하기가 어렵습니다. (“대상이론으로 증명 불가능하지만 메타이론에서는 참인 문장이 존재한다.”로 해석할 수는 없을 것입니다. 애초에 해당 문장이 대상이론에 속하지 않기 때문입니다.)

괴델의 경우를 들자면, 제가 알기로 자연수 체계와 형식적 연산 체계 PM은 둘 다 형식화된 이론입니다. 그래서 괴델은, 자연수 체계를 포함하는 모든 형식적 체계에는 그 체계 내부에서 증명 불가능한 참인 문장이 존재한다는 점을 밝혔습니다. 이때 증명 불가능한 문장은, 단순히 자연수 체계 내에서만 증명 불가능한 것이 아니라 자연수 체계를 포함하는 모든 형식적 체계에서 증명 불가능합니다. 괴델의 정리와 같은 결론을 타르스키가 도출하고자 한다면, 타르스키도 괴델과 마찬가지로 메타이론을 형식화된 이론으로 상정해야 한다는 것이 제 생각입니다.

[YOUN]

아, '메타언어(meta-language)'가 아니라 75쪽에 나오는 '메타이론(meta-theory)'이라는 용어에 주목하셨던 거네요. 그러면 분명 얘기가 달라지긴 할 것 같습니다. 말씀하신 것처럼, 타르스키가 논문 자체 내에서 메타이론에 대해 그다지 많은 설명을 하지 않기 때문에 이 논문만으로는 대상이론과 메타이론 사이의 정확한 관계에 대해 말하기는 힘들지만, 그래도 '산술학(arithmetic)'과 ‘초수학(meta-mathematics)’ 사이의 관계에서는 위에서 적으신 내용이 성립할 수 있을 것 같긴 하네요. 다만, 타르스키가 논문의 결론 부분인 76쪽에서 강조하는 건 "증명 가능성은 '메타언어’에사 '대상언어’로 번역되는 반면, 참은 그렇게 번역되지 않는다."이다 보니, (“One can describe briefly what has been achieved by saying that the definition of provability has been translated from the metalanguage into the object-language. On the other hand, the discussion of the notion of truth in common languages strongly suggests the conjecture that no such translation can be obtained for the definition of truth; otherwise the object-language would prove to be in a sense semantically universal, and a reappearance of the antinomy of the liar would be imminent.”)저는 대상 '언어’와 메타 ‘언어’ 사이의 관계로 논의를 구성하는 게 논문의 본래 구조를 제일 잘 지켜줄 수 있는 방법이 아닌가 하는 생각이 드네요.