자연수의 집합 N에 대한 induction을 사용할 때, 0이 아닌 모든 자연수는 limit ordinal이 아니라는 사실을 이용합니다.

그런데 0이 아닌 모든 자연수는 limit ordinal이 아니라는 것 역시 당연한 것은 아닙니다. 이 명제 역시 증명해야 하는 겁니다. 이건 induction을 사용해서 증명할 수 없습니다. 왜냐하면, 이 명제를 증명하기 전에는 우리는 아직 0이 아닌 모든 자연수가 limit ordinal이라는 것을 모르기 때문입니다. (최범준씨, 수업끝날 때 최범준씨께 말한 건 제가 잘못 말한거예요. 이건 induction으로 증명할 수 없어요.)

증명은 의외로 간단합니다. 개략적으로 설명하겠습니다.

1) 우선 모든 0이 아닌 limit ordinal은 inductive set(p.12 참조)이 된다는 사실을 증명할 수 있습니다. (직접해보세요.)

2) 또한 자연수는 모든 inductive set의 교집합이라는 사실을 이용해야 합니다.(p.12 문제1.4.13)

이제 증명을 하기 위해 어떤 0이 아닌 자연수 n이 limit ordinal이라 가정해봅니다. 그러면 1)에 의해서 n은 inductive set입니다. 그런데 2)에 의해서 자연수 전체의 집합 N은 n의 부분집합이 됩니다. 여기서 정리 3.1.4(c)를 이용하면 N은 n의 원소가 됩니다. 우리는 이미 n이 N의 원소라는 것을 알고 있었으므로 이는 모순을 일으킨 겁니다.

그러므로 모든 0이 아닌 자연수는 limit ordinal 이 아니라는 것을 알 수 있습니다.