Zorn の補題学習ノート
Zorn の補題に関するノート。目標：Zorn の補題を選出公理から、整列可能定理から証明する。 現在、選出公理ベースのものを二つ記した。
Zorn の補題
教科書に書いてある proposition は次の意味だった：
Suppose a partially ordered set $P$ has the property that
every chain in $P$ has an upper bound in $P$.
Then the set $P$ contains at least one maximal element.
この that 節の property を帰納的順序集合と名付けることで言い回しが短くなる。すなわち：
帰納的順序集合は極大元を少なくとも一つ持つ。
- コメント：空集合も vacuously true ルールにより帰納的順序集合とみなすことに注意。
証明
背理法により証明する：帰納的順序集合 $(S, \prec)$ に極大元が存在しないと仮定する。
帰納的順序集合の性質により、すべての鎖 $C \subset S$ には上界が存在する。
- コメント：$x \in S$ が順序集合 $C$ の上界であるとは $\forall c(c \in C \implies c \prec x \land c \ne x)$ を意味する。
- コメント：鎖 $C$ の上界 $y$ を一つをとれば、背理法の仮定により $y$ は極大元でない。 それゆえ $y \prec x \land y \ne x$ なる任意の $y$ が使える。
整列順序 $\prec$ によって整列集合となる各 $W \subset S$ に対し、選出公理を使って $W$ の上界を $f(W)$ として取り出す関数 $f$ が存在する。 $S$ の整列部分集合から $S$ への写像 $f\colon \operatorname{Well}(S) \longrightarrow S$ が与えられていて、
\[\forall x(x \in W \implies x = f(s(x)))\]であるならば $W \in \operatorname{Well}(S)$ は $f$-帰納的であるということにする。
- コメント： 資料に明示されてはいないが、$\operatorname{Well}(S)$ とは $S$ のすべての整列部分集合の族であろう。
- コメント： $x$ の切片を $s(x)$ で表す。
今 $Y, Z \in \operatorname{Well}(S)$ を $f$-帰納的集合であるとする。このとき、一方が他方の切片であることを以下に示す。 「$S$ の部分集合であり、$Y$ と $Z$ の両方の切片である」($\bigstar$) ものの和集合を $I$ とする。 このとき $I$ は ($\bigstar$) のような切片の中では極大である。 $I \subsetneq Y \cap Z\;(\spadesuit)$ と仮定する。 $y = \min(Y\setminus I)$, $z = \min(Z\setminus I)$ をとる。 すると
\[s(y) = I = s(z)\]であり、$Y, Z$ が $f$-帰納的であることから $y = f(I) = z.$ ゆえに $I$ は切片 $I \cup \lbrace y \rbrace = I \cup \lbrace z \rbrace$ へ拡張できる集合ということになり、 $I$ の極大性に矛盾する。したがって $(\spadesuit)$ はあり得ず、 $I = Y$ または $I = Z$ が必要であり、$Y, Z$ のうちの一つが他方の切片である。
だから $f$-帰納的集合の集まりは切片の包含関係による全順序集合であり、 それらの和集合を $U$ とすると、それは極大 $f$-帰納的集合になるはずだ。 しかし、その上界 $f(U)$ を付け加えた、鎖 $U \cup \lbrace f(U)\rbrace$ は $U$ よりも真に大きな $f$-帰納的順序集合であり、矛盾。以上で証明は終わる。
弱 Zorn の補題から順次証明する方法
いきなり Zorn の補題を証明するのは見通しがよくない。オリジナルの補題よりも弱い主張のものを先に見て感覚を掴む。 「帰納的順序集合は～」の部分を弱くする：
弱 Zorn の補題
$S$ を順序集合であって、どの鎖も（上界ではなく）上限を有するものだとする。 このとき $S$ には少なくとも一つは極大元がある。
証明：$S$ に次のような操作 $f$ を導入する。これが成立することは選出公理による：
- $x \in S$ が極大元ならば $f(x) = x.$
- $x \in S$ が極大元でなければ、$\exists y(y \in S \land x \prec y)$ ゆえ、 ある $y$ を一つとって $f(x) = y.$
ここで用語を一つ導入する。$N \subset S$ が塔であるとは、次の性質二つを満たすことをいうことにする：
\[\begin{aligned} P1:\quad & \forall x(x \in N \implies f(x) \in N).\\ P2:\quad & \forall C(C \subset N \land C \text{ is a chain}\implies \sup C \in N). \end{aligned}\]次は練習問題とする：
- $S$ 自身は塔である。
- 塔の族のどのようなものの交差も塔である。
$S$ の最小の塔で空でないものを $M$ とする。そしてもう一つ性質を定義する。 $x \in M$ に対して：
\[P3:\quad \forall y(y \in M \implies y \preceq x \lor f(x) \preceq y).\]とする。次の補題を考える：
補題：$P3$ 集合は鎖であり、極大元が存在して最大元に等しい
補題：すべての $x \in M$ が $P3$ を満たせば、$M$ は鎖である。 そして $M$ には $S$ の極大元であると同時に最大元となる要素がある。
証明：鎖であることからまず示す。勝手に $x, y \in M$ をとる。 $P3$ から $y \preceq x$ でなければ $f(x) \preceq y$ が必要だ。 しかし $P1$ につき $f(x) \in M$ だから $f$ の定義から $x \preceq f(x).$ 推移律は $x \preceq y$ を要求する。$\lnot(y \preceq x) \implies x \preceq y$ が言えたので $M$ は鎖だと示された。
さて $M$ は鎖であり、$P2$ が成り立つことから $M$ 自身が $\sup M$ を含まねばならない。 このとき $\sup M$ は極大元であるが、$\sup M \preceq f(\sup M)$ が成り立つ一方、 他方では $P1$ につき $f(\sup M) \in M,$ したがって $f(\sup M) \preceq \sup M.$ 反対称律により $\sup M = f(\sup M).$ 以上で補題が正しいことが証明された。
話を元に戻す。このすぐ上の補題から、$M$ のすべての要素に対して $P3$ が成立すれば先の弱 Zorn の補題が証明されることがわかる。 それをなすべく、もう一つ性質を定義する。
$x \in M$ が $P4$ であるとは次の性質があることを意味するものとする：
\[P4: \quad \forall y(y \in M \land y \prec x \implies f(y) \preceq x).\]補題： $P4$ 集合は $P3$ 集合
補題： $\forall x(x \in M \land P4(x) \implies P3(x)).$
証明： $M^\prime$ を次のように置く（述語部分は $P3$ と同じ）：
\[M^\prime \coloneqq \{y\,|\, y \in M \land (y \preceq x \lor f(x) \preceq y)\}.\]もし $M^\prime$ が塔であることが証明できれば $M$ が $S$ の最小の塔であることから $M^\prime = M.$ だから $M^\prime$ が $P1$ および $P2$ であることを以下示す。
$P1$ つまり $\forall y(y \in M^\prime \implies f(y) \in M^\prime)$ を示す。 $M^\prime$ の定義から次のうちのちょうど一つが成り立つ：
- $y \prec x$
- $y = x$
- $f(x) \preceq y$
もし 1. が成り立つならば $P4(x)$ が真であることから $f(y) \preceq x.$ したがって $f(y) \in M^\prime$ となり $P1(M^\prime)$ は真。
もし 2. か 3. が成り立つならば明らかに $f(x) \preceq f(y).$ したがって $f(y) \in M^\prime$ となり $P1(M^\prime)$ は真。
$P2$ つまり $\forall C(C \subset M^\prime \land C \text{ is a chain}\implies \sup C \in M^\prime)$ を示す。
$C$ を $M$ の鎖だと見ることができるので $\sup C \in M.$ このとき次の二通りの可能性がある：
- $\forall z(z \in C \implies z \preceq x).$
- $\exists z(z \in C \land x \prec z).$
もし 1. であれば $x$ は上界の一つなので $\sup C \preceq x.$ ゆえに $\sup C \in M^\prime.$
もし 2. であれば、この条件から直ちに $f(x) \preceq z$ が言えて $f(x) \preceq \sup C,$ したがって $\sup C \in M^\prime.$
いずれの場合でも $\sup C \in M^\prime$ が成り立つ。よって $P2(M^\prime)$ も成り立つ。
以上により $M^\prime$ は塔であり、$M^\prime = M$ が示された。
弱い Zorn の補題の証明の最終段階は次の補題を示すことだ。
補題 $M$ は $P4$ 集合
補題：
\[\forall x(x \in M \implies P4(x))\]証明：それには
\[N \coloneqq \lbrace x \,\mid\, x \in M \land P4(x)\rbrace\]とおいて、先の議論のように $N$ が塔であることを示せば十分だ。
まず $P1(N)$ が真であることを示す。言いたいことは $\forall x(x \in N \implies f(x) \in N).$ それには $y \prec f(x)$ なるすべての $y \in M$ を見て $f(y) \preceq f(x)$ であることを示してみる。
先ほどの補題から $P3(x)$ が真であることがわかっているので、あり得るケースは $y \preceq x$ しかない。
- もし $y \prec x$ ならば $P4(x)$ が真であると仮定したことから $f(y) \preceq x$ を得る。 したがって $f(y) \preceq f(x).$
- もし $y = x$ ならば $f(y) \preceq f(x)$ は自明だ。
いずれの場合においても $f(x) \in N$ が証明された。したがって $P1(N)$ は真である。
次に $P2(N)$ が真であることを示す。 鎖 $C \subset N$ を考える。$\sup C \in N$ であること、すなわち $P4(\sup C)$ が成り立つことを示したい。 言い換えると、$y \prec \sup C$ を満たす全ての $y \in M$ にたいして $f(y) \preceq \sup C$ であることを示す必要がある。
$y \prec \sup C$ より $y$ は $C$ の上界ではない。 だから $\exists z(z \in C \land \lnot(z \preceq y)).$ これが意味するのは
- $y$ と $z$ が比較不能であるか、
- あるいは $y \prec z$ であるかだ。
ところが $z \in N$ は $P4(z)$ が成り立つゆえ $P3(z)$ が成り立ち、 それにより $z$ と $y \in M$ は比較可能、つまり後者が成り立つ。
ここで $P4(z)$ を適用して $f(y) \preceq z$ を得るので $f(y) \preceq \sup C.$ ゆえに $\sup C \in N$ が言えて $P2(N)$ が成り立つことが確認できた。
以上により $N$ が塔であることがわかったので、$N = M$ が得られる。
弱い Zorn の補題の証明を仕上げよう。
$M$ のすべての要素が $P4$ であることを示した。$P4$ は $P3$ を含意することも示した。 $P3$ 集合は最大元を有しなければならず、それは $S$ の極大元であることが示された。 以上より弱い Zorn の補題が示された。
Hausdorff の極大原理
補題：順序集合は極大鎖、すなわち他の鎖の部分集合とはならないような鎖を含む。
証明：順序集合を $Q$ とする。 集合 $S$ を $Q$ のすべての鎖からなる集合（族）で定義して、 集合の包含関係に関する順序を入れてそれを $\prec_S$ とする。詳しく言うと、 $C_1, C_2 \in S$ が鎖であるとき $Q$ において $C_1 \subset C_2$ であれば
\[C_1 \prec_S C_2\]と規約する（この $\prec_S$ が順序関係であることを示すのは容易い）。
もう一つのだいじな性質は二つの鎖の $Q$ における交わりが一つの鎖であること、 そして事実、$Q$ 内の任意の鎖の交わりはまた鎖をなす（練習問題）。 今、$S$ の任意の鎖を $K$ とおこう。$K \in S$ の要素は $Q$ の（部分である）鎖（複数形）から構成されることに注意する。
- コメント：よく読むとわからない。
集合 $K$ を順序集合 $Q$ の要素で形成された集合とみなすとき $#K$ と表す。 明らかに $#K$ は $Q$ 内の鎖である。 もし $Q$ に極大鎖がなければ、次のような $k \in Q$ が少なくとも一つ存在しなければならない：
\[\forall x(x \in \#K \implies x \prec_Q k).\]このとき $#\tilde K \coloneqq #K \cup \lbrace k \rbrace$ は $Q$ の鎖であり、 $\tilde K \coloneqq K \cup \lbrace k \rbrace$ は $S$ にあり $K$ に対する上界のひとつである。
今もし $A_1, A_2 \in S$ が $K$ の上界だとすると、 $A_1 \cap A_2$ もまた $K$ の上界になる（練習問題）。 $\sup K$ を $K$ のあらゆる上界の交わりとして定義する。 すると $\sup K$ は $Q$ の鎖であり、構成から $K$ に対する上限の一つである。
したがって $S$ はすべての鎖 $K$ が上限を有するような順序集合である。 弱 Zorn の補題は、極大元 $K \in S$ が一つ存在すると述べていることになる。 しかしこれは $#K$ は $Q$ の鎖の一つであって、より長い鎖に含まれないと言うのと同じであり、この補題の証明が終わる。
Zorn の補題の証明
弱 Zorn の補題に設けた条件を強めることができる： 順序集合 $S$ の鎖のすべてに上界が存在する。
証明：Hausdorff の極大原理によれば、極大鎖 $C \subset S$ が存在する。 鎖であることから $C$ には上界 $x \in S$ がなければならない。 そしてこれは $C \cup \lbrace x \rbrace \in S$ が別の鎖であることを意味する。 ところが $C$ は極大であるゆえに $x \in C.$ それに、$x$ は $C$ の最大元でなければならない。 最後に、仮に $x \prec f(x)$ が成り立つならば $C$ の極大性に矛盾することになる集合 $C \cup \lbrace f(x)\rbrace$ を考えることができるので、 $x$ は $S$ の極大元であり $x = f(x).$ 以上で証明が終わる。
- コメント：極大鎖に上界があるのだから、それより小さい鎖すべてに上界がある。
参考資料
- Zorn’s lemma - Wikipedia
- Zorn’s lemma - nLab
- 途中の記号 $\operatorname{Well}(S)$ がわからない。
- Zorn’s Lemma - Lektor Lektorean, 2010.
- 読みやすい。上に全部写したが、私には理解を詰める箇所が残っている。