위키백과

타르스키의 정의 불가능성 정리

수리 논리학에서 타르스키의 정의 불가능성 정리(영어: Tarski's undefinability theorem)는 형식 의미론에 있어서 자기표현에 관한 중요한 제한을 가하는 정리이다. 이 정리를 비형식적으로 기술하면, "산술적 진리는 산술 내에서 정의될 수 없다"이다. 1936년 알프레트 타르스키가 기술하고 증명하였다.

이 정리는 충분히 강력한 모든 형식 체계(formal system)에 더욱 일반적으로 적용될 수 있는데, 이때는 "어떤 체계의 표준 모형 내에서의 진리는 그 체계 내에서는 정의될 수 없다"는 것을 보여준다.

정리 편집

1차 산술(페아노 공리계)의 언어 L과 그 표준 모델 N을 잡으면, (L, N)은 '산술의 1차논리 언어의 해석'을 이룬다. L 속의 모든 x는 각각 괴델 수매김 g(x)를 가진다. T가 N에서 참인 L-문장들의 집합이라 하고, T*를 T 속의 문장들의 괴델 수의 집합이라 하자. 여기서 T*가 1차 산술의 논리식으로 표현가능한가 하는 것이 이 정리의 주제이다.

타르스키의 정의 불가능성 정리 (산술): T*를 정의하는 L-논리식 True(n)은 존재하지 않는다. 즉, 모든 L-논리식 A에 대하여 True(g(A)) ↔ A 가 성립하게 하는 True(n)은 존재할 수 없다.

비형식적으로 말해서 정리가 말하는 바는, 어떤 형식 산술이 주어졌을 때 그 산술에서의 참의 개념은 그 산술로 표현가능한 방법으로는 나타낼 수 없다는 것이다. 이는 "자기표현"의 범위에 중요한 제한을 가한다. T*를 확장(extension)으로 하는 논리식 True(n)은 정의하는 것이 가능하나, 이는 L의 표현력을 뛰어넘는 메타언어를 통해서만 이루어질 수 있다. 예를 들어 1차 산술의 진리 술어는 2차 산술로 정의가능하다. 그러나, 이 식은 원래의 언어 L 속의 문장에 대한 진리 술어만을 정의할 수 있다. 메타언어를 위한 진리술어는 표현력이 더욱 강한 메타-메타언어에서 구성해야 하고, 이러한 꼴이 반복된다.

위 정리는 사실 산술 위계(산술적으로 정의가능한 모든 논리식을 위계로 분류한 것)에 관한 포스트의 정리(Post's theorem)의 따름정리로써 나온 것으로, 실제 Tarski (1936)의 발표 몇년 이후에 제시된 것이다. 이 타르스키 정리의 의미론적 증명은 다음과 같은 귀류법으로 이루어졌다. T*가 산술적으로 정의가능하다고 하면, 포스트의 정리에 의해 어떤 n에 대하여   위계의 논리식으로 T*를 정의할 수 있어야 한다. 그런데 T*는 모든 k에 대해  -정의불가능하다. 이렇다면 산술 위계가 성립하지 않아 포스트의 정리와 모순된다.

일반화 편집

본래 타르스키가 1936년 증명한 정리는 위의 진술보다 더 강력한 것으로, 특히 완전한 구문론적 방법만으로 증명되었다. 이는 부정(¬)을 포함하고 자기언급이 가능한(정확히는 괴델의 불완전성 정리 증명에 등장하는 diagonal lemma가 성립하는) 형식 언어 모두에 적용가능하며, 물론 1차 논리도 포함된다.

타르스키의 정의 불가능성 정리 (일반): 부정을 포함하는 형식언어 해석 (L, N)에, 괴델 수매김 g(x)가 있어서 모든 L-논리식 A(x)에 대해 B ↔ A(g(B))가 N에서 성립하게 하는 B가 존재하게 된다 하자. N에서 참인 L-문장의 괴델 수의 집합을 T*라 하자. 그렇다면 T*를 정의하는 L-논리식 True(n)는 존재하지 않는다. 즉, 모든 L-논리식 A에 대하여 True(g(A)) ↔ A 가 N에서 참이 되는 L-논리식 True(n)은 존재할 수 없다.

이 정리의 증명은 위와 유사하게 귀류법으로 완성된다.

타르스키 정리는 이론의 진리가 더 강한 이론에서 정의되는 것을 부정하는 것이 아니다. 예를 들어 1차 페아노 산술의 N에서 참인 논리식의 (괴델 수의) 집합은 2차 산술의 논리식으로 정의가능하다. 한편 2차 산술의 표준 모형에서 참인 문장들의 집합은 1차 ZFC 집합론으로 정의가능하다.

같이 보기 편집

참고 문헌 편집

원본 주소 "https://ko.wikipedia.org/w/index.php?title=타르스키의_정의_불가능성_정리&oldid=33236779"