大学数学基礎解説

文献あり

整列集合の比較定理の証明

集合論,順序,整列集合の比較定理

227

はじめに

久しぶりの投稿で何を書こうか迷ったが, 私が個人的に好きな定理である整列集合の比較定理を証明する.
ある程度の集合論の知識と半順序集合についての理解があれば読み進めることができるようにした.
主にutidaを参考にして書いた.

実数全体の集合を $R$ , 有理数全体の集合を $Q$ , 整数全体の集合を $Z$ , 自然数全体の集合を $N$ とする.

半順序集合

詳しくは解説しないが簡単に定義や例などを挙げる.

半順序集合

集合 $X$ 上の二項関係 $ρ$ について反射律, 推移律, 反対称律の $3$ 条件を満たすものを順序関係といい, 対 $(X, ρ)$ を半順序集合という.

順序関係が明らかなときは省略して書くことがある.
例えば以下のように書く.
「半順序集合 $X$ について～」
この後解説する全順序集合, 整列集合についても同様.

通常の大小関係 $\leq$ により $R, Q, Z, N$ は半順序集合となる.

半順序部分集合

$(X, \leq)$ を半順序集合とし, $X$ の空でない部分集合を $A$ とする.
$A$ 上の二項関係 $\leq_{A}$ を次で定義すると $\leq_{A}$ は $A$ 上の順序関係になる.
$A$ の任意の元 $a, b$ に対して,
$a \leq_{A} b \Leftrightarrow a \leq b$
を満たす.

$(A, \leq_{A})$ を半順序部分集合という.

$(A, \leq_{A})$ を単に $(A, \leq)$ と書く.

全順序集合

$(X, \leq)$ を半順序集合とする.
$X$ に属す任意の元 $a, b$ について, $a \leq b$ または $b \leq a$ が成り立つとき $(X, \leq)$ を全順序集合という.

順序を保つ写像

$(X, \leq)$ と $(X^{'}, \leq^{'})$ を半順序集合とする.
写像 $f : X \to X^{'}$ が任意の $a, b \in X$ に対して $a \leq b$ ならば $f (a) \leq^{'} f (b)$ を満たすとき, 写像 $f$ は順序を保つ写像であるという.

順序を保つ写像同士の合成は順序を保つ

　証明

(X, \leq), (Y, \leq^{'}), (Z, \leq^{″})

を半順序集合とし,

f : X \to Y, g : Y \to Z

を順序を保つ写像とする. 合成写像

g \circ f : X \to Z

が順序を保つことを示そう.
任意の元

a, b \in X

に対して

f

は順序を保つ写像であるので

a \leq b \Rightarrow f (a) \leq^{'} f (b)

, さらに

g

は順序を保つ写像であるので

f (a) \leq^{'} f (b) \Rightarrow g (f (a)) \leq^{″} g (f (b))

である. 即ち, 任意の元

a, b \in X

に対して

a \leq b \Rightarrow (g \circ f) (a) \leq^{″} (g \circ f) (b)

が成り立つので合成写像

g \circ f

は順序を保つ写像である.

順序同型

$(X, \leq)$ と $(X^{'}, \leq^{'})$ を半順序集合とする.
全単射 $f : X \to X^{'}$ が存在して写像 $f$ 及びその逆写像 $f^{- 1}$ が順序を保つ写像であるとき, $(X, \leq)$ と $(X^{'}, \leq^{'})$ は順序同型であるといい, $(X, \leq) ≃ (X^{'}, \leq^{'})$ で表す.
また, このとき写像 $f$ を順序同型写像という.

順序同型について次が成り立つ.(下で出てくる集合と二項関係の対はすべて半順序集合である)
(1) $(X, \leq) ≃ (X, \leq)$ .
(2) $(X, \leq) ≃ (X^{'}, \leq^{'})$ ならば $(X^{'}, \leq^{'}) ≃ (X, \leq)$ .
(3) $(X, \leq) ≃ (X^{'}, \leq^{'})$ かつ $(X^{'}, \leq^{'}) ≃ (X^{″}, \leq^{″})$ ならば $(X, \leq) ≃ (X^{″}, \leq^{″})$ .

証明のヒント

恒等写像を用いる.
順序同型写像 $f : X \to X^{'}$ の逆写像 $f^{- 1} : X^{'} \to X$ を考える.
順序同型写像 $f : X \to X^{'}, g : X^{'} \to X^{″}$ の合成写像 $g \circ f$ を考える.

最小元・最大元

$(X, \leq)$ を半順序集合とし, $A$ を $X$ の空でない部分集合とする.
$x \in X$ が $A$ の最小元であるとは, $x$ が $A$ に属し $A$ に属する任意の元 $a$ に対して $x \leq a$ となることである.
このとき $A$ の最小元 $x$ を $x = min A$ と書く.
$y \in X$ が $A$ の最大元であるとは, $y$ が $A$ に属し $A$ に属する任意の元 $a$ に対して $a \leq y$ となることである.
このとき $A$ の最大元 $y$ を $y = max A$ と書く.

整列集合

定理の要である整列集合を定義する.

整列集合

$(X, \leq)$ を半順序集合とする.
$X$ の空でない部分集合が常に最小元を持つとき, 半順序集合 $(X, \leq)$ は整列集合であるという.

通常の大小関係 $\leq$ により $R, Q, Z, N$ は半順序集合となったが, このうち $R, Q, Z$ は整列集合でないが $N$ は整列集合である.

整列集合の部分集合は整列集合である.

$(X, \leq)$ を整列集合とし, $Y$ を $X$ の部分集合とし半順序部分集合 $(Y, \leq)$ を考える. $Y$ の空でない部分集合 $A$ は $X$ の空でない部分集合であるので最小元 $min A$ が存在する. つまり, 半順序部分集合 $(Y, \leq)$ は整列集合となる.

整列集合は全順序集合である.

$(X, \leq)$ を整列集合とする. $x, y \in X$ をとり, 集合 $A := {x, y}$ を作る. $A$ は空でない $X$ の部分集合であるため最小元を持つ. $A$ の最小元は $x$ または $y$ である. $x$ が $A$ の最小元であれば $x \leq y$ , $y$ が $A$ の最小元であれば $y \leq x$ である. $X$ に属する任意の元 $x, y$ について $x \leq y$ または $y \leq x$ が成り立つ. つまり $(X, \leq)$ は全順序集合である.

切片

$(X, \leq)$ を半順序集合とする.
$a, b \in X$ で $a \leq b$ かつ $a \neq b$ のとき $a < b$ と書くことにする.
$X$ の元 $a$ に対して
$X ⟨ a ⟩ = {x \in X ∣ x < a}$
を $X$ の $a$ による切片という.

整列集合の比較定理

整列集合の比較定理の証明に必要な定理を示していく.
補題の証明は冗長であるかもしれないができるだけ行間を埋めて書いた.

整列集合の比較定理

整列集合 $(X, \leq_{X}), (Y, \leq_{Y})$ について
(1) $(X, \leq_{X})$ と $(Y, \leq_{Y})$ が順序同型である.
(2) $(X, \leq_{X})$ が $(Y, \leq_{Y})$ のある切片と順序同型である.
(3) $(X, \leq_{X})$ のある切片が $(Y, \leq_{Y})$ と順序同型である.
のいずれか一つが成り立つ. (つまり, どの二つも同時には起こりえない.)

以下, 補題をいくつか示す.

$(X, \leq)$ を整列集合とする.
写像 $φ : X \to X$ が順序を保つ単射であるとき, 任意の元 $x \in X$ について $x \leq φ (x)$ が成り立つ.

$A = {x \in X ∣ φ (x) < x}$ とおく. これが空集合であることを示せばよい.
$A \neq \emptyset$ と仮定する. prop:seiretuから $A$ は整列集合で $A$ の最小元を $a$ とする.
$a \in A$ より $φ (a) \leq a$ かつ $φ (a) \neq a$ である. (つまり $φ (a) < a$ )
$φ$ は順序を保つ単射であるので, $φ (φ (a)) \leq φ (a)$ かつ $φ (φ (a)) \neq φ (a)$ である. (つまり $φ (φ (a)) < φ (a)$ )
従って, $φ (a) \in A$ であるが $φ (a) < a$ であるので $a$ が $A$ の最小元であることに矛盾.
つまり, $A = \emptyset$ となる.

以下の二つが成り立つ.
(1) 整列集合はそのどんな切片とも順序同型にならない.
(2) 整列集合の相異なる二つの切片は互いに順序同型にならない.

$(X, \leq)$ を整列集合とする.
(1)
$a \in X$ とする.
順序同型写像 $φ : X \to X ⟨ a ⟩$ が存在すると仮定する.
$X ⟨ a ⟩ \subset X$ であり, $φ$ は順序を保つ単射であるのでlem:junjo*より $a \leq φ (a)$ が成り立つ.
$φ (a) \in X ⟨ a ⟩$ であるから $φ (a) < a$ であるので矛盾.
よって, 任意の $a \in X$ に対して整列集合 $(X, \leq)$ は切片 $X ⟨ a ⟩$ と順序同型にならない.
(2)
$a, b$ を相異なる $X$ の元とする.
$a < b$ としても一般性を失わない.
このとき, $(X ⟨ b ⟩) ⟨ a ⟩ = X ⟨ a ⟩$ となる.

$(X ⟨ b ⟩) ⟨ a ⟩ = {x ∣ x \in X ⟨ b ⟩ \land x < a} = {x ∣ x \in X \land x < b \land x < a} = {x ∣ x \in X \land x < a} = X ⟨ a ⟩$

prop:seiretuと(1)より $X ⟨ b ⟩$ と $(X ⟨ b ⟩) ⟨ a ⟩ = X ⟨ a ⟩$ は順序同型ではない.
よって, 相異なる任意の $a, b \in X$ に対して $X ⟨ a ⟩$ と $X ⟨ b ⟩$ は順序同型にならない.

上の証明において, 一つ上の補題を参照したが実際の補題の番号とあっていない.
アンカーテキストを自分で変えればよいのだがそれはしたくない. 果たしてどうすればよいのか.

背景グレーの文章で前文の証明若しくはヒントを与える.

$(A, \leq)$ と $(B, \leq^{'})$ を整列集合とする. $f : A \to B$ を順序同型写像とすれば, $A$ の任意の元 $a$ に対して
$f (A ⟨ a ⟩) = B ⟨ f (a) ⟩$
が成り立つ.

$f (A ⟨ a ⟩) = {f (x) ∣ x \in A ⟨ a ⟩} = {f (x) ∣ x \in A \land x < a} = {f (x) ∣ x \in A \land f (x) <^{'} f (a)} \subset B ⟨ f (a) ⟩ .$ ( $∵ f$ は特に順序を保つ単射である.)よって, $f (A ⟨ a ⟩) \subset B ⟨ f (a) ⟩ .$
$b \in B ⟨ f (a) ⟩$ とすると, $f$ は順序同型写像であるので $b = f (x)$ かつ $x < a$ となる $x$ が存在する. 従って, $b \in f (A ⟨ a ⟩)$ となる. 故に $f (A ⟨ a ⟩) = B ⟨ f (a) ⟩$ である.

$(X, \leq)$ と $(Y, \leq^{'})$ を整列集合とする. $X$ の部分集合 $X_{1}$ を次で定義する:
$X_{1} = {a \in X ∣ X ⟨ a ⟩ ≃ Y ⟨ b ⟩ となる b \in Y が存在する} .$
このとき, $X_{1}$ は $X$ と一致するか, $X$ のある切片と一致する.

$a \in X_{1}$ をとると, $X ⟨ a ⟩ ≃ Y ⟨ b ⟩$ となる $b \in Y$ が存在し, 順序同型写像 $φ : X ⟨ a ⟩ \to Y ⟨ b ⟩$ とする. $x \in X ⟨ a ⟩$ に対して $y = φ (x)$ とすれば $X ⟨ x ⟩ ≃ Y ⟨ y ⟩$ となる.

$ψ : X ⟨ x ⟩ \to Y ⟨ y ⟩$ を任意の $α \in X ⟨ x ⟩$ に対して $ψ (α) = φ (α)$ で定義するとこれは順序同型写像になる.

従って, $x \in X_{1}$ となる. つまり, $X ⟨ a ⟩$ に属する元は $X_{1}$ に属するので $X ⟨ a ⟩ \subset X_{1}$ となる.
$X \neq X_{1}$ と仮定する.
このとき $X - X_{1}$ は $X$ の空でない部分集合であるので最小元が存在してそれを $a_{1}$ とおく.
$X ⟨ a_{1} ⟩$ の任意の元 $α$ が $X_{1}$ に属さないと仮定すると $α \in X - X_{1}$ であり $α < a_{1}$ であるので $a_{1}$ が $X - X_{1}$ の最小元であることに矛盾する. 従って, $α \in X_{1}$ となる.
従って, $X ⟨ a_{1} ⟩ \subset X_{1}$ である.
$a_{1} < a$ となる $a \in X_{1}$ が存在すれば, $a_{1} \in X ⟨ a ⟩$ である. $X ⟨ a ⟩ \subset X_{1}$ であるので $a_{1} \in X_{1}$ である. これは $a_{1} \notin X_{1}$ に矛盾する. よって, $X_{1} \subset X ⟨ a_{1} ⟩$ となる.
従って, $X_{1} \neq X$ ならば $X_{1} = X ⟨ a_{1} ⟩$ となる.
また, $X = X_{1}$ であれば定理は成り立つ.

整列集合の比較定理の証明

整列集合の比較定理を再掲して証明を与える.
先ほどと同様に補題の参照番号が違うので各々確認しながら証明を追ってほしい.

整列集合の比較定理
整列集合 $(X, \leq_{X}), (Y, \leq_{Y})$ について
(1) $(X, \leq_{X})$ と $(Y, \leq_{Y})$ が順序同型である.
(2) $(X, \leq_{X})$ が $(Y, \leq_{Y})$ のある切片と順序同型である.
(3) $(X, \leq_{X})$ のある切片が $(Y, \leq_{Y})$ と順序同型である.
のいずれか一つが成り立つ. (つまり, どの二つも同時には起こりえない.)

$X$ と $Y$ の部分集合 $X_{1}, Y_{1}$ をそれぞれ次で定義する:

$\begin{array}{r} X_{1} = {a \in X ∣ X ⟨ a ⟩ ≃ Y ⟨ b ⟩ となる b \in Y が存在する}, \\ Y_{1} = {b \in Y ∣ X ⟨ a ⟩ ≃ Y ⟨ b ⟩ となる a \in X が存在する} . \end{array}$
まず, $X_{1} ≃ Y_{1}$ を示す.
任意の元 $a \in X_{1}$ に対して $X ⟨ a ⟩ ≃ Y ⟨ b ⟩$ となる元 $b \in Y$ はただ一つ存在する. また $b \in Y_{1}$ となる.

一意性: $X ⟨ a ⟩ ≃ Y ⟨ b_{1} ⟩$ , $X ⟨ a ⟩ ≃ Y ⟨ b_{2} ⟩$ となる元 $b_{1}, b_{2} \in Y$ が存在すれば $Y (b_{1}) ≃ Y (b_{2})$ であるので $b_{1} = b_{2}$ である.(lem:seppen)
$b \in Y_{1}$ : $b \in Y$ に関してみれば $X ⟨ a ⟩ ≃ Y ⟨ b ⟩$ となる元 $a \in X$ があるので $b \in Y_{1}$ である.

つまり, $a \in X_{1}$ に対して $b \in Y_{1}$ が一意に定まるのでこの元を $b = φ (a)$ とおくと写像 $φ : X_{1} \to Y_{1}$ が定まる.
この $φ$ は順序同型写像となる. 従って, $X_{1} ≃ Y_{1}$ となる.

$ψ : Y_{1} \to X_{1}$ を $φ$ と同様に定める.
つまり, $b \in Y_{1}$ に対して $X ⟨ a ⟩ ≃ Y ⟨ b ⟩$ となる元 $a \in X$ はただ一つ存在し $a \in X_{1}$ となる. この元を $a = ψ (b)$ とおくことで $ψ : Y_{1} \to X_{1}$ を定める.
$φ$ と $ψ$ の定め方により $ψ \circ φ = 1_{X_{1}}, φ \circ ψ = 1_{Y_{1}}$ となるので $φ, ψ$ は全単射になり, 互いに逆写像である.
$a, a^{'} \in X$ で $a < a^{'}$ とする. $X_{1}, φ$ の定義により $X ⟨ a^{'} ⟩ ≃ Y ⟨ φ (a^{'}) ⟩$ となる. つまり順序同型写像 $f : X ⟨ a^{'} ⟩ \to Y ⟨ φ (a^{'}) ⟩$ が存在する.
lem:fより $f (X ⟨ a ⟩) = Y ⟨ f (a) ⟩$ が成り立つ. また, $f (a)$ は $Y ⟨ φ (a^{'}) ⟩$ の元であるので $φ (a) = f (a) <^{'} φ (a^{'})$ となる.
従って $φ$ は順序を保つ全単射である. 同様に $ψ$ も順序を保つ全単射になることがわかる.
以上から $φ, ψ$ は順序同型写像である.

lem:ittiから $X_{1}$ は $X$ と一致するか, $X$ のある切片と一致する. $Y_{1}$ についてもlem:ittiを用いて $Y_{1}$ は $Y$ と一致するか, $Y$ のある切片と一致する.
もし $X_{1} = X ⟨ a ⟩$ かつ $Y_{1} = Y ⟨ b ⟩$ とすると $X_{1} ≃ Y_{1}$ であるから $X ⟨ a ⟩ ≃ Y ⟨ b ⟩$ となり $x_{1}$ の定義から $a \in X_{1}$ となるがこれは $a \notin X ⟨ a ⟩$ に矛盾する.
よって, $X_{1} = X$ または $Y_{1} = Y$ のいずれかは成り立つので(1)～(3)のいずれかは必ず成り立つ.

次にどの二つも同時に成り立たないことを示す.
(1)と(2)が同時に成り立つと仮定する.
すると $X ≃ Y$ かつ $X ≃ Y ⟨ β ⟩$ なる $β \in Y$ が存在する. $Y ≃ Y ⟨ β ⟩$ となるがこれはlem:seppenに矛盾する.
よって(1)と(2)は同時には成り立たない.
同様に(1)と(3)も同時に成り立たないことがわかる.
(2)と(3)が同時に成り立つと仮定する.
すると $X ≃ Y ⟨ β ⟩$ かつ $Y ≃ X ⟨ α ⟩$ なる $α \in X, β \in Y$ が存在するので順序同型写像 $f : X \to Y ⟨ β ⟩, g : Y \to X ⟨ α ⟩$ が存在する.
包含写像 $ι_{X} : X ⟨ α ⟩ \to X, ι_{Y} : Y ⟨ β ⟩ \to X$ はどちらも順序を保つ単射であるので合成写像 $h = ι_{X} \circ g \circ ι_{Y} \circ f$ は順序を保つ単射である.