굿스타인의 정리 (Goodstein's theorem, -定理)는 집합론 의 정리 이다. 이 정리는 처음에는 증가하는 것 같지만 결국에는 0으로 감소하는 수열 (약한 굿스타인 수열)의 예를 들고 있다. 영국 수학자 루벤 루이스 굿스타인 의 이름이 붙어 있으며, 굿스타인에 의해 1944년 처음 증명되었다.[ 1] :71 이 정리의 보다 강한 판본은 패리스의 정리로 주어진다. 패리스의 정리 는 영국 수학자 제프 패리스 (Jeff Paris)의 이름에서 따왔으며, 1981년 처음 증명되었다.[ 1] :71
굿스타인의 정리를 이해하기 위해서는 다음 개념을 먼저 이해해야 할 필요가 있다. 초항이 m인(m은 자연수 ) 약한 굿스타인 수열 이란 자연수 n≥2에 대해 정의된 순서수 열
{
g
n
}
{\displaystyle \{g_{n}\}}
으로, 순서수열
{
a
n
}
{\displaystyle \{a_{n}\}}
과
{
b
n
}
{\displaystyle \{b_{n}\}}
에 대해 다음 세 조건을 만족하는 것이다.[ 1] :66
g
2
=
m
{\displaystyle g_{2}=m}
g
n
=
0
{\displaystyle g_{n}=0}
이면
g
n
+
1
=
0
{\displaystyle g_{n+1}=0}
이다.
b
0
<
.
.
.
<
b
k
{\displaystyle b_{0}<...<b_{k}}
이고,
0
<
a
0
,
.
.
.
,
a
k
<
n
{\displaystyle 0<a_{0},...,a_{k}<n}
에 대해,
g
n
=
n
b
k
a
k
+
.
.
.
+
n
b
0
a
0
>
0
{\displaystyle g_{n}=n^{b_{k}}a_{k}+...+n^{b_{0}}a_{0}>0}
이면
g
n
+
1
=
(
n
+
1
)
b
k
a
k
+
.
.
.
+
(
n
+
1
)
b
0
a
0
−
1
{\displaystyle g_{n+1}=(n+1)^{b_{k}}a_{k}+...+(n+1)^{b_{0}}a_{0}-1}
이 성립한다.
굿스타인의 정리는 다음과 같이 공식화할 수 있다.[ 1] :67
초항이 자연수인 약한 굿스타인 수열 은 0으로 끝난다.
이 정리는 자연수에 관한 정리임에도 순서수 의 이론을 도입하지 않으면 증명이 어렵다.
약한 굿스타인 수열이 0으로 감소하는 몇 가지 예를 들어 보자.
초항이
1
{\displaystyle 1}
인 경우, 다음 항은 명백히
0
=
1
−
1
{\displaystyle 0=1-1}
이 된다.
초항이
2
=
2
1
{\displaystyle 2=2^{1}}
인 경우, 다음 항은
2
=
3
1
−
1
{\displaystyle 2=3^{1}-1}
이고, 다음 항은
1
=
2
−
1
{\displaystyle 1=2-1}
, 그리고 다음 항은
0
=
1
−
1
{\displaystyle 0=1-1}
이 되어 결국 0으로 끝나게 된다.
초항이
3
=
2
1
+
1
{\displaystyle 3=2^{1}+1}
인 경우, 항을 계속 나열하면
3
=
3
1
+
1
−
1
{\displaystyle 3=3^{1}+1-1}
,
3
=
4
1
−
1
{\displaystyle 3=4^{1}-1}
,
2
=
3
−
1
{\displaystyle 2=3-1}
,
1
=
2
−
1
{\displaystyle 1=2-1}
,
0
=
1
−
1
{\displaystyle 0=1-1}
이 되어 0으로 끝나게 된다.
초항이
4
=
2
2
{\displaystyle 4=2^{2}}
인 경우,
8
=
3
2
−
1
{\displaystyle 8=3^{2}-1}
,
9
=
4
∗
2
+
2
−
1
{\displaystyle 9=4*2+2-1}
,
10
=
5
∗
2
+
1
−
1
{\displaystyle 10=5*2+1-1}
,
11
=
6
∗
2
−
1
{\displaystyle 11=6*2-1}
,
11
=
7
+
5
−
1
{\displaystyle 11=7+5-1}
,
11
=
8
+
4
−
1
{\displaystyle 11=8+4-1}
,
11
=
9
+
3
−
1
{\displaystyle 11=9+3-1}
,
11
=
10
+
2
−
1
{\displaystyle 11=10+2-1}
,
11
=
11
+
1
−
1
{\displaystyle 11=11+1-1}
,
11
=
12
−
1
{\displaystyle 11=12-1}
,
10
=
11
−
1
{\displaystyle 10=11-1}
, ...,
0
=
1
−
0
{\displaystyle 0=1-0}
.
이 정리의 증명에는 다음과 같은 보조정리 [ 1] :65 가 필요하다.
(보조정리) 위와 같은 조건에서, 임의의 순서수 a에 대하여
a
b
n
a
n
+
.
.
.
+
a
b
0
a
0
<
a
b
n
+
1
{\displaystyle a^{b_{n}}a_{n}+...+a^{b_{0}}a_{0}<a^{b_{n}+1}}
.
이제 위의 약한 굿스타인 수열
g
n
{\displaystyle g_{n}}
에 대하여,
h
n
{\displaystyle h_{n}}
를 다음과 같이 정의하자.(아래에서 ω는 첫 번째 초한순서수)
h
n
=
ω
b
k
a
k
+
.
.
.
+
ω
b
0
a
0
{\displaystyle h_{n}=\omega ^{b_{k}}a_{k}+...+\omega ^{b_{0}}a_{0}}
그러면
h
n
{\displaystyle h_{n}}
은 다음 성질을 만족한다.
g
n
>
0
{\displaystyle g_{n}>0}
이면
h
n
>
0
{\displaystyle h_{n}>0}
이고
h
n
>
h
n
+
1
{\displaystyle h_{n}>h_{n+1}}
이다.
전자는 자명하다. 후자의 경우
b
0
=
0
{\displaystyle b_{0}=0}
이면 분명하므로
b
0
{\displaystyle b_{0}}
이 0보다 크다고 가정하면,
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 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
=
ω
b
k
a
k
+
.
.
.
+
ω
b
0
(
a
0
−
1
)
+
ω
b
0
−
1
n
+
.
.
.
+
n
{\displaystyle h_{n+1}=\omega ^{b_{k}}a_{k}+...+\omega ^{b_{0}}(a_{0}-1)+\omega ^{b_{0}-1}n+...+n}
<
ω
b
k
a
k
+
.
.
.
+
ω
b
0
(
a
0
−
1
)
+
ω
b
0
=
h
n
{\displaystyle <\omega ^{b_{k}}a_{k}+...+\omega ^{b_{0}}(a_{0}-1)+\omega ^{b_{0}}=h_{n}}
이 되어 증명이 된다. 이제
{
h
n
|
h
n
>
0
}
{\displaystyle \{h_{n}|h_{n}>0\}}
는 순서수의 모임이므로 최소원소
h
r
{\displaystyle h_{r}}
를 갖는다. 이 경우
h
r
+
1
=
0
{\displaystyle h_{r+1}=0}
이 된다. 이로부터 위의 성질에서
g
r
+
1
=
0
{\displaystyle g_{r+1}=0}
을 얻어 증명이 끝난다.
패리스의 정리는 다음과 같이 공식화할 수 있다.[ 1] :69 증명은 굿스타인의 정리에서와 유사하게 할 수 있으나 약간 더 까다롭다.
초항이 자연수인 굿스타인 수열 은 0으로 끝난다.
이 정리는 굿스타인의 정리와 유사하게, 자연수에 관한 정리임에도 순서수 의 이론을 도입하지 않으면 증명이 어렵다. 실제로 패리스와 로리 커비 (Laurie Kirby)는 이 정리에 대해서 다음 명제를 증명하였다.[ 1] :71
이에 따라서, 만약 패리스의 정리가 페아노 산술 내에서 증명이 된다면 페아노 산술이 모형을 갖는 것이 페아노 산술의 정리가 되어 괴델의 불완전성 정리 에 모순이 된다. 따라서, 패리스의 정리는 통상적인 자연수 체계인 페아노 산술에서 증명불가능하다.