13.1 整列集合 順序集合 (X, ?) は, すべての空でない部分集合が最小元をもつとき, 整列集 合であるといい, そのような順序を整列順序という. 定義から整列集合は必ず全 順序集合であることに注意しよう. 実際, a, b ∈ X に対して集合 {a, b} は X の 空でない部分集合になるから, それは最小元をもつ. 最小元は a または b であ るが, それが a であれば a ? b となるし, それが b であれば b ? a となる. こ れは, 任意の a, b ∈ X が比較可能であることを意味し, X は全順序集合である ことがわかる. 定義から空でない整列集合 X それ自身は最小元 min X をもつ.
定 理 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 の最小元であることがわかる. (引用終り)
