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

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

 

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

$(X,\;\leq)$가 정렬집합이고 $P$가 명제함수라고 하자. 이때, 다음 명제가 성립한다. $$\left(\forall x\in X,\;\left(\forall y\in X\;with\;y<x,\;P(y)\right)\Rightarrow P(x)\right)\Rightarrow\left(\forall x\in X,\;P(x)\right)$$

 

Proof:

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

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

이때, 귀납법을 위해 $S\neq\varnothing$을 가정하자. 그러면 $S\subseteq X$이므로 $S$의 최소원소 $c\in S$가 존재한다. 이때, $0\notin S$이므로 $0<c$가 성립함을 알 수 있다. 즉, $c$보다 작은 $X$의 원소가 존재한다. 이때, $\forall x\in X,\;\left(\forall y\in X\;with\;y<x,\;P(y)\right)\Rightarrow P(x)$가 참이라는 것으로부터 $\forall x\in X,\;\neg P(x)\Rightarrow\left(\exists y\in X\;s.t.\;y<x\land\neg P(y)\right)$ 역시 성립함은 자명하다. 따라서 $x<c$이면서 동시에 $P(x)$가 거짓인 $x\in X$가 존재한다. 이때, $P(x)$가 거짓이므로 $x\in S$가 성립하게 되며 이는 $c$가 $S$의 최소원소임에 모순이다. 따라서 $S=\varnothing$이며, 따라서 $\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$ 역시 극한 서수임에 주의하라. 또한, 극한 서수가 아닌 서수는 따름 서수라고 한다. 또한, 위의 세 가지 조건을 만족한다면 초한귀납법을 사용하기 위한 조건을 만족한다는 것의 증명은 간단하니 한 번쯤은 직접 해보는 것을 추천한다.