굿스타인의 정리

수학적 논리학에서 굿스타인의 정리는 자연수에 관한 진술로, 1944년 르우벤 굿스타인(Ruben Goodstein)에 의해 증명된 것으로서, 모든 굿스타인의 수열은 결국 0으로 끝난다는 것을. 커비(Kirby)와 파리는^[1] 페아노 산술에서는 증명할 수 없다는 것을 보여주었다(그러나 2차 산술과 같은 더 강력한 시스템에서는 증명할 수 있다).이는 괴델의 불완전성 정리와 게르하르트 겐첸의 1943년 페아노 산술에서 ε-유도성의₀ 비도덕성을 직접 입증한 사례에 이어 페아노 산술에서 증명할 수 없는 참된 진술의 세 번째 예였다.파리-해링턴 정리가 또 다른 예를 들었다.

로런스 커비와 제프 파리는 굿스타인 시퀀스와 유사한 행동을 가진 그래프 이데아틱 하이드라 게임을 도입했는데, '히드라'(신화학적 다두하이드라의 이름을 딴 레르나)는 뿌리가 있는 나무로, 그 '헤드'(나무의 가지) 중 하나를 잘라내는 것으로 동작이 이루어지며, 히드라는 한정된 숫자의 새로운 수를 키워 반응한다.일정한 규칙에 따르다커비와 파리는 헤라클레스가 머리를 자르는데 사용하는 전략과는 상관없이 히드라가 결국 살해될 것이라는 것을 증명했지만, 이것은 매우 오랜 시간이 걸릴지도 모른다.굿스타인 시퀀스처럼 커비와 파리는 페아노 산술만으로는 증명할 수 없다는 것을 보여주었다.^[1]

유전기준-n 표기법

Goodstein 시퀀스는 "계속적 base-n 표기법"이라는 개념으로 정의된다.이 표기법은 통상적인 base-n 위치 표기법과 매우 유사하지만, 통상적인 표기법은 굿스타인의 정리 목적으로는 충분하지 않다.

n이 1보다 큰 자연수인 일반 base-n 표기법에서 임의의 자연수 m은 n:의 힘의 배수의 합으로 표기된다.

${\displaystyle m=a_{k}n^{k-1}+a_{k-1}n^{k-1}+\cdots +a_{0},}$

여기서 각 계수 a는_i 0 ≤ a_i < n을 만족하고, ≠ 0을_k 만족한다.예를 들어, 베이스 2에서는

${\displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}}$

따라서 35의 base-2는 100011로 2⁵ + 2 + 1을 의미한다. 마찬가지로 base-3로 표시된 100은 10201이다.

${\displaystyle 100=81+18+1=3^{4}+2\cdot 3^{2}+3^{0}}}$

지수 자체는 base-n 표기법으로 작성되지 않는다는 점에 유의하십시오.예를 들어 위의 표현에는 2와⁵ 3이⁴ 있고, 5 > 2, 4 > 3이 있다.

base-n 표현을 세습 base-n 표기법으로 변환하려면 먼저 모든 지수를 base-n 표기법으로 다시 쓰십시오.그런 다음 지수 내부에 있는 모든 지수를 다시 쓰고, 표현식에 나타나는 모든 숫자(기준 자체를 제외)가 base-n 표기법으로 변환될 때까지 이러한 방식으로 계속한다.

예를 들어 일반 base-2 표기법에서 35는 2⁵ + 2 + 1인 반면, 세습 base-2 표기법에서는 다음과 같이 표기한다.

${\displaystyle 35=2^{2^{1}^{1}+1}+2^{1},}$

5 = 2² + 1이라는 사실을 이용하여 유사하게 유전 베이스 3 표기법에서 100은

${\displaystyle 100=3^{3^{1}+1}+1+2\cdot 3^{2}+1.}$

굿스타인 시퀀스

숫자 m의 Goodstein 시퀀스 G(m)는 자연수의 시퀀스다.시퀀스 G(m)의 첫 번째 원소는 m 그 자체다.두 번째 G(m)(2)를 얻으려면 m을 유전 베이스-2 표기법으로 쓰고, 2s를 모두 3s로 변경한 다음 결과에서 1을 뺀다.일반적으로 goodstein sequence of m의 (n + 1)-초기 용어 G(m)(n + 1)는 다음과 같다.

• G(m)(n)의 세습 베이스 n + 1 표현을 취한다.
• base-n + 1의 각 발생을 n + 2로 교체한다.
• 1을 빼라. (다음 항은 전기와 지수 n에 모두 의존한다.)
• 결과가 0이 될 때까지 계속하며, 이때 시퀀스가 종료된다.

초기 Goodstein 시퀀스는 빠르게 종료된다.예를 들어, G(3)는 6번째 단계에서 종료된다.

베이스	유전 표기법	가치	메모들
2	${\displaystyle 2^{1}+1}$	3	3을 base-2 표기법으로 작성
3	${\displaystyle 3^{1}+1-1=3^{1}:{1}$	3	2를 3으로 바꾼 다음 1을 빼십시오.
4	${\displaystyle 4^{1}-1=3}$	3	3을 4로 바꾼 다음 1을 뺀다.이제 4초도 남지 않았다.
5	$3-1=2}$	2	4초 남아서 5초.1만 빼면 돼.
6	${\displaystyle$	1	5초 남아서 6초.1만 빼면 돼.
7	$1-1=0}$	0	6초 남아서 7초.1만 빼면 돼.

나중에 굿스타인 시퀀스는 매우 많은 수의 스텝에 대해 증가한다.예를 들어 G(4) OEIS: A056193은 다음과 같이 시작한다.

베이스	유전 표기법	가치
2	${\displaystyle 2^{2^{1}}$	4
3	${\displaystyle 3^{3^{1}-1=2\cdot 3^{2}+2\cdot 3+2}$	26
4	${\displaystyle 2\cdot 4^{2}+2\cdot 4+1}$	41
5	${\displaystyle 2\cdot 5^{2}+2\cdot 5}$	60
6	${\displaystyle 2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5}$	83
7	${\displaystyle 2\cdot 7^{2}+7+4}$	109
$\displaystyle \vdots }$	$\displaystyle \vdots }$	$\displaystyle \vdots }$
11	${\displaystyle 2\cdot 11^{2}+11}$	253
12	${\displaystyle 2\cdot 12^{2}+12-1=2\cdot 12^{2}+11}$	299
$\displaystyle \vdots }$	$\displaystyle \vdots }$	$\displaystyle \vdots }$
24	${\displaystyle 2\cdot 24^{2}-1=24^{2}+23\cdot 24+23}$	1151
$\displaystyle \vdots }$	$\displaystyle \vdots }$	$\displaystyle \vdots }$
${\displaystyle B=3\cdot 2^{402\,653\,209}-1}$	$B^{1}{\displaystyle 2\cdot B^{1}$	${\displaystyle 3\cdot 2^{402\,653\,property}-2}$
${\displaystyle B=3\cdot 2^{402\,653\,209}}$	${\displaystyle 2\cdot B^{1}-1=B^{1}+(B-1)}$	${\displaystyle 3\cdot 2^{402\,653\,property}-1}$
$\displaystyle \vdots }$	$\displaystyle \vdots }$	$\displaystyle \vdots }$

Elements of G(4) continue to increase for a while, but at base ${\displaystyle 3\cdot 2^{402\,653\,209}}$, they reach the maximum of ${\displaystyle 3\cdot 2^{402\,653\,210}-1}$, stay there for the next ${\displaystyle 3\cdot 2^{402\,653\,209}}$ steps, and그리고 나서 그들의 하강을 시작한다.

The value 0 is reached at base ${\displaystyle 3\cdot 2^{402\,653\,211}-1}$. (Curiously, this is a Woodall number: ${\displaystyle 3\cdot 2^{402\,653\,211}-1=402\,653\,184\cdot 2^{402\,653\,184}-1}$. This is also the case with all other fin4보다 큰 시작 값에 대한 기준)^{[citation needed]}

그러나 G(4)조차 굿스타인 염기서열의 원소가 얼마나 빨리 증가할 수 있는지에 대한 좋은 생각을 주지 못한다.G(19)는 훨씬 더 빠르게 증가하며 다음과 같이 시작한다.

유전 표기법	가치
${\displaystyle 2^{2^{2}}+2+1}$	19
${\displaystyle 3^{3^{3}+3}$	7625597484990
${\displaystyle 4^{4^{4}}+3}$	${\displaystyle \ 약 1.3\cHB 10^{11}}$
${\displaystyle 5^{5^{5}+2}$	$1.8원정도의 \displaystyle \cHB 10^{2\,cHB}}$
${\displaystyle 6^{6^{6}}+1}$	${\displaystyle \ 약 2.6\cHB 10^{36\,305}}$
${\displaystyle 7^{7^{7}}$	$약 3원.8\cHB 10^{695\,974}}$
${\displaystyle 8^{8^{8}-1=7\cdot 8^{7}+7}{7}+7\cdot 8^{6}+7}{5}\cdot 8^{4}+7}+7}{3}\cdot 8^{2}+7}\cdot 8+7\cdot 8+7}}}}}}}}}\cdot 8+7}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$ ${\displaystyle {}+7\cdot 8^{7}{7}+7\cdot 8^{6}{5}+7}+7\cdot 8^{4}}+7}}\cdot 8^{3}+7}+7\cdot 8+7+7+7}+7}\cdots }}\cdots}}}}}}}}}}}}cdots}}}}}}}}cdots}}}}}}}}}}cdotsdotsdots$ ${\displaystyle {}+7\cdot 8^{8+2}+7\cdot 8^{8+1}+7\cdot 8^{8}}}$ ${\displaystyle {}+7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}}}$ ${\displaystyle {}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7}$	${\displaystyle \ 약 6\cHB 10^{15\,335}$
${\displaystyle 7\cdot 9^{7}+7}+7\cdot 9^{6}+7}{5}+7\cdot 9^{4}+7}\cdot 9^{3}+7}\cdot 9^{2}+7}\cdot 9+7}}\cdot 9+7\cdot 9+7}}}}}}}}}}}\cdot 9+7}}}}}}}}}\cdot 9+7}}}}}}}}}}$ ${\displaystyle {}+7\cdot 9^{7}{7}+7\cdot 9^{6}}{5}+7\cdot 9^{4}+7}\cdot 9^{3}+7}+7+7\cdot 9+7+7}\cdot 9+6}\cdots }}}}}}}}}}}}}}}}}cdots}}}}}}}}}cdots}}}}cdots}}}cdots}}}}}$ ${\displaystyle {}+7\cdot 9^{9+2}+7\cdot 9^{9+1}+7\cdot 9^{9}}}$ ${\displaystyle {}+7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}}}$ ${\displaystyle {}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6}$	$약 5.6\cHB 10^{35\,942\,384}}}$
$\displaystyle \vdots }$	$\displaystyle \vdots }$

이러한 급속한 성장에도 불구하고 굿스타인의 정리에는 모든 굿스타인의 순서는 결국 출발값이 어떻게 되든 0으로 종료된다고 명시되어 있다.

굿스타인의 정리 증명

굿스타인의 정리는 다음과 같이 증명할 수 있다(페아노 산술 외 기법을 사용, 이하 참조). 굿스타인의 수열 G(m)를 주어 엄격히 감소하고 종료되는 서수형 숫자의 평행 순서 P(m)를 구성한다.그러면 G(m)도 종료해야 하며, 0이 되어야 종료할 수 있다.이 증거에 대한 일반적인 오해는 G(m)가 P(m)에 의해 지배되기 때문에 0으로 간다고 믿는 것이다.사실 P(m)가 G(m)를 지배한다는 사실은 전혀 작용하지 않는다.중요한 점은: P(m)(k)가 존재하는 경우에만(병렬) G(m)(k)가 존재한다는 것이다.그 후 P(m)가 종료되면 G(m)도 종료된다.그리고 G(m)는 0에 해당하는 경우에만 종료할 수 있다.

u의 유전적 base k 표현을 계산한 다음 base k의 각 발생을 첫 번째 무한 서수 Ω으로 대체하는$$ $f{\displaystyle }$= f (${\displaystyle u}$ , ${\displaystyle k}$) ${\displaystyle f=f(u,k)}$ 함수를 정의한다.For example, ${\displaystyle f(100,3)=f(3^{3^{1}+1}+2\cdot 3^{2}+1,3)=\omega ^{\omega ^{1}+1}+2\omega ^{2}+1=\omega ^{\omega +1}+2\omega ^{2}+1}$.

그런 다음 시퀀스 P(m)의 각 용어 P(m)(n)는 f(G)(m)(n),n+1)로 정의된다.예를 들어 G(3)(1) = 3¹ = 2 + 2 및⁰ P(3)(1) = f(2¹ + 2,2⁰) = Ω¹ = Ω⁰ = Ω = Ω + Ω + 1. 순서형 숫자의 덧셈, 곱셈, 지수를 잘 정의한다.

는 f( ( )( n), + )> (n + ) + ) ,n+ ) ${\displaystyle f (G(m)$ ($n),n+1)>f(g(m$) ($n+1$) $,n+2)}$을 다음과 같이 주장한다

Goodstein 시퀀스의 다음 요소를 생성하기 위해 첫 번째 베이스 교환 작업을 적용한 후, 이 세대에서는 두 번째 마이너스 1 작업 전에 $G{\displaystyle {}^{(}m}$)${\displaystyle }$(${\displaystyle n}$) ${\displaystyle G'(m)(n)}$을 G(m)(n)로$$ 한다.$G{\displaystyle }$( ${\displaystyle m}$)${\displaystyle }$( ${\displaystyle \mathrm{n}}$+ 1${\displaystyle }$)${\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$( ${\displaystyle m}$)${\displaystyle }$( ${\displaystyle n}$)${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle G(m)(n+1)=G'(m)-1$을 관찰한다.

그러면 분명히 $f{\displaystyle }$( ${\displaystyle G}$( ${\displaystyle m}$)${\displaystyle }$( n${\displaystyle }$)${\displaystyle }$, ${\displaystyle n}$+ 1${\displaystyle }$)${\displaystyle }$= f${\displaystyle }$( ${\displaystyle G}$ ${\displaystyle {\prime }^{}}$( m${\displaystyle }$)${\displaystyle }$( ${\displaystyle n}$)${\displaystyle }$, ${\displaystyle \mathrm{n}}$+ ${\displaystyle 2}$) ${\displaystyle$ f$(G(m)(n),n+1)=f(G'm$),$n+2$이제 우리는 n+2)>이름(G(m)(n+1), n+2){\displaystyle f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)}, G′(m)(n))G(m)(n+1)+1{G'(m)(n)=G(m)(n+1)+1\displaystyle}. 예를 들어 영하 1운영, 그리고 f(G′(m)(n)을 적용, G(4)=22{\displaystyle G(4)(1)=2^{2}}G(4(1). )(2${\displaystyle G(4)(2)=2\cdot 3^{2}+2\cdot 3+2}$, so ${\displaystyle f(2^{2},2)=\omega ^{\omega }}$ and ${\displaystyle f(2\cdot 3^{2}+2\cdot 3+2,3)=2\omega ^{2}+2\omega +2}$, which is strictly smaller.참고로 f(G(m)(n),n+1)를 계산하려면 먼저 ${\displaystyle {\Omega }^{}}$- 1 {\$displaystyle \omega ^{\omega$$^{\$^{\$1$}-$}$ 식과 같이$$ g(m)(n)을 유전 베이스 n+${\displaystyle 1}$ 표기법으로 써야 한다$.$

따라서 시퀀스 P(m)는 엄격히 감소하고 있다.표준 순서 <의 서수>가 근거가 충분하므로, 무한히 감소하는 서열은 존재할 수 없으며, 또는 동등하게, 엄격하게 감소하는 서열은 모두 종료된다(그리고 무한할 수 없다).그러나 P(m)(n)는 G(m)(n)에서 직접 계산한다.따라서 시퀀스 G(m)도 종료되어야 하며 이는 반드시 0에 도달해야 함을 의미한다.

굿스타인의 정리라는 이 증거는 상당히 쉬운 반면,^[1] 굿스타인의 정리가 페이노 산술의 정리가 아니라는 것을 보여주는 커비-파리스의 정리는 기술적이고 상당히 더 어렵다.그것은 페아노 산술의 셀 수 없는 비표준 모델을 사용한다.

연장된 굿스타인의 정리

Goodstein 시퀀스의 정의가 b + 1로 바뀌었다고 가정합시다. b + 1은 b + 2로 대체한다.그 순서가 아직 끝나지 않았을까?보다 일반적으로 b₁, b₂, b₃, …을 정수의 순서에 따르도록 한다.그런 다음 m의 확장된 굿스타인 수열의 (n + 1)-초기 G(m)(n + 1)-초기 G(m)(n + 1)가 다음과 같이 되도록 한다: G(m)(n)의 세습 b를_n 취하고 b(n)의_n 각 발생을 b로_n+1 교체한 다음 1을 뺀다.그 주장은 이 시퀀스가 여전히 종료된다는 것이다.확장증명은 P(m)(n) = f(G)(m)(n), n)를 다음과 같이 정의한다. G(m)(n)의 유전적 b를_n 취하고, base b의_n 발생을 첫 번째 무한 서수 Ω으로 대체한다.G(m)(n)에서 G(m)(n)(n + 1)로 이동할 때 굿스타인 시퀀스의 기저변환 연산은 여전히 f의 값을 변경하지 않는다.예를 들어, bn)4, 만약bn+1=9, f(3⋅ 444+4,4)=3ω ω ω+ω)f({\displaystyle f(3\cdot 4^{4^{4}}+4,4)=3\omega ^{\omega ^{\omega}}+\omega =f(3\cdot 9^{9^{9}}+9,9)}그 서수 f(3⋅ 444+4,4){\displaystyle f(3\cdot 4^{4^{4}}+4,4)}엄격하다.사행서수 $f{\displaystyle }$(${\displaystyle 3}$ 9${\displaystyle {{}^{}}^{}}$9 +${\displaystyle 9}$ )${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle 9}$) .${\displaystyle f{{\big (}\cdot 9^{9}}+9)-1,9{\big )}$보다 큼.$}$

시작 값의 함수로서 시퀀스 길이

The Goodstein function, ${\displaystyle {\mathcal {G}}:\mathbb {N} \to \mathbb {N} }$, is defined such that ${\displaystyle {\mathcal {G}}(n)}$ is the length of the Goodstein sequence that starts with n. (This is a total function since every Goodstein sequence terminates.)$G{\displaystyle \mathcal{}}$ ${\$의 극한 증가율은 하디 계층 구조에서$$ $H{\displaystyle {}_{}}$ ${\displaystyle {\alpha }_{}}$ ${\$ 빠르게 성장하는 계층 구조에서$$ ${\displaystyle {f\alpha }_{}}$ ${\$과 같은 기능의 다양한 표준 순서 지수 계층 구조와 관련시켜 보정할 수 있다$$.뢰브 자손과 와이너 자손이다.

• 커비와 파리(1982)는 이 사실을 증명했다.

${\displaystyle {\mathcal {G}}}$ has approximately the same growth-rate as ${\displaystyle H_{\epsilon _{0}}}$ (which is the same as that of ${\displaystyle f_{\epsilon _{0}}}$); more precisely, ${\displaystyle {\mathcal {G}}}$ dominates ${\displaystyle H_{\alpha }}$ forα < ${\$<\$epsilon _{0$ $그리고{\displaystyle {}_{}}$ H ${\displaystyle {{0\mathrm{}}_{}}_{}}$0 {\$displaystyle$ H_${\epsilon _{$0}}}이 $G$. ${\displaystyle {\mathcal}\,\,\!$$}$

(${\displaystyle 두}$ 가지 함수 f${\displaystyle }$: g : ${\displaystyle N\mathbb{}}$→ ${\displaystyle N\mathbb{}}$ ${\$$displaystyle$ $f,g:\mathb {N} \to \mathb${$n},$f ${\displaystyle$ $f$$}$은( ${\$$displaystystyle$f($n)}을($$$$n)$로 충분히 큰 $경우{\displaystyle }$ g$}$을 지배한다고 $한다$.

• 시촌(1983)은 다음과 같은 것을 보여주었다.

${\displaystyle {\mathcal{G}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,}$

여기서 R ${\displaystyle {2\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}(n}$ )$${\$displaystyle R_{2}^{\\omega$}($n)}}$은 유전 베이스-2 표기법에 n을 넣은 다음 모든 2s를 Ω으로 대체한 결과(굿스타인의 정리 증명에 행해진 것과 같다)이다$$.

• 카이세도(2007)는 $n{\displaystyle }$= ${\displaystyle {{2m\mathrm{}}_{}}^{}}$ 1${\displaystyle {{}_{}}^{}}$+ ${\displaystyle {{2m\mathrm{}}_{}}^{}}$ 2${\displaystyle {{}_{}}^{}}$+ ${\displaystyle \cdots }$+ ${\displaystyle {{2m}_{}}^{}}$ k {\$displaystyle n=2^{m_{$1}+$2^{m_{2}}+}+\cdots +2^{$2^{$m$}를 나타냈다.$_{k}},$ m > 2 > > k$,${\$displaystyle m_{1}>m_{2}>\cdots >m_{k}},$ 그 다음

${\displaystyle {\mathcal {G}}(n)=f_{R_{2}^{\omega }(m_{1})}(f_{R_{2}^{\omega }(m_{2})}(\cdots (f_{R_{2}^{\omega }(m_{k})}(3))\cdots ))-2}$.

몇 가지 예:

n			${\displaystyle {\mathcal{G}(n)}$
1	${\displaystyle 2^{0}}$	$(\displaystyle 2-1})$	${\displaystyle H_{\omega}(1)-1}$	${\displaystyle f_{0}(3)-2}$	2
2	${\displaystyle 2^{1}$	${\displaystyle 2^{1}+1-1}$	${\displaystyle H_{\omega +1}(1)-1}$	${\displaystyle f_{1}(3)-2}$	4
3	${\displaystyle 2^{1}+2^{0}}$	${\displaystyle 2^{2}-1}$	${\displaystyle H_{\omega ^{\\omega ^}(1)-1}$	${\displaystyle f_{1}(f_{0}(3)-2}$	6
4	${\displaystyle 2^{2}}$	${\displaystyle 2^{2}+1-1}$	${\displaystyle H_{\omega ^{\omega ^}+1}(1)-1}$	${\displaystyle f_{\omega}(3)-2}$	3·2402653211 − 2 ≈ 6.895080803×10121210694
5	${\displaystyle 2^{2}+2^{0}}}$	${\displaystyle 2^{2}+2-1}$	${\displaystyle H_{\omega ^{\omega ^{\omega }+\omega }(1)-1}$	${\displaystyle f_{\omega}(f_{0}(3)-2}$	> A(4,4) > 10101019728
6	${\displaystyle 2^{2}+2^{1}}$	${\displaystyle 2^{2}+2+1-1}$	${\displaystyle H_{\omega ^{\omega ^}+\omega +1}(1)-1}$	${\displaystyle f_{\omega}(f_{1}(3)-2}$	> A(6,6)
7	${\displaystyle 2^{2}+2^{1}+2^{0}}$	${\displaystyle 2^{2+1}-1}$	${\displaystyle H_{\omega ^{\omega +1}(1)-1}$	${\displaystyle f_{\omega}(f_{1}(f_{0}(3)))--2}$	> A(8,8)
8	${\displaystyle 2^{2+1}$	${\displaystyle 2^{2+1}+1-1}$	${\displaystyle H_{\omega ^{\omega +1}+1}(1)-1}$	${\displaystyle f_{\omega +1}(3)-2}$	> A3(3,3) = A(61, 61) A(61, 61)
$\displaystyle \vdots }$
12	${\displaystyle 2^{2+1}+2^{2}}$	${\displaystyle 2^{2+1}+2^{2}+1-1}$	${\displaystyle H_{\omega ^{\omega +1}+{\omega ^{\omega }+1}(1)-1}$	${\displaystyle f_{\omega +1}(f_{\omega }(3)-}-}$	> f(64ω+1) > 그레이엄의 번호
$\displaystyle \vdots }$
19	${\displaystyle 2^{2^{2}}+2^{1}+2^{0}}$	${\displaystyle 2^{2^{2}}+2^{2}-1}$	${\displaystyle H_{\omega ^{\omega ^{\\omega ^}+{\omega ^{\omega ^1}$	${\displaystyle f_{\omega ^{\\omega ^}(f_{1})(f_{0}(3))-}-}$

(Ackermann 함수 및 Graham의 수 제한에 대해서는 빠르게 증가하는 계층#빠르게 성장하는 계층의 기능을 참조하십시오.)

계산 가능한 함수에 응용 프로그램

굿스타인의 정리는 페이노 산술로는 총체라고 증명할 수 없는 총 계산 가능한 함수를 구성하는 데 사용될 수 있다.숫자의 Goodstein 순서는 Turing 기계에 의해 효과적으로 열거될 수 있다. 따라서 n의 Goodstein 순서가 종료되는 데 필요한 단계 수에 n을 매핑하는 기능은 특정 Turing 기계에 의해 계산될 수 있다.이 기계는 n의 굿스타인 시퀀스를 열거할 뿐이며, 시퀀스가 0이 되면 시퀀스의 길이를 반환한다.모든 Goodstein 시퀀스는 결국 종료되기 때문에, 이 기능은 총체적이다.그러나 페아노 산술은 모든 굿스타인 염기서열이 종료된다는 것을 증명하지 못하기 때문에, 페아노 산술은 이 튜링 기계가 총함수를 계산한다는 것을 증명하지 못한다.

참고 항목

• 비표준 산술 모형
• 빠르게 성장하는 계층 구조
• 파리-해링턴 정리
• 카나모리-맥칼룬 정리
• 크루스칼의 트리 정리

참조

참고 문헌 목록

• Goodstein, R. (1944), "On the restricted ordinal theorem", Journal of Symbolic Logic, 9 (2): 33–41, doi:10.2307/2268019, JSTOR 2268019, S2CID 235597.
• Cichon, E. (1983), "A Short Proof of Two Recently Discovered Independence Results Using Recursive Theoretic Methods", Proceedings of the American Mathematical Society, 87 (4): 704–706, doi:10.2307/2043364, JSTOR 2043364.
• Caicedo, A. (2007), "Goodstein's function" (PDF), Revista Colombiana de Matemáticas, 41 (2): 381–391.

외부 링크

• Weisstein, Eric W. "Goodstein Sequence". MathWorld.
• 굿스타인의 정리가 PA의 정리가 아니라는 증거의 일부 요소, 저스틴 T 밀러의 학부 논문에서 나온 것이다.
• Goodstein의 정리를 통한 Peano 산술 비표준모델의 분류 - Dan Kaplan, Franklan, Marshall College Library의 논문
• 하스켈과 람다 미적분학의 굿스타인 시퀀스 정의
• 자바 애플릿으로 구현된 하이드라 게임
• 하이드라 게임의 변종 Javascript 구현
• Goodstein 시퀀스: 인피니티를 통한 우회로의 힘 - Goodstein Sequence와 히드라 게임의 삽화가 있는 좋은 설명.
• 굿스타인 계산기