굿스타인 정리

굿스타인 정리는 자연수론의 한 정리로, hereditary base-n 표기법과 굿스타인 수열에 관련된 결과를 담고 있다. 1944년 루벤 굿스타인(Reuben Goodstein)이 증명했으며, 페아노 공리계로는 증명할 수 없다는 사실이 알려져 있다. 즉, 수학적 귀납법만으로는 증명할 수 없는 정리의 대표적인 예시 중 하나이다.

정의

굿스타인 수열은 다음과 같이 정의된다.

1. 자연수 n을 선택한다.
2. n을 hereditary base-2 표기법으로 나타낸다. (예: 26 = 2³ + 2¹ + 2⁰은 hereditary base-2 표기법으로도 동일하다.)
3. base를 3으로 바꾼 후 1을 뺀다.
4. 결과가 0이 될 때까지 base를 4, 5, 6, ... 순서대로 바꿔가며 1을 빼는 과정을 반복한다.

굿스타인 정리는 위와 같은 과정을 통해 얻어지는 굿스타인 수열은 유한한 횟수의 반복 후 반드시 0에 도달한다는 것을 보장한다. 겉보기에는 수가 기하급수적으로 증가할 수 있지만, 충분히 큰 base에 도달하면 감소하는 속도가 증가 속도를 압도하여 결국 0이 된다.

페아노 공리계와의 관계

굿스타인 정리는 페아노 공리계로는 증명할 수 없는 정리이다. 이는 커스칼 나무 정리와 함께 괴델의 불완전성 정리의 구체적인 예시로 간주된다. 굿스타인 정리의 증명에는 초한 귀납법이 필요하며, 이는 페아노 공리계에서 다룰 수 없는 개념이다. 굿스타인 정리가 페아노 공리계로 증명 불가능하다는 사실은 로리 베켓이 1982년에 증명했다.

의미

굿스타인 정리는 수학적 귀납법으로는 증명할 수 없는 직관적으로 보이는 명제가 존재한다는 것을 보여준다. 이는 수학적 공리계의 한계를 보여주는 중요한 사례이며, 수학 기초론 연구에 영향을 미쳤다.