타르스키의 정의 불가능성 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[수리 논리학]]에서 '''타르스키의 정의 불가능성 정리'''({{llang|en|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에 대하여 <math>\Sigma^0_n</math> 위계의 논리식으로 T*를 정의할 수 있어야 한다. 그런데 T*는 모든 k에 대해 <math>\Sigma^0_k</math>-정의불가능하다. 이렇다면 산술 위계가 성립하지 않아 포스트의 정리와 모순된다.

== 일반화 ==
본래 타르스키가 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]] 집합론으로 정의가능하다.

== 같이 보기 ==
* [[진리론]]
* [[산술 위계]]
* [[괴델의 불완전성 정리]]

== 참고 문헌 ==
* J.L. Bell, and M. Machover, 1977. ''A Course in Mathematical Logic''. North-Holland.
* [[조지 불로스|G. Boolos]], J. Burgess, and R. Jeffrey, 2002. ''Computability and Logic'', 4th ed. Cambridge University Press.
* J.R. Lucas, 1961. "[http://users.ox.ac.uk/~jrlucas/Godel/mmg.html Mind, Machines, and Gödel] {{웹아카이브|url=https://web.archive.org/web/20070819165214/http://users.ox.ac.uk/~jrlucas/Godel/mmg.html}}". Philosophy 36: 112–27.
* R. Murawski, 1998. [https://web.archive.org/web/20110608131053/http://www.staff.amu.edu.pl/~rmur/hpl1.ps Undefinability of truth. The problem of the priority: Tarski vs. Gödel]. History and Philosophy of Logic 19, 153–160
* [[레이먼드 스멀리언|R. Smullyan]], 1991. ''Godel's Incompleteness Theorems''. Oxford Univ. Press.
* [[레이먼드 스멀리언|R. Smullyan]], 2001. "Gödel’s Incompleteness Theorems".  In L. Goble, ed., ''The Blackwell Guide to Philosophical Logic'', Blackwell, 72–89.
* {{저널 인용|제목=Der Wahrheitsbegriff in den formalisierten Sprachen|저널=Studia Philosophica|성=[[알프레트 타르스키|A. Tarski]]|url=http://www.ifispan.waw.pl/studialogica/s-p-f/volumina_i-iv/I-07-Tarski-small.pdf|연도=1936|권=1|쪽=261–405|보존url=https://web.archive.org/web/20140109135345/http://www.ifispan.waw.pl/studialogica/s-p-f/volumina_i-iv/I-07-Tarski-small.pdf|보존날짜=9 January 2014|url-status=dead|확인날짜=26 June 2013}}
* [[알프레트 타르스키|A. Tarski]], tr J.H. Woodger, 1983. "The Concept of Truth in Formalized Languages". [http://www.thatmarcusfamily.org/philosophy/Course_Websites/Readings/Tarski%20-%20The%20Concept%20of%20Truth%20in%20Formalized%20Languages.pdf English translation of Tarski's 1936 article].  In A. Tarski, ed. J. Corcoran, 1983, ''Logic, Semantics, Metamathematics'', Hackett.

[[분류:논리철학]]
[[분류:진리론]]
[[분류:수리논리학]]