괴델 번호 부여

이 문서에는 일반 참조 목록이 포함되어 있지만 해당 인라인 인용이 충분하지 않습니다. 좀 더 정확한 인용문을 소개하여 이 기사를 개선할 수 있도록 도와주세요. (2021년 4월) (이 템플릿 메시지를 제거하는 방법과 시기에 대해 알아보세요.)

수학 논리학에서 괴델 번호는 어떤 형식 언어의 각 기호와 잘 형성된 공식에 고유한 자연수를 할당하는 함수로 괴델 번호라고 합니다. 이 개념은 쿠르트 괴델(Kurt Gödel)이 자신의 불완전성 정리를 증명하기 위해 개발했습니다(Gödel 1931).

괴델 번호 부여는 수학적 표기법의 각 기호에 숫자가 할당되고, 그 후 자연수 시퀀스가 일련의 기호를 나타낼 수 있는 인코딩으로 해석될 수 있습니다. 자연수의 이러한 수열은 다시 하나의 자연수로 표현될 수 있으며, 형식적인 산술 이론에서 자연수의 조작을 용이하게 합니다.

1931년 괴델의 논문이 발표된 이래로, "괴델 번호 부여" 또는 "괴델 코드"라는 용어는 수학적 대상에 대한 자연수의 보다 일반적인 할당을 나타내는 데 사용되었습니다.

간략개요

괴델은 계 내의 각 문장은 자연수(Gödel number)로 표현될 수 있다고 언급했습니다. 이것의 중요성은 문장의 참 또는 거짓과 같은 속성이 괴델 수가 특정 속성을 가지고 있는지 여부를 결정하는 것과 동일하다는 것입니다. 관련된 숫자는 실제로 매우 클 수 있지만, 이것은 장벽이 아닙니다. 중요한 것은 그러한 숫자를 만들 수 있다는 것입니다.

간단히 말해서, 그는 공식과 괴델 수를 기계적으로 앞뒤로 변환할 수 있는 방법으로 시스템에서 공식화될 수 있는 모든 공식 또는 문장이 고유한 수를 얻는 방법을 고안했습니다. 이렇게 할 수 있는 방법은 여러 가지가 있습니다. 간단한 예로는 아스키를 사용하여 컴퓨터에 영어를 일련의 숫자로 저장하는 방법이 있습니다. ASCII 코드의 범위는 0~127이므로 10진수 3자리로 패드한 다음 연결하면 됩니다.

• foxy라는 단어는 10211120121로 표현됩니다.
• 논리식은 1200611210320610620321061120으로 표현됩니다.

괴델의 부호화

괴델의 원본 부호화^[1]

								숫자 변수				속성 변수			...
기호.	0	s	¬	∨	∀	(	)	x1	x2	x3	...	P1	P2	P3	...
번호	1	3	5	7	9	11	13	17	19	23	...	289	361	529	...

괴델은 소인수분해에 기초한 시스템을 사용했습니다. 그는 먼저 자신이 다루고 있는 산술의 공식 언어로 각 기본 기호에 고유한 자연수를 할당했습니다.

괴델은 기호들의 시퀀스인 전체 공식을 인코딩하기 위해 다음과 같은 시스템을 사용했습니다. 양의 정수의$$ 수열$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle ...,}$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle(x_{1}, x_{2}, x_{3},$ ...,$x_{n})$이 주어졌을 때, 수열의 괴델 인코딩은 수열에서 해당 값으로 상승한 첫 번째 n개의 소수의 곱입니다.

${\displaystyle \mathrm {enc} (x_{1},x_{2},x_{3},\dots ,x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.}$

산술의 기본 정리에 따르면, 어떤 수(특히 이런 방식으로 얻은 수)도 소인수로 고유하게 인수분해될 수 있으므로 괴델 수에서 원래의 수열을 복구하는 것이 가능합니다(어떤 주어진 수의 n개의 부호화된 기호에 대해).

괴델은 특히 두 가지 수준에서 이 체계를 사용했습니다: 첫째, 공식을 나타내는 기호의 시퀀스를 인코딩하는 것과 둘째, 증명을 나타내는 공식의 시퀀스를 인코딩하는 것입니다. 이를 통해 그는 자연수에 대한 진술과 증명의 핵심 관찰인 자연수에 대한 정리의 증명 가능성에 대한 진술 사이의 일치를 보여줄 수 있었습니다. (Gödel 1931)

수열에 대한 괴델 번호를 구성하는 더 정교한(그리고 더 간결한) 방법이 있습니다.

예

Nagel과 Newman이 사용한 구체적인 괴델 번호에서 기호 "0"에 대한 괴델 번호는 6이고 기호 "="에 대한 괴델 번호는 5입니다. 따라서 이들의 체계에서 공식 "0 = 0"의 괴델 수는 2 × 3 × 5 = 243,000,000입니다.

고유성의 결여

무한히 많은 다른 괴델 수가 가능합니다. 예를 들어, K개의 기본 기호가 있다고 가정할 때, 이 기호 집합(예를 들어, 가역 함수 h를 통해)을 쌍방향 기저-K 수계의 자릿수 집합에 가역적으로 매핑하여 대안적인 괴델 번호를 구성할 수 있습니다. n개 기호의 ${\displaystyle {문자열}_{}}$로 구성된 공식 ${\displaystyle {s1s2s3\mathrm{}}_{}}$…${\$이 숫자에 매핑됩니다$$.

${\displaystyle h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.}$

즉, k개의 기본 기호 집합을 고정된 순서로 배치하여 $i{\displaystyle }$ ${\displaystyle$ i$}$번째$$ 기호가 $고유$하게 i ${\displaystyle$ i$}$번째$$ 숫자와 일치하도록 함으로써 각 공식은 자신의 괴델 수와 같은 역할을 할 수 있습니다.

예를 들어, 여기에 설명된 번호는 K=1000입니다.

형식적 연산에 대한 적용

재귀

괴델 번호를 사용하여 값 과정 재귀에 의해 정의된 함수가 실제로 원시 재귀 함수라는 것을 보여줄 수 있습니다.

숫자로 문 및 증명 표현

형식 이론에 대한 괴델 번호가 설정되면 이론의 각 추론 규칙은 자연수에 대한 함수로 표현될 수 있습니다. 만약 f가 괴델 매핑이고 r이 추론 규칙이라면, 공식 C가 추론 규칙을 통해 공식 A와 B에서 유도되는 것과 같은 자연수의 산술 함수 g가_r 있어야 합니다.

${\displaystyle A,B\vdash _{r}C,}$

그리고나서

${\displaystyle g_{r}(f(A),f(B))=f(C).}$

이것은 괴델이 사용한 번호와 암호화된 공식이 괴델 번호에서 산술적으로 복구될 수 있는 다른 번호에 대해서도 마찬가지입니다.

따라서 페아노 산술과 같은 형식적 이론에서는 수와 그 산술적 관계에 대해 서로 진술할 수 있으며, 괴델 번호를 사용하여 이론 자체에 대해 간접적으로 진술할 수 있습니다. 이 기술을 통해 괴델은 공식 시스템의 일관성과 완전성에 대한 결과를 증명할 수 있었습니다.

일반화

계산 가능성 이론에서 "Gödel Numbering"이라는 용어는 위에서 설명한 것보다 더 일반적인 설정에서 사용됩니다. 다음을 가리킨다.

1. 알고리즘에 의해 숫자가 조작될 수 있는 방식으로 자연수에 대한 형식 언어의 요소의 할당은 형식 언어의 요소를 조작하는 것을 시뮬레이션합니다.^{[citation needed]}
2. 더 일반적으로, 수학적 객체의 알고리즘 조작을 허용하기 위해, 셀 수 있는 그룹과 같은 셀 수 있는 수학적 객체의 요소들을 자연수에 할당하는 것.^{[citation needed]}

또한 할당된 "숫자"가 실제로 문자열일 때 괴델 번호 부여라는 용어가 사용되기도 하는데, 숫자가 아닌 문자열을 조작하는 튜링 기계와 같은 계산 모델을 고려할 때 필요합니다.^{[citation needed]}

괴델 집합

괴델 집합은 때때로 집합론에서 공식을 인코딩하는 데 사용되며, 인코딩을 수행하기 위해 숫자 대신 집합을 사용한다는 점을 제외하고는 괴델 수와 유사합니다. 유전적으로 유한한 집합을 사용하여 공식을 인코딩하는 단순한 경우 이는 본질적으로 괴델 수를 사용하는 것과 동일하지만 공식의 트리 구조는 집합의 트리 구조에 의해 모델링될 수 있기 때문에 정의하기가 다소 쉽습니다. 괴델 집합은 또한 무한 언어로 공식을 인코딩하는 데 사용될 수 있습니다.

참고 항목

• 교회 부호화
• 설명번호
• 수열에 대한 괴델 번호 부여
• 괴델의 불완전성 정리
• 차이틴의 불완전성 정리

참고문헌

• Gödel, Kurt (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (PDF), Monatshefte für Mathematik und Physik, 38: 173–198, doi:10.1007/BF01700692, S2CID 197663120, archived from the original (PDF) on 2018-04-11, retrieved 2013-12-07.
• 어니스트 네이글과 제임스 R의 괴델의 증명. 뉴먼(1959). 이 책은 증명에 대한 좋은 소개와 요약을 제공하며, 괴델의 번호 부여에 초점을 맞춘 큰 부분이 있습니다.

더보기

• 괴델, 에셔, 바흐: 더글러스 호프스태터의 영원한 황금 땋은 머리. 이 책은 대안적인 괴델 번호를 정의하고 사용합니다.
• 나는 더글라스 호프스태터의 이상한 고리입니다. 이것은 괴델의 번호 부여의 역사를 포함하는 호프스태터의 새로운 책입니다.
• 제이슨 헤만과 에릭 홀크의 튜링 타피트를 시각화합니다. Gödel 번호를 사용하여 프로그램을 인코딩합니다.