굿스타인의 정리 문서 원본 보기

'''굿스타인의 정리'''(Goodstein's theorem, -定理)는 [[집합론]]의 [[정리]]이다. 이 정리는 처음에는 증가하는 것 같지만 결국에는 0으로 감소하는 [[수열]](약한 굿스타인 수열)의 예를 들고 있다. [[영국]] 수학자 [[루벤 루이스 굿스타인]]의 이름이 붙어 있으며, 굿스타인에 의해 [[1944년]] 처음 증명되었다.<ref name="최창선">{{서적 인용|저자=최창선|제목=수학, 철학, 전산학, 언어학도를 위한 집합론 입문|출판사=경문사|날짜=2006|isbn=89-7282-777-0|url=http://kyungmoon.com/shop_product/shop_pdt_view.php?p_idx=4599|언어=ko|access-date=2014-11-19|archive-date=2014-11-29|archive-url=https://web.archive.org/web/20141129034347/http://kyungmoon.com/shop_product/shop_pdt_view.php?p_idx=4599|url-status=}}</ref>{{rp|71}} 이 정리의 보다 강한 판본은 패리스의 정리로 주어진다. [[#패리스의 정리|패리스의 정리]]는 [[영국]] 수학자 [[제프 패리스]](Jeff Paris)의 이름에서 따왔으며, [[1981년]] 처음 증명되었다.<ref name="최창선"/>{{rp|71}}

== 약한 굿스타인 수열 ==
굿스타인의 정리를 이해하기 위해서는 다음 개념을 먼저 이해해야 할 필요가 있다. 초항이 m인(m은 [[자연수]]) '''약한 굿스타인 수열'''이란 자연수 n≥2에 대해 정의된 [[순서수]]열 <math>\{g_n\}</math> 으로, 순서수열 <math>\{a_n\}</math>과 <math>\{b_n\}</math>에 대해 다음 세 조건을 만족하는 것이다.<ref name="최창선"/>{{rp|66}}

# <math>g_2 = m</math>
# <math>g_n = 0</math> 이면 <math>g_{n+1} = 0</math>이다.
# <math>b_0 < ... < b_k</math> 이고, <math>0 < a_0, ..., a_k < n</math> 에 대해, <math>g_n = n^{b_k}a_k + ... + n^{b_0}a_0 > 0</math> 이면 <math>g_{n+1} = (n+1)^{b_k}a_k + ... + (n+1)^{b_0}a_0 - 1</math> 이 성립한다.

== 공식화 ==
굿스타인의 정리는 다음과 같이 공식화할 수 있다.<ref name="최창선"/>{{rp|67}}

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

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

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

* 초항이 <math>1</math> 인 경우, 다음 항은 명백히 <math>0 = 1 - 1</math> 이 된다.
* 초항이 <math>2 = 2^1</math> 인 경우, 다음 항은 <math>2 = 3^1 - 1</math> 이고, 다음 항은 <math>1 = 2 - 1</math>, 그리고 다음 항은 <math>0 = 1 - 1</math>이 되어 결국 0으로 끝나게 된다.
* 초항이 <math>3 = 2^1 + 1</math> 인 경우, 항을 계속 나열하면 <math>3 = 3^1 + 1 - 1</math>, <math>3 = 4^1 - 1</math>, <math>2 = 3 - 1</math>, <math>1 = 2 - 1</math>, <math>0 = 1 - 1</math>이 되어 0으로 끝나게 된다.
* 초항이 <math>4 = 2^2</math> 인 경우, <math>8 = 3^2 - 1</math>, <math>9 = 4*2 + 2 - 1</math>, <math>10 = 5*2 + 1 - 1</math>, <math>11 = 6*2 - 1</math>, <math>11 = 7 + 5 - 1</math>, <math>11 = 8 + 4 - 1</math>, <math>11 = 9 + 3 - 1</math>, <math>11 = 10 + 2 - 1</math>, <math>11 = 11 + 1 - 1</math>, <math>11 = 12 - 1</math>, <math>10 = 11 - 1</math>, ..., <math>0 = 1 - 0</math>.

== 증명 ==
이 정리의 증명에는 다음과 같은 [[보조정리]]<ref name="최창선"/>{{rp|65}}가 필요하다.

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

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

* <math>h_n = \omega^{b_k}a_k + ... + \omega^{b_0}a_0</math>

그러면 <math>h_n</math> 은 다음 성질을 만족한다.

* <math>g_n > 0</math> 이면 <math>h_n > 0</math> 이고 <math>h_n > h_{n+1}</math>이다.

전자는 자명하다. 후자의 경우 <math>b_0 = 0</math> 이면 분명하므로 <math>b_0</math>이 0보다 크다고 가정하면,

* <math>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</math>

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

* <math>h_{n+1} = \omega^{b_k}a_k + ... + \omega^{b_0}(a_0 - 1) + \omega^{b_0 - 1}n + ... + n</math>
* <math>< \omega^{b_k}a_k + ... + \omega^{b_0}(a_0 - 1) + \omega^{b_0} = h_n</math>

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

== 패리스의 정리 ==
=== 공식화 ===
패리스의 정리는 다음과 같이 공식화할 수 있다.<ref name="최창선"/>{{rp|69}} 증명은 굿스타인의 정리에서와 유사하게 할 수 있으나 약간 더 까다롭다.

* 초항이 자연수인 굿스타인 [[수열]]은 0으로 끝난다.

=== 증명불가능성 ===
이 정리는 굿스타인의 정리와 유사하게, 자연수에 관한 정리임에도 [[순서수]]의 이론을 도입하지 않으면 증명이 어렵다. 실제로 패리스와 [[로리 커비]](Laurie Kirby)는 이 정리에 대해서 다음 명제를 증명하였다.<ref name="최창선"/>{{rp|71}}

* 패리스의 정리가 성립하면 [[페아노 공리계|페아노 산술]]이 [[모형]]을 갖는다.

이에 따라서, 만약 패리스의 정리가 페아노 산술 내에서 증명이 된다면 페아노 산술이 모형을 갖는 것이 페아노 산술의 정리가 되어 [[괴델의 불완전성 정리]]에 모순이 된다. 따라서, 패리스의 정리는 통상적인 자연수 체계인 페아노 산술에서 증명불가능하다.

== 각주 ==
{{각주}}
* Kirby, L.; Paris, J. (1982), "[https://web.archive.org/web/20110825205826/http://reference.kfupm.edu.sa/content/a/c/accessible_independence_results_for_pean_59864.pdf Accessible independence results for Peano arithmetic]", Bulletin London Mathematical Society 14: 285–293.

{{위키데이터 속성 추적}}

[[분류:수학기초론 정리]]
[[분류:집합론]]
[[분류:순서수]]