굿스타인의 정리

3. 굿스타인 수열

굿스타인 수열은 자연수에서 시작하여, 유전적 밑-n 표기법을 기반으로 다음 항을 만들어 가는 수열이다.

굿스타인 수열 $G\_m$의 첫 번째 항은 ''m'' 자신이다. 두 번째 항 $G\_m(2)$를 얻기 위해서는, ''m''을 유전적 2진법 표기법으로 나타낸 후, 모든 2를 3으로 바꾸고 1을 뺀다.

일반적으로, $G\_m(n)$이 주어졌을 때, $G\_m(n+1)$은 다음과 같이 계산한다.

1. $G\_m(n)$을 유전적 (n+1)진법으로 표현한다.

2. 표현식에서 모든 (n+1)을 (n+2)로 바꾼다.

3. 결과에서 1을 뺀다.

이 과정을 결과가 0이 될 때까지 반복한다.

예를 들어, $G\_3$은 다음과 같이 전개된다.

$G\_4$는 더 복잡하게 전개되지만, 결국에는 0으로 수렴한다.

$G\_4$의 진행 과정은 다음과 같다.

$G\_\{19\}$는 초반에 매우 급격하게 증가한다.

3. 1. 유전적 밑-n 표기법

3. 2. 굿스타인 수열의 정의

• $G\_m\; (n)$의 유전적 진법 표현을 취한다.
• 각 진법의 발생을 로 대체한다.
• 1을 뺀다. (다음 항은 이전 항과 지수 ''n'' 모두에 의존한다.)
• 결과가 0이 될 때까지 계속하고, 이 시점에서 수열은 종료된다.

G(3)의 진행 과정은 다음과 같다.

나중 굿스타인 수열은 매우 많은 단계 동안 증가한다. 예를 들어, $G\_4$는 다음과 같이 시작한다.

$G\_4$의 요소는 잠시 동안 계속 증가하지만, $3\; \backslash cdot\; 2^\{402\backslash ,653\backslash ,209\}$진법에서 최대값 $3\; \backslash cdot\; 2^\{402\backslash ,653\backslash ,210\}\; -\; 1$에 도달하고, 다음 $3\; \backslash cdot\; 2^\{402\backslash ,653\backslash ,209\}$ 단계 동안 그 상태를 유지한 다음 감소하기 시작한다.

G(4)는 다음과 같이 진행된다.

G(4)의 항은 잠시 증가를 계속하지만, 밑이 3 · 2^402653209가 된 시점에서 최대값 3 · 2^402653210 − 1에 도달하며, 그대로 3 · 2^402653209항 동안 같은 값을 유지하다가, 최초이자 마지막 하강을 시작한다.

$G\_\{19\}$는 훨씬 더 빠르게 증가하며 다음과 같이 시작한다.

4. 굿스타인 정리의 증명

굿스타인 정리는 페아노 공리계 밖의 기법, 즉 순서수를 이용하여 증명할 수 있다. 굿스타인 수열에 대응하는 감소하는 순서수열을 구성하고, 이 순서수열이 유한 번의 연산 후 0으로 수렴함을 보인다.

이 정리의 증명에는 다음과 같은 보조정리가 필요하다.^[1]

• (보조정리) 위와 같은 조건에서, 임의의 순서수 a에 대하여 .

• $h\_n\; =\; \backslash omega^\{b\_k\}a\_k\; +\; ...\; +\; \backslash omega^\{b\_0\}a\_0$

• $g\_n\; >\; 0$ 이면 $h\_n\; >\; 0$ 이고 $h\_n\; >\; h\_\{n+1\}$이다.

• $g\_\{n+1\}\; =\; (n+1)^\{b\_k\}a\_k\; +\; ...\; +\; (n+1)^\{b\_0\}(a\_0\; -\; 1)\; +\; (n+1)^\{b\_0\; -\; 1\}n\; +\; ...\; +\; (n+1)n\; +\; n$

• $h\_\{n+1\}\; =\; \backslash omega^\{b\_k\}a\_k\; +\; ...\; +\; \backslash omega^\{b\_0\}(a\_0\; -\; 1)\; +\; \backslash omega^\{b\_0\; -\; 1\}n\; +\; ...\; +\; n$

4. 1. 증명 과정

5. 패리스의 정리 (Kirby-Paris 정리)

패리스의 정리는 굿스타인 정리와 마찬가지로 자연수 수열에 관한 정리이지만, 페아노 공리계 내에서는 증명할 수 없다. 로리 커비와 패리스는 이 정리가 페아노 산술의 무모순성과 관련이 있음을 증명하였다.^[1]

5. 1. 공식화

• 초항이 자연수인 굿스타인 수열은 0으로 끝난다.

5. 2. 증명 불가능성

• 패리스의 정리가 성립하면 페아노 산술이 모형을 갖는다.

6. 확장된 굿스타인 정리

밑수 변경 연산에서 밑을 ''b'' + 1 대신 ''b'' + 2로 바꾸도록 굿스타인 수열의 정의를 변경해도 굿스타인 정리는 여전히 성립한다.

더 일반적으로, ''b''₁, ''b''₂, ''b''₃, ...를 ''b''₁ ≥ 2인 정수의 비감소 수열이라고 하자. 그러면 ''m''의 확장된 굿스타인 수열의 (''n'' + 1)-번째 항 ''G''(''m'')(''n'' + 1)은 다음과 같이 정의된다.

• ''G''(''m'')(''n'')의 유전적 밑수 ''b_n'' 표현을 취한다.
• 밑수 ''b_n''의 각 발생을 ''b''_''n''+1로 바꾼다.
• 1을 뺀다.

7. 수열의 길이와 굿스타인 함수

굿스타인 함수 $\backslash mathcal\{G\}:\; \backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}$는 $\backslash mathcal\{G\}(n)$이 ''n''으로 시작하는 굿스타인 수열의 길이로 정의된다. 모든 굿스타인 수열이 종료되므로 이는 전체 함수이다. $\backslash mathcal\{G\}$의 매우 높은 증가율은 하디 계층의 함수 $H\_\backslash alpha$ 및 뢰브와 와이너의 빠르게 증가하는 계층의 함수 $f\_\backslash alpha$와 같이 다양한 표준 서수-색인 함수 계층과 관련하여 보정될 수 있다.

• 커비와 파리(1982)는 $\backslash mathcal\{G\}$가 $H\_\{\backslash epsilon\_0\}$와 거의 같은 성장률을 가짐을 증명했다(이는 $f\_\{\backslash epsilon\_0\}$와도 같다). 보다 정확하게는, $\backslash mathcal\{G\}$는 모든 에 대해 $H\_\backslash alpha$를 지배하고, $H\_\{\backslash epsilon\_0\}$는 $\backslash mathcal\{G\}\backslash ,\backslash !$를 지배한다.

• 치촌(1983)은 $\backslash mathcal\{G\}(n)\; =\; H\_\{R\_2^\backslash omega(n+1)\}(1)\; -\; 1$임을 보였다. 여기서 $R\_2^\backslash omega(n)$은 ''n''을 상속적 2진법 표기법으로 넣은 다음 모든 2를 ω로 대체한 결과이다(굿스타인 정리 증명에서 수행된 바와 같음).

• 카이세도(2007)는 $n\; =\; 2^\{m\_1\}\; +\; 2^\{m\_2\}\; +\; \backslash cdots\; +\; 2^\{m\_k\}$이고 $m\_1\; >\; m\_2\; >\; \backslash cdots\; >\; m\_k$일 경우, $\backslash mathcal\{G\}(n)\; =\; f\_\{R\_2^\backslash omega(m\_1)\}(f\_\{R\_2^\backslash omega(m\_2)\}(\backslash cdots(f\_\{R\_2^\backslash omega(m\_k)\}(3))\backslash cdots))\; -\; 2$임을 보였다.

(아커만 함수 및 그레이엄 수 경계에 대한 내용은 빠르게 증가하는 계층#빠르게 증가하는 계층의 함수 참조.)

8. 계산 가능 함수에의 응용

어떤 수의 굿스타인 수열은 튜링 기계로 효과적으로 열거할 수 있다. 따라서 ''n''을 ''n''의 굿스타인 수열이 종료되는 데 필요한 단계의 수에 매핑하는 함수는 특정 튜링 기계로 계산 가능하다.^[1] 이 기계는 단순히 ''n''의 굿스타인 수열을 열거하고, 수열이 ''0''에 도달하면 수열의 길이를 반환한다.^[1] 모든 굿스타인 수열은 결국 종료되므로 이 함수는 전역 함수이다.^[1] 그러나 페아노 산술은 모든 굿스타인 수열이 종료된다는 것을 증명하지 않기 때문에, 페아노 산술은 이 튜링 기계가 전역 함수를 계산한다는 것을 증명하지 않는다.^[1]