초한 귀납법: 두 판 사이의 차이
Osteologia (토론 | 기여) 편집 요약 없음 |
Osteologia (토론 | 기여) 편집 요약 없음 |
||
1번째 줄: | 1번째 줄: | ||
[[집합론]]에서, ''' |
[[집합론]]에서, '''초한 귀납법'''(超限歸納法, {{llang|en|transfinite induction}})은 [[수학적 귀납법]]을 [[자연수]]뿐만이 아니라 일반적인 [[정렬 집합]]에 적용할 수 있도록 확장한 것이다. 모든 [[순서수]]나 [[기수 (수학)|기수]]에 대한 명제를 증명할 때 사용된다. |
||
== 정의 == |
== 정의 == |
||
''' |
'''초한 귀납법'''은 특정한 성질 P(α)가 모든 [[순서수]] α에 대해 성립함을 증명하기 위한 방법이다. 초한귀납법은 다음을 증명한다. |
||
* 임의의 [[순서수]] α에 대해, α보다 작은 모든 γ에 대해 P(γ)가 성립한다면 P(α)라는 것을 증명한다. |
* 임의의 [[순서수]] α에 대해, α보다 작은 모든 γ에 대해 P(γ)가 성립한다면 P(α)라는 것을 증명한다. |
||
12번째 줄: | 12번째 줄: | ||
* 임의의 [[극한순서수]] λ에 대해, λ보다 작은 모든 γ에 대해 P(γ)를 가정하고 P(λ)를 증명한다. |
* 임의의 [[극한순서수]] λ에 대해, λ보다 작은 모든 γ에 대해 P(γ)를 가정하고 P(λ)를 증명한다. |
||
즉, 위의 세 가지 성질이 성립할 경우 P(α)는 모든 순서수 α에 대해 참이다. 이 과정에서 수학적 |
즉, 위의 세 가지 성질이 성립할 경우 P(α)는 모든 순서수 α에 대해 참이다. 이 과정에서 [[수학적 귀납법]]과 차이가 되는 부분은 극한순서수인데, 따름순서수는 P(β)를 가정하고 P(β+1)을 증명하여도 되지만 극한순서수는 계속 1을 더해가는 방법으로는 전부 만들어낼 수 없기에 극한순서수의 경우를 따로 고려해준다는 것뿐이다. |
||
만약 따름순서수의 경우에도 β보다 작은 모든 γ에 대해 P(γ)가 성립한다는 것을 가정하는 경우, 따름순서수와 극한순서수의 조건은 동일하다. 다만 일반적으로 두 경우 증명 방법이 크게 달라지기 때문에 이를 구분하는 것이 편리한 것 뿐이다. |
만약 따름순서수의 경우에도 β보다 작은 모든 γ에 대해 P(γ)가 성립한다는 것을 가정하는 경우, 따름순서수와 극한순서수의 조건은 동일하다. 다만 일반적으로 두 경우 증명 방법이 크게 달라지기 때문에 이를 구분하는 것이 편리한 것 뿐이다. |
||
== |
== 초한 반복 == |
||
''' |
'''초한 반복'''(超限反復, {{llang|en|transfinite recursion}})은 집합들의 열 A<sub>α</sub>를 모든 순서수 α에 대해 정의하기 위해 초한귀납법과 유사한 과정을 사용한다. 구체적으로는 다음의 세 단계가 필요하다. |
||
*A<sub>0</sub>을 정의한다. |
*A<sub>0</sub>을 정의한다. |
||
*임의의 따름순서수 β+1에 대해, A<sub>β</sub>가 주어져 있을 때 A<sub>β+1</sub>를 정의하는 방법을 규정한다. (필요할 경우 β보다 작은 모든 γ에 대해 A<sub>γ</sub>에도 의존하도록 정의해도 된다.) |
*임의의 따름순서수 β+1에 대해, A<sub>β</sub>가 주어져 있을 때 A<sub>β+1</sub>를 정의하는 방법을 규정한다. (필요할 경우 β보다 작은 모든 γ에 대해 A<sub>γ</sub>에도 의존하도록 정의해도 된다.) |
||
*임의의 극한순서수 λ에 대해, λ보다 작은 모든 γ에 대해 A<sub>γ</sub>들이 주어져 있을 때 A<sub>λ</sub>을 정의하는 방법을 규정한다. |
*임의의 극한순서수 λ에 대해, λ보다 작은 모든 γ에 대해 A<sub>γ</sub>들이 주어져 있을 때 A<sub>λ</sub>을 정의하는 방법을 규정한다. |
||
보다 형식적으로는, |
보다 형식적으로는, 초한 반복 정리의 내용은 다음과 같다. |
||
:모임 함수 <b>G<sub>1</sub></b>, <b>G<sub>2</sub></b>, <b>G<sub>3</sub></b>에 대해, 다음을 만족하는 초한 수열 <b>F</b>가 유일하게 존재한다: |
:모임 함수 <b>G<sub>1</sub></b>, <b>G<sub>2</sub></b>, <b>G<sub>3</sub></b>에 대해, 다음을 만족하는 초한 수열 <b>F</b>가 유일하게 존재한다: |
||
:*<b>F</b>의 정의역은 모든 순서수의 모임 |
:*<b>F</b>의 정의역은 모든 순서수의 모임 |
||
31번째 줄: | 31번째 줄: | ||
초한귀납법을 [[정렬 집합]]에 적용시킬 때는 [[선택 공리]]가 필요하지 않다. 그러나 초한귀납법이 응용되는 여러 경우, [[정렬 정리]]를 사용하여 집합에 정렬 순서를 부여하여야 하는데, 이 경우 [[선택 공리]]가 필요하게 된다. |
초한귀납법을 [[정렬 집합]]에 적용시킬 때는 [[선택 공리]]가 필요하지 않다. 그러나 초한귀납법이 응용되는 여러 경우, [[정렬 정리]]를 사용하여 집합에 정렬 순서를 부여하여야 하는데, 이 경우 [[선택 공리]]가 필요하게 된다. |
||
== 바깥 고리 == |
|||
⚫ | |||
* {{eom|title=Transfinite recursion}} |
|||
* {{매스월드|id=TransfiniteInduction|title=Transfinite induction}} |
|||
* {{웹 인용|url=http://jdh.hamkins.org/transfinite-recursion-as-a-fundamental-principle-in-set-theory/|제목=Transfinite recursion as a fundamental principle in set theory|이름=Joel David|성=Hamkins|날짜=2014-10-20|언어고리=en}} |
|||
⚫ | |||
[[분류:순서수]] |
[[분류:순서수]] |
||
[[분류:증명]] |
[[분류:증명]] |
2015년 1월 5일 (월) 03:40 판
집합론에서, 초한 귀납법(超限歸納法, 영어: transfinite induction)은 수학적 귀납법을 자연수뿐만이 아니라 일반적인 정렬 집합에 적용할 수 있도록 확장한 것이다. 모든 순서수나 기수에 대한 명제를 증명할 때 사용된다.
정의
초한 귀납법은 특정한 성질 P(α)가 모든 순서수 α에 대해 성립함을 증명하기 위한 방법이다. 초한귀납법은 다음을 증명한다.
- 임의의 순서수 α에 대해, α보다 작은 모든 γ에 대해 P(γ)가 성립한다면 P(α)라는 것을 증명한다.
보통 이 증명 과정은 다음의 세 단계로 나뉜다.
- P(0)이 성립함을 증명한다.
- 임의의 따름순서수 β+1에 대해, P(β)를 가정하고(혹은 β 이하의 모든 γ에 대해 P(γ)를 가정하고) P(β+1)을 증명한다.
- 임의의 극한순서수 λ에 대해, λ보다 작은 모든 γ에 대해 P(γ)를 가정하고 P(λ)를 증명한다.
즉, 위의 세 가지 성질이 성립할 경우 P(α)는 모든 순서수 α에 대해 참이다. 이 과정에서 수학적 귀납법과 차이가 되는 부분은 극한순서수인데, 따름순서수는 P(β)를 가정하고 P(β+1)을 증명하여도 되지만 극한순서수는 계속 1을 더해가는 방법으로는 전부 만들어낼 수 없기에 극한순서수의 경우를 따로 고려해준다는 것뿐이다. 만약 따름순서수의 경우에도 β보다 작은 모든 γ에 대해 P(γ)가 성립한다는 것을 가정하는 경우, 따름순서수와 극한순서수의 조건은 동일하다. 다만 일반적으로 두 경우 증명 방법이 크게 달라지기 때문에 이를 구분하는 것이 편리한 것 뿐이다.
초한 반복
초한 반복(超限反復, 영어: transfinite recursion)은 집합들의 열 Aα를 모든 순서수 α에 대해 정의하기 위해 초한귀납법과 유사한 과정을 사용한다. 구체적으로는 다음의 세 단계가 필요하다.
- A0을 정의한다.
- 임의의 따름순서수 β+1에 대해, Aβ가 주어져 있을 때 Aβ+1를 정의하는 방법을 규정한다. (필요할 경우 β보다 작은 모든 γ에 대해 Aγ에도 의존하도록 정의해도 된다.)
- 임의의 극한순서수 λ에 대해, λ보다 작은 모든 γ에 대해 Aγ들이 주어져 있을 때 Aλ을 정의하는 방법을 규정한다.
보다 형식적으로는, 초한 반복 정리의 내용은 다음과 같다.
- 모임 함수 G1, G2, G3에 대해, 다음을 만족하는 초한 수열 F가 유일하게 존재한다:
- F의 정의역은 모든 순서수의 모임
- F(0) = G1()
- 모든 순서수 α에 대해, F(α+1) = G2(F(α))
- 모든 0이 아닌 극한순서수 α에 대해, F(α) = G3(Fα).
선택 공리와의 관계
초한귀납법을 정렬 집합에 적용시킬 때는 선택 공리가 필요하지 않다. 그러나 초한귀납법이 응용되는 여러 경우, 정렬 정리를 사용하여 집합에 정렬 순서를 부여하여야 하는데, 이 경우 선택 공리가 필요하게 된다.
바깥 고리
- “Transfinite recursion”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Transfinite induction”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Hamkins, Joel David (2014년 10월 20일). “Transfinite recursion as a fundamental principle in set theory”.