ツォルンの補題の証明

2020/04/262020/06/08

今日の目標

選択公理からツォルンの補題を示す。

以下、 $X$ は集合で $\leq$ は $X$ 上の半順序とする。

半順序についてはこちら

半順序・全順序・狭義半順序・狭義全順序

今日の目標半順序・全順序・狭義半順序・狭義全順序とそれらの関係について学ぶ。この記事で使う記号 ...

https://sorai-note.com/math/200413/

基礎事項と用語の確認

定義

$C \subseteq X$ が鎖であるとは、

各 $x, y \in C$ に対し $x \leq y$ または $y \leq x$

であることとする（つまり $C$ は $\leq$ により全順序集合）。

定義

$S \subseteq X$ が整列集合であるとは、

$S$ の空でない部分集合は必ず最小元を持つ

こととする。

命題１

整列集合は鎖である。

証明

整列集合 $S$ に対し $x, y \in S$ を任意に取ると、 $S$ の非空部分集合 ${x, y}$ は最小元を持つので $x \leq y$ または $y \leq x$ である。

定義

$x, y \in X$ に対し $x < y$ とは

$x \leq y$ かつ $x \neq y$

であることとして定める。

定義

整列集合 $S \subseteq X$ と $a \in S$ に対し、整列集合 $S [a]$ を $S [a] = {b \in S | b < a}$ で定め、 $S$ の $a$ による切片という。

定義

$x \in X$ が極大元であるとは

各 $y \in X$ に対し $x ≮ y$

であることとする。
$u \in X$ が $A \subseteq X$ の上界であるとは

各 $a \in A$ に対し $a \leq u$

であることとする。
$v \in X$ が $A \subseteq X$ の強上界であるとは

各 $a \in A$ に対し $a < v$

であることとする。

今日示すのはこれ

定理（ツォルンの補題）

選択公理を仮定する。このとき $X$ の任意の鎖が上界を持つならば $X$ は極大元を持つ。

方針は？

対偶を示そうかな

つまり
「極大元がない

⟹

上界を持たない鎖がある」
を示す

ちなみに
極大元が存在しない状況では
上界の存在と強上界の存在は同値

命題２

$X$ は極大元を持たないとする。このとき $X$ の部分集合が上界を持つことと強上界を持つことは同値である。

証明

強上界は上界なので、強上界を持てば上界を持つ。

逆に $A$ が上界 $u$ を持つと、 $u$ は極大元でないので $u < v$ なる $v$ が存在し、

各 $a \in A$ に対し $a \leq u < v$

となるので $v$ が $A$ の強上界になる。

あと
強上界を持つ整列集合は延長できる
ってことも確認しとこう

命題３

整列集合 $S \subseteq X$ が強上界 $v$ を持てば $S \cup {v}$ も整列集合である。

証明

$S \cup {v}$ の非空部分集合 $A$ を任意に取り、 $A$ が最小元を持つことを示す。

$A = {v}$ のときや $A \subseteq S$ のときは自明。そうでないとき $A = (A \cap S) \cup {v}$ であり、 $A \cap S$ が $S$ の非空部分集合なので $m = min (A \cap S)$ が存在するが、

各 $a \in A \cap S$ に対し $a < v$

なので、 $A$ の最小元は $m$ である。

「上界」より「強上界」にスポットライト当てる感じ？

上界より強上界の方が
「整列集合の延長」を考えるときに
しっくりくるからね

ツォルンの補題の証明では
強上界を持たない整列集合を作るのを目指すよ

ツォルンの補題の証明のイメージ

強上界を持たない整列集合ってことは
けっこうでかい整列集合を作るってこと？

そうそう
整列集合をたくさん集めて
その和集合を取ろうかと

でも整列集合ってめちゃくちゃあるじゃん

そうそう図にするとこんな感じ

丸が

X

の要素で
青線はそれぞれ整列集合だと思ってね

うげ

ここから
こんな感じの整列集合の集まりを取り出したい

あらすっきり

こんな整列集合の集まり

S_{f}

を作るために
選択公理を使うよ

「強上界を持つ鎖」それぞれに対して
その強上界を一つずつ選んでくれるような
関数

f

を選択公理で取ってくる

その

f

の選択方針に沿うような
整列集合だけを集めて

S_{f}

を作る

どゆこと？

こんな感じにしたいってこと

あーね

あとは

S_{f}

の整列集合全部の和集合

\tilde{S} = ⋃_{S \in S_{f}} S

を考えて

「

\tilde{S}

も

S_{f}

に属す」ってことと

「

S \in S_{f}

が強上界を持ったら

S \cup {f (S)} \in S_{f}

」ってことを示して……

もし

\tilde{S}

が強上界持っちゃったら

\tilde{S} \cup {f (\tilde{S})}

っていうもっとでかいのが作れて
でも

\tilde{S}

は

S_{f}

の中で一番でかいはずだから
それはおかしいねってことね

そ

ふたつの整列集合を「切って」同じにする

S_{f}

が綺麗な並びになってることを示すのに
便利なのがこれ

定理４

整列集合 $S, T \subseteq X$ に対し、

$S = T$
$S = T [b]$ となる $b \in T$ が存在する
$S [a] = T$ となる $a \in S$ が存在する
$S [a] = T [b]$ かつ $a \neq b$ となる $a \in S$ と $b \in T$ が存在する

のいずれかが成立する。

証明

1 ～ 3 が成り立たないとして 4 を示す。1 でないので「 $S ⊈ T$ または $T ⊈ S$ 」だが、対称性より $S ⊈ T$ としてよい。

$S ∖ T$ が非空なので $a = min (S ∖ T)$ が存在する。最小性から、 $a$ より小さな要素は $S ∖ T$ に属さない。つまり $S [a] \subseteq T$ である。いま 3 は成り立たないので $S [a] ⊉ T$ である。よって $b = min (T ∖ S [a])$ が存在し、最小性から $T [b] \subseteq S [a]$ である。ここで $a \neq b$ であることが $a \notin T$ と $b \in T$ からわかる。よってもし $T [b] \supseteq S [a]$ であれば 4 が成り立つことがわかる。

以下 $T [b] ⊉ S [a]$ とする。このとき $c = min (S [a] ∖ T [b])$ が存在し、最小性から $S [a] [c] \subseteq T [b]$ だが、 $c \in S [a]$ なので $S [c] \subseteq T [b]$ である。ここで $b \neq c$ であることが $b \notin S [a]$ と $c \in S [a]$ からわかる。

$b < c$ を示す。 $c \in T$ であることが $c \in S [a]$ からわかる。更に $c ≮ b$ であることが $c \notin T [b]$ からわかる。 $b$ も $c$ も鎖 $T$ に属し $b = c$ でも $c < b$ でもないので、 $b < c$ になるしかない。

$T [b] \subseteq S [a]$ より $T [b]$ の要素は $S$ に属すことと $b < c$ であることにより $T [b] \subseteq S [c]$ となり、 $T [b] = S [c]$ を得た。よって 4 が成り立つ。

チョキチョキ切った下側が等しくなる

意外といろんな状況があって厄介だね

ツォルンの補題の証明

定理（ツォルンの補題）

選択公理を仮定する。このとき $X$ の任意の鎖が上界を持つならば $X$ は極大元を持つ。

証明

$X$ に極大元がないと仮定し、上界を持たない鎖が存在することを示す。このとき $X$ の部分集合が上界を持つことと強上界を持つことが同値になることに注意（命題２）。

強上界を持つ鎖全体（したがって上界を持つ鎖全体）を $\hat{C}$ とする。このとき選択公理より

各 $C \in \hat{C}$ に対し $f (C)$ は $C$ の強上界

であるような写像 $f : \hat{C} \to X$ が存在する。ここで整列集合 $S \subseteq X$ で $\forall a \in S, f (S [a]) = a$ なるもの全体を $S_{f}$ と書く（ $S [a]$ は強上界 $a$ を持つので $S [a] \in \hat{C}$ ）。

主張１

$S, T \in S_{f}$ で $S \neq T$ ならば

「 $S$ は $T$ のある切片」または「 $T$ は $S$ のある切片」

となる。特に $S, T \in S_{f}$ に対し $S \subseteq T$ または $T \subseteq S$ である。

もし $S [a] = T [b]$ となる $a \in S, b \in T$ が存在したら $a = f (S [a]) = f (T [b]) = b$ なので定理４の 4 は $S, T \in S_{f}$ に対して成り立たない。いま定理４の 1 も成り立たないので、一方がもう一方の切片になるしかない。

$\tilde{S}$ $= ⋃_{S \in S_{f}} S$ とする。

主張２

$\tilde{S}$ は鎖である。

$a, b \in \tilde{S}$ とすると $a \in S, b \in T$ なる $S, T \in S_{f}$ が取れ、主張１より

$S \subseteq T$ または $T \subseteq S$

である。よって $a, b \in T$ または $a, b \in S$ であり、 $S$ も $T$ も鎖なので、どちらの場合でも「 $a \leq b$ または $a \geq b$ 」を得る。

主張３

$a, b \in \tilde{S}$ で $a < b$ のとき、任意の $S \in S_{f}$ に対し $b \in S ⟹ a \in S$ が成り立つ。

$b \in S$ とし、 $a \in T$ なる $T \in S_{f}$ を取る。主張１を用いる。まず $S [c] = T (c \in S)$ のときは $a \in T = S [c] \subseteq S$ である。一方 $S = T [c] (c \in T)$ のときは $a < b$ と $b \in S = T [c]$ より $a \in T [c] = S$ である。

主張４

$\tilde{S}$ は整列集合である。

$A$ が $\tilde{S}$ の非空部分集合ならば、 $\tilde{S}$ の定義より $A \cap S \neq \emptyset$ なる $S \in S_{f}$ が存在し、 $S$ は整列集合なので $m = min (A \cap S)$ が存在する。

$a \in A$ を任意に取る。もし $a < m$ ならば、主張３と $m \in S$ から $a \in S$ となり、 $m$ の最小性に矛盾する。よって $a ≮ m$ であり、主張２より $\tilde{S}$ は鎖なので $m \leq a$ であり $m = min A$ を得る。

主張５

$\tilde{S} \in S_{f}$ である。

主張４より $\tilde{S}$ は整列集合。 $a \in \tilde{S}$ を任意に取って $f (\tilde{S} [a]) = a$ を示す。

$a \in S$ なる $S \in S_{f}$ を取ると、 $S \subseteq \tilde{S}$ より $S [a] \subseteq \tilde{S} [a]$ である。一方 $b \in \tilde{S} [a]$ を任意に取ると、 $b < a$ と主張３と $a \in S$ より $b \in S$ であり、 $b \in S [a]$ を得る。よって $\tilde{S} [a] \subseteq S [a]$ も得られた。したがって $\tilde{S} [a] = S [a]$ となり $f (\tilde{S} [a]) = f (S [a]) = a$ である。

主張６

$S \in S_{f}$ が強上界を持てば $S \cup {f (S)} \in S_{f}$ である。

$f (S)$ は $S$ の強上界。 $S^{'} = S \cup {f (S)}$ とすると命題３より $S^{'}$ は整列集合なので、各 $a \in S^{'}$ に対し $f (S^{'} [a]) = a$ を示せばよい。

$a = f (S)$ のときは、 $f (S^{'} [a]) = f (S^{'} [f (S)]) = f (S) = a$ である。

$a \in S$ のときは、 $a < f (S)$ なので $S^{'} [a] = S [a]$ である。よって $f (S^{'} [a]) = f (S [a]) = a$ を得る。

もし $\tilde{S}$ が上界を持てば強上界も持ち（命題２）、主張６より $\tilde{S} ⊊ \tilde{S} \cup {f (\tilde{S})} \in S_{f}$ となるが、これは $\tilde{S}$ の定義に反する。

よって鎖 $\tilde{S}$ は上界を持たない。

空集合に対するツォルンの補題

定理のステートメントに

X

が空集合のときを除外してないけど
大丈夫？

X = \emptyset

のとき

X

の鎖は

\emptyset

ただ一つでしょ

うん

でもその鎖には上界が無い

X = \emptyset

だからね

つまり

X = \emptyset

は上界を持たない鎖

\emptyset

を持つ

ああ
「任意の鎖が上界を持つならば」って言ってる時点で

X \neq \emptyset

になるのか

セミナー,数学Zornの補題,ツォルンの補題,数学,整列順序,選択公理

始域や終域が空集合の写像｜空関数と単射性と全射性

ペアノの公理の一意性