以下, 断らない限り, 順序集合の順序は で 表す. つぎ の性質を 持つ順序集合 W を整列集合[well-ordered set], その順序を整列順序[well-order] という:
∅ =A⊂W ⇒ ∃minA
すなわち, 整列集合とは, 空でないど んな部分集合にも最小元(始まり, 最初の元) が あるような順序集合のことである. 自然数の集合 Nは 整列集合の典型的な例で ある(演習 5.4). 以下は 定義から 直ちに 分かる:
• 整列集合のど んな部分順序集合も整列集合となる. 空集合も整列集合と見なせる.
演習 7.7 整列集合は全順序集合となることを示せ.
ヒント x, y∈X に 対し て,{x, y} ⊂X を 考えよ.
整列集合 W と a ∈ W に 対し て, つぎ のように 定義され る部分集合 W(a)をa によるW の(始)切片[initial segment]とい う:
W(a) ={x∈W |x < a} 特に, a= minW のとき W(a) =∅である.
全順序集合X において,a < b となる X の元に対し て,a < x < bとなる X の 元が 存在し ないとき,aは bの直前[predecessor]の元, bは a の直後[successor] の 元と呼ぶ.
整列集合 W の切片に 関し て, 以下の基本的な性質が 成り立つ: (1) ∀a∈W, supW(a) =a または supW(a)は aの直前の元 (2) W(a)⊂W(b)⇔ab
(3) ∀a < b∈W, W(b)(a) = W(a)
演習 7.8 上記の切片に 関する基本的性質(1)–(3)を証明せよ.
命題 7.1 整列集合の間の順序同型写像 f :W →W′ に対し て, つぎ が 成り立つこ とを示せ:
∀a∈W, f(W(a)) =W′(f(a)) このとき, W(a)≃W′(f(a))となる.
演習 7.9 命題7.1 を証明せよ.
補題 7.2 整列集合 W においては,つぎ の条件を満たすA⊂W は W 自身に限る: a∈W, W(a)⊂A ⇒a ∈A
証明 A=W とすると,W \A=∅. ∴∃a= min(W \A)
このとき,W(a)⊂Aとなり,条件よりa∈A—矛盾 注意: 補題の条件は minW ∈Aとなることも含んでいる.
整列集合の代表的にな 例である Nには, (数学的)帰納法が あり, n ∈ Nに 関す る命題を 証明するのに 非常に 有用な 道具となっている. 整列集合 W に 対し ては, これに 対応する超限帰納法[transfinite induction]が ある.
定理 7.3 (超限帰納法) 整列集合 W の元 x ∈W に 関する条件 P(x)が 与えられ ているとき, 以下を満たせば, すべての x∈W に 対し て,P(x)が 成立する:
(∗)∀x < a, P(x)が 成立⇒P(a)が 成立
証明 A={x∈W |P(x)}とおけば, (∗)は “W(a)⊂A⇒a∈A”となる
上の補題より, A=W,すなわ ち,∀x∈W,P(x)が 成立する
注意: 上の条件 (∗)は P(minW)が 成立することも含んでいる.
補題 7.4 (切片の特徴付け) 整列集合 W に おいて, A W が 切片になるために は,つぎ の条件を満たすことが 必要十分である:
x∈A, y∈W, y < x⇒y ∈A (i.e., ∀x∈A, W(x)⊂A)
証明の方針 切片W(a)が 上の条件を満たすのは明らか. 逆に,条件を満たすAW に 対し て,a= min(W\A)とおくとW(a)⊂A,A⊂W(a)を 背理法で 示す.
補題 7.5 整列集合 W の自己順序単射 f :W →W はつぎ の性質を持つ:
∀x∈W, xf(x)
証明の方針 M = {x ∈ W | f(x)< x} =∅ を 示せば よい. M =∅ と 仮定すると
∃a= minM. f が 順序単射であることを用いて,f(a)∈M を 示し て矛盾を 導く.
補題 7.6 整列集合 W において,つぎ が 成り立つ: (1) ∀a∈W, W ≃W(a)
(2) a=b∈W ⇒W(a)≃W(b)
証明の方針 (1)は,順序同型写像が 存在し たとし て, 補題7.5より矛盾を 出す. (2)は,a < bと 仮定し て(1)に 帰着.
定理 7.7 整列集合 W, W′ が 順序同型であれば, W から W′ への順序同型写像は 一意的に 決まる. 特に, W から W 自身への順序同型写像は 恒等写像に 限る.
証明 f, g:W →W′ を順序同型写像とすれば,
∀a∈W,W′(f(a))≃W(a)≃W′(g(a)) (演習7.1)
補題7.6(2)より,f(a) =g(a) ∴ f =g
補題 7.8 整列集合W, W′が 順序同型であれば, 任意の a∈W に対し て,W(a)≃ W′(a′)となる a′ ∈W′ が 一意的に 決まる.
証明 f :W →W′ を 順序同型写像とすれば,
W(a)≃W′(f(a)) (演習7.1) —これは a′の存在を 意味する さらにW(a)≃W′(a′)とすれば,
補題7.6(2)より,a′=f(a) —これはa′ の一意性を 意味する
つぎ の定理は 整列集合の比較定理と呼ばれ る:
定理 7.9 (整列集合の比較定理) 任意の整列集合 W,W′ に対し て,つぎ の 3つの 場合の うちいずれか 1 つだけが 成り立つ:
(1) W ≃W′
(2) ∃a′ ∈W′, W ≃W′(a′) (3) ∃a∈W, W(a)≃W′
証明の概略 補題7.6(1)を用いれば, 3つの場合のいずれの2つも両立し ないことが 示せる. 3 つの 場合のいずれか1 つが 成り立つことを 示すために, A⊂W,A′ ⊂W′ をつぎ のように 定義する:
A={x∈W | ∃x′ ∈W′, W(x)≃W′(x′)}, A′={x′ ∈W′| ∃x∈W, W(x)≃W′(x′)}.
補題 7.8 と 7.4 を 用いて, A, A′ は それぞ れ W, W′ に 等し いか, または それ らの 切片とな ることが 示せ る. このと き, つぎ の 4 つの場合が 考えられ る: (1) A=W, A′ =W′; (2)A=W, ∃a′ ∈W′, A′ =W′(a′); (3)A′ =W′, ∃a∈W, A=W(a);
(4)∃a∈W, A=W(a),∃a′ ∈W′, A′ =W′(a′). A≃A′ であれば, (1), (2), (3)の 場合には,対応する結論が 得られ, (4)の場合には 矛盾が あり,生じ 得ないことが 分か る. よって,A≃A′ を 示せば よい.
補題 7.8 に より, 写像 f : A → A′, g : A′ → Aで, ∀x ∈ A, W(x) ≃ W′(f(x))
∀x′ ∈ A′, W′(x′) ≃ W(g(x′))を 満た すものが 一意的に 得られ る. 補題 7.6(2) を 用いて, gf = idW, f g = idW′ が 示せ る. これ より, f は 全単射で f−1 = g. さ らに, x < y ∈ W と すれば, W(y) ≃ W(f(y)), x ∈ W(y)より, ∃x′ ∈ W(f(y)), W(x) =W(y)(x)≃W(f(y)(x′) =W(x′) (補題7.8). このとき, 補題7.6(2) より, f(x) =x′ となりf(x)< f(y). よって, f は 順序を 保つ. 同様に g=f−1も順序を 保つので,f は順序同型写像(演習7.2). 従って, A≃A′.