굿스타인의 정리 (Goodstein's theorem, -定理)는 집합론 의 정리 이다. 이 정리는 처음에는 증가하는 것 같지만 결국에는 0으로 감소하는 수열 (약한 굿스타인 수열)의 예를 들고 있다. 영국 수학자 루벤 루이스 굿스타인 의 이름이 붙어 있으며, 굿스타인에 의해 1944년 처음 증명되었다.[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}
초항이
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}
초항이
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}}
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}
같이 보기 참고 문헌 
