定 理 13.1 自然数 (N, ?) は整列集合である. 証 明 いつも通り, [n] = {1, 2, . . . , n} と書くことにする. A ⊂ N を空でない 部分集合とする. このとき, A = A ∩ N = A ∩∪∞n=1 [n] = ∪∞n=1 A ∩ [n] と A ≠Φ から, A ∩ [n] ≠Φ を満たす n ∈ N が存在する. そこで, N の部分集合 A が A ∩ [n] ≠Φ を満たせば A は最小元をもつことを示せばよい. そのことを数学的帰納法で証明しよう. まず, n = 1 のときは A ∩ [1] ≠Φ か ら 1 ∈ A がわかる. 1 は自然数の中で最小であるから, 確かに A は最小元をも つ. 次に n ? 1 まで主張が正しいと仮定して, A ∩ [n + 1] ≠Φ とする. もし, A ∩ [n] ≠Φ であれば帰納法の仮定から A は最小元をもつ. A ∩ [n] = Φ であれ ば, A ∩ [n + 1] ≠Φ と合わせて n + 1 が A の最小元であることがわかる.■
