초한 귀납법

집합론에서, 초한 귀납법(超限歸納法, 영어: transfinite induction)은 수학적 귀납법을 순서수나 기수를 비롯한 정렬 집합으로 확장한 것이다.

정의

$P$가 순서수에 대한 성질이고, 다음이 임의의 순서수 $\alpha$에 대해 성립한다고 하자.

• 만약 임의의 순서수 $\beta <\alpha$에 대하여 $P(\beta )$라면, $P(\alpha )$이다.

초한 귀납법의 원리에 따르면, 이때 다음이 성립한다.

• 임의의 순서수에 대해 $P$이다.

즉, 만약 어떤 성질이 모든 순서수에 대하여 성립한다는 것을 증명하려면, 임의의 순서수의 실례와 그보다 작은 모든 순서수의 실례 사이의 함의 관계를 증명하면 된다. 이 함의 관계는 보통 순서수의 유형에 따라 경우를 나누어 증명한다. 구체적으로, 다음과 같다.

1. $P(0)$을 증명한다.
2. 임의의 따름 순서수 $\beta +1$에 대해, $P(\beta )$이면 $P(\beta +1)$임을 증명한다.
3. 임의의 극한 순서수 $\alpha$에 대해, 모든 $\beta <\alpha$가 $P(\beta )$이면 $P(\alpha )$임을 증명한다.

물론 기술적으로 가능한 경우, 세번째 경우를 임의의 순서수에 대해 증명하는 것으로 전체 증명을 대신할 수도 있다.

초한 귀납법을 정렬 집합에 적용시킬 때는 선택 공리가 필요하지 않다. 그러나 초한 귀납법이 응용되는 여러 경우, 정렬 정리를 사용하여 집합에 정렬 순서를 부여하여야 하는데, 이 경우 선택 공리가 필요하게 된다.

초한 귀납법은 임의의 정초 관계 위에서도 사용할 수 있다.

초한 재귀

초한 재귀(超限再歸, 영어: transfinite recursion)는 초한 귀납법과 유사한, 모든 순서수 위의 열을 구성하는 방법이다. 임의의 순서수에 대응하는 항을, 그 이전 순서수에 대한 항 또는 그보다 작은 모든 순서수에 대한 항들로부터 결정하는 규칙을 통해 모든 순서수 위의 열을 유일하게 구성한다. 구체적으로, $F(\alpha )$를 $\varnothing$이나 $F(\alpha -1)$이나 $(F(\beta ))_{\beta <\alpha }$로부터 결정하는 규칙을 정하면, 열 $(F(\alpha ))_{\alpha \in {\text{Ord}}}$이 정의된다.

집합론에서, 순서수 위의 초한 재귀 정리(영어: transfinite recursion theorem)는 다음과 같다. 모임 함수 $G\colon V\to V$가 주어지면, 다음을 만족하는 초한 수열 $F\colon {\text{Ord}}\to V$가 유일하게 존재한다.

$F(\alpha )=G(F|_{\alpha })\quad \forall \alpha \in {\text{Ord}}$

여기서 $V$는 모든 집합의 모임, $F|_{\alpha }$는 $F$의 $\alpha$로의 제한이다. 구체적으로 $F$는 다음과 같다.

$F=\bigcup \left\{\exists \gamma \in {\text{Ord}}\colon f\colon \gamma \to V,\forall \alpha <\gamma \colon f(\alpha )=G(f{|}_{\alpha })\right\}$

초한 재귀 역시 임의의 정초 관계 위에서도 사용할 수 있다.

같이 보기

• 정초 관계

외부 링크

• “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” (영어).