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

Tarski's undefinability theorem

1933년 알프레드 타르스키에 의해 명기되고 증명된 타르스키의 정의 불가능한 정리는 수학논리와 수학의 기초, 형식적인 의미론에서 중요한 제한적 결과물이다.비공식적으로, 그 정리는 산술적 진리를 산술적으로 정의할 수 없다고 명시한다.

이 정리는 시스템 내에서 표준 모델의 진리를 정의할 수 없다는 것을 보여줌으로써 충분히 강력한 공식 시스템에 더 일반적으로 적용된다.

역사

1931년, 커트 괴델은 불완전성 이론들을 발표했는데, 이 이론은 1차 산술 내에서 형식 논리의 구문을 표현하는 방법을 보여줌으로써 부분적으로 증명되었다.산술 형식 언어의 각 표현에는 구별되는 숫자가 할당된다.이 절차는 괴델 번호 매기기, 부호화, 그리고 더 일반적으로 산술화라고 알려져 있다.특히 다양한 표현 집합은 숫자 집합으로 코딩된다.다양한 구문적 특성(예: 공식, 문장 등)에 대해 이러한 집합은 계산 가능하다.더욱이 계산 가능한 숫자의 집합은 일부 산술 공식으로 정의할 수 있다.예를 들어, 산술 언어에는 산술 문장의 코드 집합을 정의하는 공식과 증명 가능한 산술 문장의 공식들이 있다.

정의하기 어려운 정리는 이 인코딩이 진리와 같은 의미 개념에 대해 이루어질 수 없음을 보여준다.그것은 충분히 풍부한 해석 언어가 그 자신의 의미론을 대표할 수 없다는 것을 보여준다.한 가지 중요한 것은 어떤 목적어 언어의 의미론을 표현할 수 있는 모든 금속구조는 목적어 언어의 의미보다 더 뛰어난 표현력을 가져야 한다는 것이다.금속구어에는 원시 개념, 공리, 목적어 언어와 무관한 규칙이 포함되어 있어 목적어에서는 증명할 수 없는 금속구어에는 이론이 있다.

정의하기 어려운 정리는 관례적으로 알프레드 타르스키에게 귀속된다.괴델은 또한 1931년, 그리고 1933년 타르스키의 작품이 출간되기 훨씬 전에 그의 불완전성 정리를 증명하면서 1930년에 정의 불가능한 정리를 발견했다(Murawski 1998).괴델은 자신의 독자적 정의 불가능 발견과 관련된 어떤 것도 발표하지 않았지만, 존 폰 노이만에게 보낸 1931년 편지에서 그것을 묘사했다.타르스키는 1929년부터 1931년 사이에 1933년 자신의 모노그래프인 "연역과학의 언어에서 진리의 개념"의 거의 모든 결과를 얻었고, 폴란드 청중들에게 이들에 대해 말했다.그러나 논문에서 강조했듯이 정의롭지 못한 정리는 그가 일찍이 얻지 못한 유일한 결과였다.1933년 모노그래프의 정의하기 어려운 정리(Twierdzenie I)에 대한 각주에 따르면, 1931년 원고를 인쇄소에 보낸 후에야 비로소 증명서의 정리 및 스케치가 모노그래프에 추가되었다.타르스키는 그곳에서 1931년 3월 21일 바르샤바 과학 아카데미에 자신의 모노그래프 내용을 발표했을 때, 부분적으로 자신의 조사와 부분적으로 불완전성에 대한 괴델의 짧은 보고에 근거한 약간의 추측만을 표현했다고 보고한다.d Widerspruchsfreiheit" , Akademie der Wissenschaften, 1930년 Wien.

성명서

우리는 먼저 타르스키의 정리를 간략하게 설명한 후, 타르스키가 1933년에 증명한 정리를 다음 절에 기술하고 증명할 것이다.

L을 1차 산술의 언어가 되게 하라.이것은 1차적인 페아노 공리에 의해 공리화된 그들의 덧셈과 곱셈을 포함한 자연수의 이론이다.이것은 "1차 순서" 이론이다: 정량자는 자연수에 걸쳐 확장되지만 자연수의 집합이나 함수에 대해서는 확장되지 않는다.이 이론은 지수, 요인 또는 피보나치 수열과 같은 반복적으로 정의된 정수 함수를 설명할 수 있을 만큼 충분히 강하다.

Let N을 L의 표준 구조로 하자, 즉 N은 자연수의 일반적인 집합과 그 덧셈과 곱셈으로 구성된다.L의 각 문장은 N으로 해석될 수 있으며, 그 다음 참 또는 거짓이 될 수 있다.따라서 (L, N)은 "산술의 해석된 1차 언어"이다.

L의 각 공식 φ은 괴델 번호 g(φ)를 가지고 있다.이것은 φ의 "encodes"인 자연수다.그런 식으로 L언어는 숫자만이 아니라 L의 공식에 대해 말할 수 있다.Let T는 N에서 L-ssents의 집합을 나타내고, T*는 Gödel의 문장 수를 나타낸다.다음의 정리는 질문에 대답한다: T*는 1차 산술의 공식으로 정의될 수 있는가?

타르스키의 정의 불가능한 정리:T*를 정의하는 L-formula True(n)는 없다.즉, A가 N에 보유하고 있는 모든 L-sentence A, True(g(A) £와 같은 L-formula True(n)는 없다.

비공식적으로, 정리는 1차 산술 문장의 진리의 개념은 1차 산술에서 공식으로 정의할 수 없다고 말한다.이는 '자기표현'의 범위에 대한 큰 한계를 내포하고 있다.확장자가 T*인 True(n) 공식은 정의할 수 있지만, 표현력이 L을 뛰어넘는 금속구조에 그려야 가능하다.예를 들어 1차 산술의 진리 술어는 2차 산술에서 정의할 수 있다.그러나 이 공식은 원래 언어 L에서 공식에 대한 진실 술어를 정의할 수 있을 뿐이다.금속구조의 진리를 정의하기 위해서는 아직 더 높은 변형이 필요할 것이다.

정리를 증명하기 위해, 우리는 모순에 의해 진행하며, 만약 n이 L에 있는 문장의 괴델 번호인 경우에만 N에 있는 자연수 n에 대해 참인 L-포뮬라 True(n)가 존재한다고 가정한다.We could then use True(n) to define a new L-formula S(m) which is true for the natural number m if and only if m is the Gödel number of a formula φ(x) (with a free variable x) such that φ(m) is false when interpreted in N (i.e. the formula φ(x), when applied to its own Gödel number, yields a false statement).이제 우리가 S(m) 공식의 괴델 숫자 g를 고려하고, 문장 S(g)가 N에서 사실인지 물어보면 모순을 얻는다.(이것은 대각선 주장이라고 알려져 있다.)

이 정리는 타르스키(1933년) 이후 몇 년 후에 증명된 산술적 위계질서에 관한 포스트의 정리의 산술적 정리의 귀결이다.포스트의 정리로부터 타르스키의 정리를 의미론적으로 증명하는 것은 다음과 같이 환원 ad lossenum에 의해 얻어진다.산술적으로 T*를 정의할 수 있다고 가정하면 산술적 계층 구조에서 수준의 공식으로 T*를 정의할 수 있는 자연수 n이 있다.단, T*는 모든 k에 대해 k 0 {\ \_{k}^{ -hard이다.따라서 산술적 계층 구조는 수준 n에서 붕괴되어 포스트의 정리와는 모순된다.

일반형식

타르스키는 전적으로 구문론적인 방법을 사용하여 위에서 말한 것보다 더 강력한 정리를 증명했다.결과 정리는 부정과 대각선 보조정리기가 보유하고 있는 자기 참조를 위한 충분한 능력을 갖춘 모든 공식 언어에 적용된다.1차 산술은 이러한 전제조건을 만족시키지만, 그 정리는 훨씬 더 일반적인 형식 시스템에 적용된다.

타르스키의 정의 불가능한 정리(일반 형식):(L,N)은 부정을 포함하고 대각선 보조정리기를 만족시키는 괴델 번호 매기기 g(iii)를 가진 해석된 공식 언어로서, 즉 모든 L-forma B(x) (자유 변수 x)에 대해 A(b)(A)가 N에서 보유하는 문장이 있다.그리고 다음 속성을 가진 L-formula True(n)는 없다: 모든 L-sentence A에 대해 True(g(A) £는 N에서 사실이다.

타르스키가 이 형식에서 정의하지 못한 정리에 대한 증거는 다시 환원 ad urlousum에 의해 증명된다.위와 같은 L-포뮬라 True(n)가 존재한다고 가정합시다. 즉, A가 산술의 문장이라면 True(g(A))는 N을 유지하고 A가 N을 유지하는 경우에만 N을 유지한다고 가정합시다.따라서 모든 A에 대해 True(g(A) £A라는 공식은 N에 있다. 그러나 대각선 보조정리기는 S파운드의 True(g(S)가 N에 보유하는 것과 같은 "liar" 공식 S를 줌으로써 이러한 동등성에 대한 백례를 산출한다.이것은 모순이다.QED.

토론

위에 제시된 증명의 형식 기계는 대각선 보조정리기가 요구하는 대각선화를 제외하고 완전히 초보적이다.대각선 보조정리법도 마찬가지로 놀랍도록 간단하다. 예를 들어, 그것은 어떤 방법으로도 재귀적 기능을 발동시키지 않는다.증명서는 모든 L-포뮬라에는 괴델 번호가 있다고 가정하지만, 코딩 방법의 구체적인 내용은 필요하지 않다.따라서 타르스키의 정리는 1차 산술의 변태적 특성에 대한 괴델의 더 유명한 이론보다 동기 부여와 증명하기가 훨씬 쉽다.

스물리안(1991년, 2001년)은 타르스키의 정의 불가능한 정리가 괴델의 불완전성 이론에서 얻은 많은 관심을 받을 만하다고 강력하게 주장해 왔다.후자의 이론들이 모든 수학에 대해 말할 것이 많고 더 논쟁적으로 철학적 이슈의 범위(예: 루카스 1961)에 대해 말할 것이 많다는 것은 명확하지 않다.한편 타르스키의 정리는 수학에 관한 것이 아니라 어떤 형식적인 언어의 내재된 한계에 관한 것으로서 진정한 관심을 가질 수 있을 만큼 충분히 표현된다.그러한 언어는 대각선 보조정리기가 적용되기에 충분한 자체 참조가 필요하다.타르스키의 정리에 대한 보다 폭넓은 철학적 수입은 더욱 두드러지게 드러난다.

해석된 언어는 언어에 특정된 모든 의미 개념을 정의하는 술어와 함수 기호를 포함하는 언어의 경우 정확히 강하게 의미론적으로 자기표현적이다.따라서 요구되는 기능에는 수식 A를 진리 값 A에 매핑하는 "대안 평가 함수"와 t를 나타내는 객체에 매핑하는 "대안 변성 함수"가 포함된다.그러면 타르스키의 정리는 다음과 같이 일반화된다.충분히 강력한 언어는 강렬하게 자기표현적이지 않다.

정의하기 어려운 정리는 한 이론의 진리가 더 강한 이론으로 정의되는 것을 막지 못한다.예를 들어, N에서 참인 1차 페아노 산술의 공식 집합은 2차 산술의 공식으로 정의할 수 있다.마찬가지로, 2차 산술(또는 n차 산술) 표준 모형의 실제 공식 집합은 1차 산술 ZFC의 공식으로 정의할 수 있다.

참고 항목

참조

  • J. L. 벨과 M.1977년 마하버.수학적 논리학의 과정.노스홀랜드.
  • G. Boolos, J. Burgess, 2002년 R. Jeffrey.계산성과 논리학, 4번째 에디션.케임브리지 대학교 출판부
  • J. R. 루카스, 1961년"마인드, 머신스, 괴델"철학 36: 112–27.
  • 1998년 R. 무라우스키.진실의 정의가 없다. 우선 순위의 문제: 타르스키 vs. 괴델 논리학 19, 153–160
  • R. Smulyan, 1991.고델의 불완전성 이론.옥스퍼드 유니브누르다
  • R. Smulyan, 2001."괴델의 불완전성 이론"L. 고블, 에드, 블랙웰의 철학 논리 가이드, 블랙웰, 72–89.
  • A. 타르스키, 1933.Pojęcie Prawdy 와 Jjzykach Nauk Dedukcyjnych.나크와뎀 토와지스트와 나우코베고 워즈쇼스키에고.
  • A. Tarski (1936). "Der Wahrheitsbegriff in den formalisierten Sprachen" (PDF). Studia Philosophica. 1: 261–405. Archived from the original (PDF) on 9 January 2014. Retrieved 26 June 2013.