굿스타인의 정리

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

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

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

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

  1. 이면 이다.
  2. 이고, 에 대해, 이면 이 성립한다.

공식화[편집]

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

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

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

사례[편집]

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

  • 초항이 인 경우, 다음 항은 명백히 이 된다.
  • 초항이 인 경우, 다음 항은 이고, 다음 항은 , 그리고 다음 항은 이 되어 결국 0으로 끝나게 된다.
  • 초항이 인 경우, 항을 계속 나열하면 , , , , 이 되어 0으로 끝나게 된다.
  • 초항이 인 경우, , , , , , , , , , , , ..., .

증명[편집]

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

  • (보조정리) 위와 같은 조건에서, 임의의 순서수 a에 대하여 .

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

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

  • 이면 이고 이다.

전자는 자명하다. 후자의 경우 이면 분명하므로 이 0보다 크다고 가정하면,

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

이 되어 증명이 된다. 이제 {} 는 순서수의 모임이므로 최소원소 를 갖는다. 이 경우 이 된다. 이로부터 위의 성질에서 을 얻어 증명이 끝난다.

같이 보기[편집]

참고 문헌[편집]