굿스타인의 정리

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

약한 굿스타인 수열

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

1. $g_2 = m$
2. $g_n = 0$ 이면 $g_{n+1} = 0$ 이다.
3. $b_0 < ... < b_k$ 이고, $0 < a_0, ..., a_k < n$ 에 대해, $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$ 이 성립한다.

공식화

굿스타인의 정리는 다음과 같이 공식화할 수 있다.

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

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

사례

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

• 초항이 $1$ 인 경우, 다음 항은 명백히 $0 = 1 - 1$ 이 된다.

• 초항이 $2 = 2^1$ 인 경우, 다음 항은 $2 = 3^1 - 1$ 이고, 다음 항은 $1 = 2 - 1$, 그리고 다음 항은 $0 = 1 - 1$ 이 되어 결국 0으로 끝나게 된다.

• 초항이 $3 = 2^1 + 1$ 인 경우, 항을 계속 나열하면 $3 = 3^1 + 1 - 1$, $3 = 4^1 - 1$, $2 = 3 - 1$, $1 = 2 - 1$, $0 = 1 - 1$ 이 되어 0으로 끝나게 된다.

• 초항이 $4 = 2^2$ 인 경우, $8 = 3^2 - 1$, $9 = 4*2 + 2 - 1$, $10 = 5*2 + 1 - 1$, $11 = 6*2 - 1$, $11 = 7 + 5 - 1$, $11 = 8 + 4 - 1$, $11 = 9 + 3 - 1$, $11 = 10 + 2 - 1$, $11 = 11 + 1 - 1$, $11 = 12 - 1$, $10 = 11 - 1$, ..., $0 = 1 - 0$.

증명

이 정리의 증명에는 다음과 같은 보조정리가 필요하다.

• (보조정리) 위와 같은 조건에서, 임의의 서수 a에 대하여 $a^{b_n}a_n + ... + a^{b_0}a_0 < a^{b_n + 1}$.

이제 위의 약한 굿스타인 수열 $g_n$ 에 대하여, $h_n$ 를 다음과 같이 정의하자.(아래에서 ω는 첫 번째 초한서수)

• $h_n = \omega^{b_k}a_k + ... + \omega^{b_0}a_0$

그러면 $h_n$ 은 다음 성질을 만족한다.

• $g_n > 0$ 이면 $h_n > 0$ 이고 $h_n > h_{n+1}$ 이다.

전자는 자명하다. 후자의 경우 $b_0 = 0$ 이면 분명하므로 $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$

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

• $h_{n+1} = \omega^{b_k}a_k + ... + \omega^{b_0}(a_0 - 1) + \omega^{b_0 - 1}n + ... + n$
• $< \omega^{b_k}a_k + ... + \omega^{b_0}(a_0 - 1) + \omega^{b_0} = h_n$

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

같이 보기

• 패리스의 정리

참고 문헌

• 최창선, 《집합론 입문》, 경문사, 2006.