굿스타인의 정리(Goodstein's theorem)는 임의의 자연수에서 시작하는 굿스타인 수열이 유한한 숫자의 항을 갖는다는 정리이다. 이 정리는 사실이지만 페아노 공리계로 증명할 수 없으며, 이것은 불완전성 정리가 발표된 뒤 발견된 "사실이지만 증명 불가능한 명제"들 중 하나로, 앞선 것들보다 상대적으로 설명하기 쉽고 굿스타인 수열의 값 자체가 큰 수이기 때문에 유명해지게 되었다.

이 영상들을 참고하면 된다: 소개 상세

약한 굿스타인 수열을 알고 있으면 굿스타인 수열을 이해하기 쉽다. 약한 굿스타인 수열은 이렇게 정의된다.

약한 굿스타인 수열은 항상 유한한 단계 뒤에 끝나게 되며, 이것은 서수 개념이 필요하지만 페아노 공리계에서 증명 가능하다. 수열의 각 값은 어떠한 서수에 대응되고, (예를 들어, 위의 $a_1=11=2^3+2^1+2^0$은 $\omega^3+\omega+1$) 이 대응된 서수는 1을 빼는 과정 때문에 줄어들기만 한다.

반복 n진법 표현은 어떤 자연수 $m$을 n진법 전개 $\Sigma_{i=0}^k {d_i n^i}$로 나타낸 뒤, 각각의 $i$를 다시 n진법 전개로 나타내고, 이 과정을 더 이상 반복할 수 없을 때까지 계속하는 것이다.

따라서, 11의 반복 2진법 표현은 $11=2^3+2^1+2^0=2^{2^1+2^0}+2^1+2^0$이 된다.

굿스타인 수열은 약한 굿스타인 수열의 n진법 표현을 반복 n진법 표현으로 대체한 것이다. 약한 굿스타인 수열보다 훨씬 급격히 커지지만 유한한 단계 뒤에 끝나는 것은 같다. 약한 굿스타인 수열과 달리, 이 수열이 유한한 단계 뒤에 끝난다는 것은 페아노 공리계에서 증명할 수 없다. 증명은 약한 굿스타인 수열의 경우와 거의 동일하지만, 이 경우 대응하는 서수가 $\omega^{\omega^{\omega^\cdots}}=\epsilon_0$보다 작은 어떤 것이든 올 수 있게 된다. 약한 굿스타인 수열의 경우, 대응하는 서수의 상한은 $\omega^\omega$였다.

불완전성 정리가 증명된 뒤 4년이 지난 1935년에, 게르하르트 겐첸은 초한 귀납법의 정당성을 $\epsilon_0$ 이상의 서수에 대해서 보일 수 없다는 사실을 증명하였다. 이것은 그 자체로 페아노 공리계에 대한 불완전성 정리의 직접적인 증명이 된다.

굿스타인은 1944년에 큰 서수에 대한 초한 귀납법이 필요한 굿스타인 정리를 증명하면서, 참이지만 페아노 공리계에서 증명할 수 없는 또 다른 명제를 만들어 냈다.

이후, 램지 이론에서 증명된 패리스-해링턴 정리가 페아노 공리계에서는 증명될 수 없다는 사실이 밝혀지면서, 패리스-해링턴 정리는 최초로 불완전성 원리의 "자연스러운" 예가 되었다.

$n$에서 시작하는 약한 굿스타인 수열의 최대값을 $g(n)$, 굿스타인 수열의 최대값은 $G(n)$이라고 하면, $g(n)$은 대략 $f_{\omega^\omega}(n)$와 비슷한 크기이고, $G(n)$은 $f_{\epsilon_0}(n)$ 정도인 것을 알 수 있다.