굿스타인의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

약한 굿스타인 수열[편집]

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

  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 이 성립한다.

공식화[편집]

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

  • 초항이 자연수인 약한 굿스타인 수열은 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.

증명[편집]

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

  • (보조정리) 위와 같은 조건에서, 임의의 순서수 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을 얻어 증명이 끝난다.

같이 보기[편집]

참고 문헌[편집]