"초한귀납법"의 두 판 사이의 차이

54 바이트 제거됨 ,  4년 전
편집 요약 없음
(봇: 인용 틀 변수 이름 수정)
[[집합론]]에서, '''초한 귀납법'''(超限歸納法, {{llang|en|transfinite induction}})은 [[수학적 귀납법]]을 [[자연수]]뿐만이 아니라 일반적인 [[정렬 집합]]에 적용할 수 있도록 확장한 것이다. 모든 [[순서수]]나 [[기수 (수학)|기수]] 대한비롯한 명제를[[정렬 증명할집합]]으로 확장한 사용된다것이다.
 
== 정의 ==
<math>P</math>를 [[순서수]]에 대한 성질이고, 다음이 임의의 순서수 <math>\alpha</math>에 대해 성립한다고 하자.
'''초한 귀납법'''은 특정한 성질 P(α)가 모든 [[순서수]] α에 대해 성립함을 증명하기 위한 방법이다. 초한귀납법은 다음을 증명한다.
* 만약 임의의 순서수 <math>\beta<\alpha</math>에 대하여 <math>P(\beta)</math>라면, <math>P(\alpha)</math>이다.
'''초한 귀납법'''의 원리에 따르면, 이때 다음이 성립한다.
* 임의의 순서수에 대해 <math>P</math>이다.
즉, 만약 어떤 성질이 모든 순서수에 대하여 성립한다는 것을 증명하려면, 임의의 순서수의 실례와 그보다 작은 모든 순서수의 실례 사이의 함의 관계를 증명하면 된다. 이 함의 관계는 보통 순서수의 유형에 따라 경우를 나누어 증명한다. 구체적으로, 다음과 같다.
* <math>P(0)이 성립함을</math>을 증명한다.
* <math>P(\beta)</math>이면 <math>P(\beta+1)</math>임을 임의의 [[따름 순서수]] <math>\beta+1</math>에 대해 증명한다.
* <math>\forall\beta<\alpha\colon P(\beta)</math>이면 <math>P(\alpha)</math>임을 임의의 [[극한 순서수]] <math>\alpha</math>에 대해 증명한다.
물론 기술적으로 가능한 경우, 세번째 경우를 임의의 순서수에 대해 증명하는 것으로 전체 증명을 대신할 수도 있다.
 
초한 귀납법을 [[정렬 집합]]에 적용시킬 때는 [[선택 공리]]가 필요하지 않다. 그러나 초한 귀납법이 응용되는 여러 경우, [[정렬 정리]]를 사용하여 집합에 정렬 순서를 부여하여야 하는데, 이 경우 [[선택 공리]]가 필요하게 된다.
* 임의의 [[순서수]] α에 대해, α보다 작은 모든 γ에 대해 P(γ)가 성립한다면 P(α)라는 것을 증명한다.
 
초한 귀납법은 임의의 [[정초 관계]] 위에서도 사용할 수 있다.
보통 이 증명 과정은 다음의 세 단계로 나뉜다.
 
== 초한 반복재귀 ==
* P(0)이 성립함을 증명한다.
'''초한 재귀'''(超限再歸, {{llang|en|transfinite recursion}})는 초한 귀납법과 유사한, 모든 순서수 위의 열을 구성하는 방법이다. 임의의 순서수에 대응하는 항을, 그 이전 순서수에 대한 항 또는 그보다 작은 모든 순서수에 대한 항들로부터 결정하는 규칙을 통해 모든 순서수 위의 열을 유일하게 구성한다. 구체적으로, <math>F(\alpha)</math>를 <math>\varnothing</math>이나 <math>F(\alpha-1)</math>이나 <math>(F(\beta))_{\beta<\alpha}</math>로부터 결정하는 규칙을 정하면, 열 <math>(F(\alpha))_{\alpha\in\text{Ord}}</math>이 정의된다.
* 임의의 [[따름순서수]] β+1에 대해, P(β)를 가정하고(혹은 β 이하의 모든 γ에 대해 P(γ)를 가정하고) P(β+1)을 증명한다.
* 임의의 [[극한순서수]] λ에 대해, λ보다 작은 모든 γ에 대해 P(γ)를 가정하고 P(λ)를 증명한다.
 
집합론에서, 순서수 위의 '''초한 재귀 정리'''({{llang|en|transfinite recursion theorem}})는 다음과 같다. [[모임 (집합론)|모임]] 함수 <math>G\colon V\to V</math>가 주어지면, 다음을 만족하는 초한 수열 <math>F\colon\text{Ord}\to V</math>가 유일하게 존재한다.
즉, 위의 세 가지 성질이 성립할 경우 P(α)는 모든 순서수 α에 대해 참이다. 이 과정에서 [[수학적 귀납법]]과 차이가 되는 부분은 극한순서수인데, 따름순서수는 P(β)를 가정하고 P(β+1)을 증명하여도 되지만 극한순서수는 계속 1을 더해가는 방법으로는 전부 만들어낼 수 없기에 극한순서수의 경우를 따로 고려해준다는 것뿐이다.
:<math>F(\alpha)=G(F|_\alpha)\quad\forall\alpha\in\text{Ord}</math>
만약 따름순서수의 경우에도 β보다 작은 모든 γ에 대해 P(γ)가 성립한다는 것을 가정하는 경우, 따름순서수와 극한순서수의 조건은 동일하다. 다만 일반적으로 두 경우 증명 방법이 크게 달라지기 때문에 이를 구분하는 것이 편리한 것 뿐이다.
여기서 <math>V</math>는 모든 집합의 모임, <math>F|_\alpha</math>는 <math>F</math>의 <math>\alpha</math>로의 [[함수의 제한|제한]]이다. 구체적으로 <math>F</math>는 다음과 같다.
:<math>F=\bigcup\left\{\exists\gamma\in\text{Ord}\colon f\colon\gamma\to V,\forall\alpha<\gamma\colon f(\alpha)=G(f{|}_\alpha)\right\}</math>
 
초한 재귀 역시 임의의 [[정초 관계]] 위에서도 사용할 수 있다.
== 초한 반복 ==
'''초한 반복'''(超限反復, {{llang|en|transfinite recursion}})은 집합들의 열 A<sub>α</sub>를 모든 순서수 α에 대해 정의하기 위해 초한귀납법과 유사한 과정을 사용한다. 구체적으로는 다음의 세 단계가 필요하다.
*A<sub>0</sub>을 정의한다.
*임의의 따름순서수 β+1에 대해, A<sub>β</sub>가 주어져 있을 때 A<sub>β+1</sub>를 정의하는 방법을 규정한다. (필요할 경우 β보다 작은 모든 γ에 대해 A<sub>γ</sub>에도 의존하도록 정의해도 된다.)
*임의의 극한순서수 λ에 대해, λ보다 작은 모든 γ에 대해 A<sub>γ</sub>들이 주어져 있을 때 A<sub>λ</sub>을 정의하는 방법을 규정한다.
 
== 같이 보기 ==
보다 형식적으로는, 초한 반복 정리의 내용은 다음과 같다.
* [[정초 관계]]
:모임 함수 '''G<sub>1</sub>''', '''G<sub>2</sub>''', '''G<sub>3</sub>'''에 대해, 다음을 만족하는 초한 수열 '''F'''가 유일하게 존재한다:
:*'''F'''의 정의역은 모든 순서수의 모임
:*'''F'''(0) = '''G<sub>1</sub>'''(<math>\emptyset</math>)
:*모든 순서수 α에 대해, '''F'''(α+1) = '''G<sub>2</sub>'''('''F'''(α))
:*모든 0이 아닌 극한순서수 α에 대해, '''F'''(α) = '''G<sub>3</sub>'''('''F'''<math>\upharpoonright</math>α).
 
==선택 공리와의 관계==
초한 귀납법을 [[정렬 집합]]에 적용시킬 때는 [[선택 공리]]가 필요하지 않다. 그러나 초한 귀납법이 응용되는 여러 경우, [[정렬 정리]]를 사용하여 집합에 정렬 순서를 부여하여야 하는데, 이 경우 [[선택 공리]]가 필요하게 된다.
 
== 바깥 고리 ==