굿스타인의 정리

굿스타인의 정리(Goodstein's theorem, -定理)는 집합론의 정리이다. 이 정리는 처음에는 증가하는 것 같지만 결국에는 0으로 감소하는 수열(약한 굿스타인 수열)의 예를 들고 있다. 영국 수학자 루벤 루이스 굿스타인의 이름이 붙어 있으며, 굿스타인에 의해 1944년 처음 증명되었다.^[1]:71 이 정리의 보다 강한 판본은 패리스의 정리로 주어진다. 패리스의 정리는 영국 수학자 제프 패리스(Jeff Paris)의 이름에서 따왔으며, 1981년 처음 증명되었다.^[1]:71

굿스타인의 정리를 이해하기 위해서는 다음 개념을 먼저 이해해야 할 필요가 있다. 초항이 m인(m은 자연수) 약한 굿스타인 수열이란 자연수 n≥2에 대해 정의된 순서수열 ${\displaystyle \{g_{n}\}}$ 으로, 순서수열 ${\displaystyle \{a_{n}\}}$과 ${\displaystyle \{b_{n}\}}$에 대해 다음 세 조건을 만족하는 것이다.^[1]:66

1. ${\displaystyle g_{2}=m}$
2. ${\displaystyle g_{n}=0}$ 이면 ${\displaystyle g_{n+1}=0}$이다.
3. ${\displaystyle b_{0}<...<b_{k}}$ 이고, ${\displaystyle 0<a_{0},...,a_{k}<n}$ 에 대해, ${\displaystyle g_{n}=n^{b_{k}}a_{k}+...+n^{b_{0}}a_{0}>0}$ 이면 ${\displaystyle g_{n+1}=(n+1)^{b_{k}}a_{k}+...+(n+1)^{b_{0}}a_{0}-1}$ 이 성립한다.

굿스타인의 정리는 다음과 같이 공식화할 수 있다.^[1]:67

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

이 정리는 자연수에 관한 정리임에도 순서수의 이론을 도입하지 않으면 증명이 어렵다.

약한 굿스타인 수열이 0으로 감소하는 몇 가지 예를 들어 보자.

• 초항이 ${\displaystyle 1}$ 인 경우, 다음 항은 명백히 ${\displaystyle 0=1-1}$ 이 된다.
• 초항이 ${\displaystyle 2=2^{1}}$ 인 경우, 다음 항은 ${\displaystyle 2=3^{1}-1}$ 이고, 다음 항은 ${\displaystyle 1=2-1}$, 그리고 다음 항은 ${\displaystyle 0=1-1}$이 되어 결국 0으로 끝나게 된다.
• 초항이 ${\displaystyle 3=2^{1}+1}$ 인 경우, 항을 계속 나열하면 ${\displaystyle 3=3^{1}+1-1}$, ${\displaystyle 3=4^{1}-1}$, ${\displaystyle 2=3-1}$, ${\displaystyle 1=2-1}$, ${\displaystyle 0=1-1}$이 되어 0으로 끝나게 된다.
• 초항이 ${\displaystyle 4=2^{2}}$ 인 경우, ${\displaystyle 8=3^{2}-1}$, ${\displaystyle 9=4*2+2-1}$, ${\displaystyle 10=5*2+1-1}$, ${\displaystyle 11=6*2-1}$, ${\displaystyle 11=7+5-1}$, ${\displaystyle 11=8+4-1}$, ${\displaystyle 11=9+3-1}$, ${\displaystyle 11=10+2-1}$, ${\displaystyle 11=11+1-1}$, ${\displaystyle 11=12-1}$, ${\displaystyle 10=11-1}$, ..., ${\displaystyle 0=1-0}$.

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

• (보조정리) 위와 같은 조건에서, 임의의 순서수 a에 대하여 ${\displaystyle a^{b_{n}}a_{n}+...+a^{b_{0}}a_{0}<a^{b_{n}+1}}$.

이제 위의 약한 굿스타인 수열 ${\displaystyle g_{n}}$ 에 대하여, ${\displaystyle h_{n}}$를 다음과 같이 정의하자.(아래에서 ω는 첫 번째 초한순서수)

• ${\displaystyle h_{n}=\omega ^{b_{k}}a_{k}+...+\omega ^{b_{0}}a_{0}}$

그러면 ${\displaystyle h_{n}}$ 은 다음 성질을 만족한다.

• ${\displaystyle g_{n}>0}$ 이면 ${\displaystyle h_{n}>0}$ 이고 ${\displaystyle h_{n}>h_{n+1}}$이다.

전자는 자명하다. 후자의 경우 ${\displaystyle b_{0}=0}$ 이면 분명하므로 ${\displaystyle b_{0}}$이 0보다 크다고 가정하면,

• ${\displaystyle 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}$

이므로, 위의 보조정리에 의하여,

• ${\displaystyle h_{n+1}=\omega ^{b_{k}}a_{k}+...+\omega ^{b_{0}}(a_{0}-1)+\omega ^{b_{0}-1}n+...+n}$
• ${\displaystyle <\omega ^{b_{k}}a_{k}+...+\omega ^{b_{0}}(a_{0}-1)+\omega ^{b_{0}}=h_{n}}$

이 되어 증명이 된다. 이제 ${\displaystyle \{h_{n}|h_{n}>0\}}$는 순서수의 모임이므로 최소원소 ${\displaystyle h_{r}}$를 갖는다. 이 경우 ${\displaystyle h_{r+1}=0}$이 된다. 이로부터 위의 성질에서 ${\displaystyle g_{r+1}=0}$을 얻어 증명이 끝난다.

패리스의 정리는 다음과 같이 공식화할 수 있다.^[1]:69 증명은 굿스타인의 정리에서와 유사하게 할 수 있으나 약간 더 까다롭다.

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

이 정리는 굿스타인의 정리와 유사하게, 자연수에 관한 정리임에도 순서수의 이론을 도입하지 않으면 증명이 어렵다. 실제로 패리스와 로리 커비(Laurie Kirby)는 이 정리에 대해서 다음 명제를 증명하였다.^[1]:71

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

이에 따라서, 만약 패리스의 정리가 페아노 산술 내에서 증명이 된다면 페아노 산술이 모형을 갖는 것이 페아노 산술의 정리가 되어 괴델의 불완전성 정리에 모순이 된다. 따라서, 패리스의 정리는 통상적인 자연수 체계인 페아노 산술에서 증명불가능하다.

• Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic", Bulletin London Mathematical Society 14: 285–293.