초한 귀납법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →초한반복 |
|||
18번째 줄: | 18번째 줄: | ||
보다 형식적으로는, 초한반복 정리의 내용은 다음과 같다. |
보다 형식적으로는, 초한반복 정리의 내용은 다음과 같다. |
||
:모임 함수 <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>(0) = <b>G<sub>1</sub></b>(<math>\emptyset</math>) |
:*<b>F</b>(0) = <b>G<sub>1</sub></b>(<math>\emptyset</math>) |
||
:*모든 |
:*모든 서수 α에 대해, <b>F</b>(α+1) = <b>G<sub>2</sub></b>(<b>F</b>(α)) |
||
:*모든 |
:*모든 0이 아닌 극한서수 α에 대해, <b>F</b>(α) = <b>G<sub>3</sub></b>(<b>F</b><math>\upharpoonright</math>α). |
||
==선택공리와의 관계== |
==선택공리와의 관계== |
2007년 4월 30일 (월) 16:37 판
초한귀납법(transfinite induction)은 수학적 귀납법을 서수나 기수들의 집합을 비롯한 커다란 정렬순서집합에 적용시킬 수 있도록 확장한 것이다.
초한귀납법
초한귀납법은 특정한 성질 P(α)가 모든 서수 α에 대해 성립함을 증명하기 위한 방법이다. 증명은 대체로 다음의 세 단계로 이루어진다:
- P(0)이 성립함을 증명한다.
- 임의의 따름서수 β+1에 대해, P(β)를 가정하고 P(β+1)을 증명한다. (필요할 경우 β보다 작은 모든 γ에 대해 P(γ)가 성립한다는 것도 가정해도 된다.)
- 임의의 극한서수 λ에 대해, λ보다 작은 모든 γ에 대해 P(γ)가 성립한다는 것을 가정하고 P(λ)를 증명한다.
즉, 위의 세 가지 성질이 성립할 경우 P(α)는 모든 서수 α에 대해 참이다. 여기서 수학적 귀납법과의 유일한 차이는, 서수는 계속 1을 더해가는 방법으로는 전부 만들어낼 수 없기에 극한서수의 경우를 따로 고려해준다는 것 뿐이다. 위의 내용을 잘 보면 알 수 있듯이 따름서수의 경우와 극한서수의 경우에서 증명할 내용은 사실상 동일하다.
초한반복
초한반복(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α).
선택공리와의 관계
초한귀납법(혹은 초한반복)이 선택공리를 필요로 한다는 오해가 널리 퍼져 있으나, 이는 사실과 다르다. 초한귀납법은 임의의 정렬순서집합에 대해 적용될 수 있기 때문이다. 그러나 초한귀납법을 사용하기 위해서는 많은 경우 선택공리를 이용해 집합에 정렬순서를 부여할 필요가 있다.