집합론, 그 열네 번째 이야기 | 초한 귀납법 ( Transfinite Induction )

초한 귀납법(Transfinite Induction)은 자연수에서의 수학적 귀납법을 정렬 집합으로 확장한 것을 말한다. 초한 귀납법은 다음과 같은 명제이다.

 

Theorem 1. 초한 귀납법 ( Transfinite Induction )

$(X,\le )$가 정렬집합이고 $P$가 명제함수라고 하자. 이때, 다음 명제가 성립한다. $$(\mathrm{\forall }x\in X,(\mathrm{\forall }y\in Xwithy<x,P(y))\Rightarrow P(x))\Rightarrow (\mathrm{\forall }x\in X,P(x))$$

 

Proof:

증명의 편의를 위해 $X$의 최소원소를 $0$이라고 하자. 그러면 $\mathrm{\forall }x\in X,(\mathrm{\forall }y\in Xwithy<x,P(y))\Rightarrow P(x)$로부터 $t\Rightarrow P(0)$이 성립함을 알 수 있으며, 이는 $\mathrm{\neg }t\vee P(0)$와 동치이므로 $P(0)$가 참임을 알 수 있다. 이제 집합 $X$의 부분집합 $S$를 다음과 같이 정의하자.

$$S=\{x\in X|\mathrm{\neg }P(x)\}$$

이때, 귀납법을 위해 $S\ne \varnothing$을 가정하자. 그러면 $S\subseteq X$이므로 $S$의 최소원소 $c\in S$가 존재한다. 이때, $0\notin S$이므로 $0<c$가 성립함을 알 수 있다. 즉, $c$보다 작은 $X$의 원소가 존재한다. 이때, $\mathrm{\forall }x\in X,(\mathrm{\forall }y\in Xwithy<x,P(y))\Rightarrow P(x)$가 참이라는 것으로부터 $\mathrm{\forall }x\in X,\mathrm{\neg }P(x)\Rightarrow (\mathrm{\exists }y\in Xs.t.y<x\wedge \mathrm{\neg }P(y))$ 역시 성립함은 자명하다. 따라서 $x<c$이면서 동시에 $P(x)$가 거짓인 $x\in X$가 존재한다. 이때, $P(x)$가 거짓이므로 $x\in S$가 성립하게 되며 이는 $c$가 $S$의 최소원소임에 모순이다. 따라서 $S=\varnothing$이며, 따라서 $\mathrm{\forall }x\in X,P(x)$가 성립한다.

 

이때, 이를 모든 서수에 대해 확장이 가능하며, 이 경우, 다음과 같은 형태로 바꿀 수 있다.

 

다음 세 가지 조건을 만족한다면 모든 서수 $\alpha$에 대해 $P(\alpha )$가 성립한다.

1. $P(0)$이 성립한다.

2. 모든 서수 $\beta$에 대해 $P(\beta )\Rightarrow P(\beta +1)$이다.

3. 모든 극한 서수 $\alpha$에 대해 모든 $\beta <\alpha$가 $P(\beta )$이면 $P(\alpha )$이다.

이때, $\alpha$가 극한 서수라는 것은 $\alpha =S(\beta )=\beta \cup \{\beta \}$가 성립하는 서수 $\beta$가 없음을 의미한다. 이때, $0$ 역시 극한 서수임에 주의하라. 또한, 극한 서수가 아닌 서수는 따름 서수라고 한다. 또한, 위의 세 가지 조건을 만족한다면 초한귀납법을 사용하기 위한 조건을 만족한다는 것의 증명은 간단하니 한 번쯤은 직접 해보는 것을 추천한다.