타르스키의 정의 불가능성 정리
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
타르스키의 정의 불가능성 정리는 형식 언어가 자체의 진리 개념을 표현할 수 없다는 것을 증명하는 정리이다. 이 정리는 알프레드 타르스키가 1930년대에 발표했으며, 쿠르트 괴델의 불완전성 정리와 유사하게 형식 논리의 한계를 보여준다. 타르스키의 정리는 충분히 강력한 형식 언어는 자체의 의미론을 표현할 수 없으며, 대상 언어의 진리를 표현하기 위해서는 대상 언어보다 표현력이 더 강한 메타 언어가 필요하다는 것을 의미한다. 이 정리는 1차 산술의 메타수학적 속성에 대한 괴델의 불완전성 정리보다 동기 부여와 증명이 더 쉽고, 다양한 형식 시스템에 적용될 수 있다. 타르스키의 정리는 자기 지칭의 한계를 보여주며, 수학 및 철학 분야에 광범위한 영향을 미쳤다.
더 읽어볼만한 페이지
- 진리론 - 카마
카마는 힌두교와 불교에서 감각적 즐거움, 정서적 매력, 미적 쾌락을 포괄하는 개념으로, 힌두교에서는 삶의 네 가지 목표 중 하나이며, 불교에서는 깨달음의 장애물로 여겨진다. - 진리론 - 진실
진실은 학문이 탐구하는 대상이며, 검증 가능한 객관적 사실에 기반하여 사실들의 상관관계에서 원리를 발견해야 학문적 진실에 도달한다. - 논리철학 - 마음
마음은 의식, 사고, 지각, 감정, 동기, 행동, 기억, 학습 등을 포괄하는 심리적 현상과 능력의 총체이며, 다양한 분야에서 연구되고 인간 삶의 중추적인 역할을 한다. - 논리철학 - 이성
이성은 인간의 사고, 추론, 판단 능력을 포괄하는 개념으로, 고대 그리스어 로고스에서 유래되었으며, 지식, 진리, 행복 추구에 중요한 역할을 해왔지만, 현대 사회에서는 이성에 대한 비판적 시각도 존재한다. - 수리논리학 - NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다. - 수리논리학 - 셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.
| 타르스키의 정의 불가능성 정리 |
|---|
2. 역사
쿠르트 괴델은 1931년에 불완전성 정리를 발표했는데, 이는 형식 논리의 구문을 1차 산술 내에서 표현하는 방법을 보여주는 방식으로 증명했다. 산술의 형식 언어의 각 표현식에는 고유한 숫자가 할당된다. 이 절차는 괴델 수 부여, '코딩' 등으로 알려져 있으며, 더 일반적으로는 산술화라고 한다. 특히, 표현식의 다양한 '집합'은 숫자의 집합으로 코딩된다. 다양한 구문적 속성(예: '공식', '문장' 등)에 대해, 이러한 집합은 계산 가능하다. 게다가, 모든 계산 가능한 숫자 집합은 어떤 산술 공식으로 정의할 수 있다. 예를 들어, 산술 문장의 코드 집합과 증명 가능한 산술 문장의 코드 집합을 정의하는 산술 언어의 공식이 있다.
Tarski's undefinability theorem영어 (산술)에 따르면, N에서 참인 L-문장들의 집합 T에 대해, T 속 문장들의 괴델 수 집합인 T*를 정의하는 L-논리식 True(n)은 존재하지 않는다. 즉, 모든 L-논리식 A에 대하여 True(g(A)) ↔ A 가 성립하게 하는 True(n)은 불가능하다.[2]
타르스키의 정의 불가능성 정리는 원래 타르스키가 1936년에 증명한 것보다 더 강력한 형태로 일반화될 수 있다. 이 일반화된 정리는 부정을 포함하고 자기언급이 가능한 형식 언어에 적용된다.
타르스키의 정의 불가능성 정리는 형식 산술에서 '참'의 개념을 그 산술 내에서 표현할 수 없음을 보여준다. 이는 자기표현 범위에 중요한 제한을 가한다. 예를 들어 1차 산술의 진리 술어는 2차 산술로 정의할 수 있지만, 이는 원래 언어 L 속 문장에 대한 진리 술어만 정의할 수 있다. 메타언어의 진리 술어는 더 강력한 메타-메타언어에서 구성해야 하며, 이 과정이 반복된다.[3]
레이먼드 스멀리언은 타르스키의 정의 불가능성 정리가 괴델의 불완전성 정리가 받은 주목을 받을 만하다고 강력하게 주장했다.[5] 괴델의 정리가 모든 수학이나 더 논란이 되는 철학적 문제[6]에 대해 많은 것을 말할 수 있는지는 명확하지 않다. 반면 타르스키의 정리는 직접적으로 수학에 관한 것이 아니라, 실제적 흥미를 가질 만큼 충분한 표현 능력이 있는 모든 형식 언어의 선천적인 한계에 관한 것이다. 그러한 언어는 대각선 보조정리를 적용할 수 있을 정도의 자기 지칭이 필연적으로 가능하다. 타르스키 정리의 광범위한 철학적 의의는 더 뚜렷하게 나타난다.
[1]
논문
How Tarski Defined the Undefinable
2015
정의 불가능성 정리는 이러한 인코딩이 진실과 같은 의미론적 개념에 대해 수행될 수 없음을 보여준다. 이는 충분히 풍부한 해석 언어가 자체 의미론을 표현할 수 없음을 보여준다. 그 결과로, 일부 대상 언어의 의미론을 표현할 수 있는 모든 메타 언어 (예: 페아노 산술 언어의 공식이 산술의 표준 모델에서 참인지 여부에 대한 체르멜로-프렝켈 집합론에서 정의 가능한 술어[2])는 대상 언어의 표현력을 초과해야 한다. 메타 언어는 대상 언어에 없는 원시적인 개념, 공리, 규칙을 포함하므로 대상 언어에서 증명할 수 없는 정리를 메타 언어에서 증명할 수 있다.
정의 불가능성 정리는 일반적으로 알프레드 타르스키의 것으로 여겨진다. 괴델은 또한 1931년에 발표한 불완전성 정리를 증명하면서 1930년에 정의 불가능성 정리를 발견했으며, 타르스키의 1933년 논문이 발표되기 훨씬 전에 발견했다(Murawski 1998). 괴델은 정의 불가능성에 대한 자신의 독립적인 발견에 대해 어떠한 것도 발표하지 않았지만, 1931년 존 폰 노이만에게 보낸 편지에서 이를 설명했다. 타르스키는 1929년에서 1931년 사이에 그의 1933년 모노그래프 "''연역 과학의 언어에서 진실의 개념''"의 거의 모든 결과를 얻었으며, 폴란드 청중에게 이에 대해 이야기했다. 그러나 그가 논문에서 강조했듯이, 정의 불가능성 정리는 그가 이전에 얻지 못한 유일한 결과였다. 1933년 모노그래프의 정의 불가능성 정리(Twierdzenie I)에 대한 각주에 따르면, 이 정리와 증명 초안은 원고가 1931년에 인쇄소로 보내진 후에야 모노그래프에 추가되었다. 타르스키는 1931년 3월 21일 바르샤바 과학 아카데미에 자신의 모노그래프 내용을 발표했을 때, 이 자리에서 자신의 연구와 괴델의 불완전성 정리에 대한 짧은 보고서 Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit|결정의 확정성과 일관성에 대한 일부 메타수학적 결과de[4], 오스트리아 과학 아카데미, 빈, 1930에 부분적으로 근거한 몇 가지 추측만 표현했다고 보고한다.
3. 정리 (산술)
이는 형식 산술에서 참의 개념이 그 산술 내에서 표현될 수 없음을 의미한다. 이는 "자기표현"에 중요한 제약을 가하며, T*를 정의하는 논리식 True(n)은 L의 표현력을 넘어서는 메타 언어를 통해서만 가능하다. 예를 들어, 1차 산술의 진리 술어는 2차 산술로 정의될 수 있지만, 이는 원래 언어 L 속 문장에 대한 진리 술어만을 정의할 뿐이다. 메타언어의 진리 술어는 더 강력한 메타-메타언어에서 구성해야 하며, 이 과정이 반복된다.[2]
이 정리는 산술 위계에 관한 포스트의 정리(Post's theorem)의 따름정리로, Tarski (1936)보다 몇 년 후에 제시되었다. 의미론적 증명은 귀류법을 사용한다. T*가 산술적으로 정의 가능하다면, 포스트의 정리에 의해 어떤 n에 대해 위계의 논리식으로 정의될 수 있어야 한다. 그러나 T*는 모든 k에 대해 -정의 불가능하므로, 산술 위계가 성립하지 않아 포스트의 정리와 모순된다.[2]
4. 일반화
타르스키의 정의 불가능성 정리 (일반): 부정을 포함하는 형식언어 해석 (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)은 존재할 수 없다.[2]
이 정리는 귀류법을 통해 증명된다. 만약 T*를 정의하는 논리식 True(n)이 존재한다면, 모든 L-논리식 A에 대해 True(g(A)) ↔ A 가 성립해야 한다. 그러나 대각선 보조정리에 의해, 이러한 동치에 대한 반례, 즉 "거짓말쟁이" 문장 S가 존재하여 S ↔ ¬True(g(S))가 성립한다. 이는 모순이므로, True(n)은 존재할 수 없다.[3]
타르스키 정리는 이론의 진리가 더 강한 이론에서 정의되는 것을 부정하는 것이 아니다. 예를 들어, 1차 페아노 산술의 N에서 참인 논리식의 (괴델 수의) 집합은 2차 산술의 논리식으로 정의 가능하다. 한편 2차 산술의 표준 모형에서 참인 문장들의 집합은 1차 ZFC 집합론으로 정의 가능하다.[4]
5. 함의와 영향
이 정리는 산술 위계에 관한 포스트의 정리의 따름정리로도 도출할 수 있다. 만약 T*가 산술적으로 정의 가능하다면, 어떤 n에 대해 \(\Sigma^0_n\) 위계의 논리식으로 정의할 수 있어야 한다. 그러나 T*는 모든 k에 대해 \(\Sigma^0_k\)-정의 불가능하므로, 산술 위계가 성립하지 않아 포스트의 정리와 모순된다.
타르스키는 더 강력한 정리를 증명했는데, 이는 부정(¬)을 포함하고 자기언급이 가능한 (괴델의 불완전성 정리 증명에 등장하는 대각선 보조정리가 성립하는) 모든 형식 언어에 적용된다.
타르스키 정리는 한 이론의 진리가 더 강한 이론에서 정의되는 것을 부정하지 않는다. 예를 들어 1차 페아노 산술의 N에서 참인 논리식(의 괴델 수) 집합은 2차 산술의 논리식으로 정의 가능하다. 2차 산술의 표준 모형에서 참인 문장 집합은 1차 ZFC 집합론으로 정의할 수 있다.
레이먼드 스멀리언은 타르스키의 정의 불가능성 정리가 괴델의 불완전성 정리만큼 중요하다고 주장했다. 타르스키의 정리는 충분히 표현력이 있는 모든 형식 언어의 내재적 한계에 관한 것이며, 대각 보조정리를 적용할 수 있을 만큼 충분한 자기 참조가 가능하다.
정의 불가능성 정리는 괴델이 1930년에 이미 발견했으나, 1931년에 존 폰 노이만에게 보낸 편지에서만 언급했다.[3] 타르스키는 1933년 논문에서 이 정리를 발표했으며, 1931년에 원고가 인쇄된 후 추가했다.[4]
6. 현대적 의의와 비판
해석된 언어는 그 언어가 그 언어에 특유의 의미론적 개념을 정의하는 술어와 함수 기호를 포함할 때 정확히 '강한 의미론적 자기 표현(strongly-semantically-self-representational)'이 된다. 따라서 요구되는 함수는 식 ''A''를 그 진리값 ||''A''||에 대응시키는 "의미론적 평가 함수"와 항 ''t''를 그 대상에 대응시키는 "의미론적 지시 함수"를 포함한다. 타르스키의 정리는 다음과 같이 일반화된다. "충분히 강력한 언어는 강한 의미론적 자기 표현이 될 수 없다."
정의 불가능성 정리는 어떤 이론에서의 진리가 더 강한 이론에서 정의되는 것을 막지는 않는다. 예를 들어, 일차 술어 페아노 산술의 식(의 코드)으로 ''N''에서 참이 되는 것들의 집합은 2차 산술의 식으로 정의할 수 있다. 마찬가지로, 2차 산술 (혹은 그 이상의 고차 산술)의 표준 모델에서 참이 되는 식들의 집합은 일차 술어인 ZFC의 식으로 정의할 수 있다.
참조
[2]
arXiv
Satisfaction is not absolute
2013
[3]
서적
1998
[4]
간행물
Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit
Austrian Academy of Sciences
1930
[5]
서적
1991, 2001
[6]
문서
1961
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com