초한 귀납법

집합론에서, 초한귀납법(超限歸納法, 영어: transfinite induction)은 수학적 귀납법을 자연수뿐만이 아니라 일반적인 정렬집합에 적용할 수 있도록 확장한 것이다. 모든 순서수나 기수에 대한 명제를 증명할 때 사용된다.

정의

초한귀납법은 특정한 성질 P(α)가 모든 순서수 α에 대해 성립함을 증명하기 위한 방법이다. 초한귀납법은 다음을 증명한다.

• 임의의 순서수 α에 대해, α보다 작은 모든 γ에 대해 P(γ)가 성립한다면 P(α)라는 것을 증명한다.

보통 이 증명 과정은 다음의 세 단계로 나뉜다.

• P(0)이 성립함을 증명한다.
• 임의의 따름순서수 β+1에 대해, P(β)를 가정하고(혹은 β 이하의 모든 γ에 대해 P(γ)를 가정하고) P(β+1)을 증명한다.
• 임의의 극한순서수 λ에 대해, λ보다 작은 모든 γ에 대해 P(γ)를 가정하고 P(λ)를 증명한다.

즉, 위의 세 가지 성질이 성립할 경우 P(α)는 모든 순서수 α에 대해 참이다. 이 과정에서 수학적 귀납법과 차이가 되는 부분은 극한순서수인데, 따름순서수는 P(β)를 가정하고 P(β+1)을 증명하여도 되지만 극한순서수는 계속 1을 더해가는 방법으로는 전부 만들어낼 수 없기에 극한순서수의 경우를 따로 고려해준다는 것뿐이다. 만약 따름순서수의 경우에도 β보다 작은 모든 γ에 대해 P(γ)가 성립한다는 것을 가정하는 경우, 따름순서수와 극한순서수의 조건은 동일하다. 다만 일반적으로 두 경우 증명 방법이 크게 달라지기 때문에 이를 구분하는 것이 편리한 것 뿐이다.

초한반복

초한반복(transfinite recursion)은 집합들의 열 A_α를 모든 순서수 α에 대해 정의하기 위해 초한귀납법과 유사한 과정을 사용한다. 구체적으로는 다음의 세 단계가 필요하다.

• A₀을 정의한다.
• 임의의 따름순서수 β+1에 대해, A_β가 주어져 있을 때 A_β+1를 정의하는 방법을 규정한다. (필요할 경우 β보다 작은 모든 γ에 대해 A_γ에도 의존하도록 정의해도 된다.)
• 임의의 극한순서수 λ에 대해, λ보다 작은 모든 γ에 대해 A_γ들이 주어져 있을 때 A_λ을 정의하는 방법을 규정한다.

보다 형식적으로는, 초한반복 정리의 내용은 다음과 같다.

모임 함수 G₁, G₂, G₃에 대해, 다음을 만족하는 초한 수열 F가 유일하게 존재한다:

• F의 정의역은 모든 순서수의 모임
• F(0) = G₁($\emptyset$)
• 모든 순서수 α에 대해, F(α+1) = G₂(F(α))
• 모든 0이 아닌 극한순서수 α에 대해, F(α) = G₃(F$\upharpoonright$α).

선택공리와의 관계

초한귀납법(혹은 초한반복)이 선택공리를 필요로 한다는 오해가 널리 퍼져 있으나, 이는 사실과 다르다. 초한귀납법은 임의의 정렬집합에 대해 적용될 수 있기 때문이다. 그러나 초한귀납법을 사용하기 위해서는 많은 경우 선택공리를 이용해 집합에 정렬순서를 부여할 필요가 있다.