Zornの補題の主張を図で理解する!
0. はじめに
これまで私は, Zornの補題が何を言っているのかよく分からず, 証明も長いので, 脳が理解することを拒絶していました. しかし, この補題の主張はHasse図を用いればすんなりと受け入れられることができます. この記事では, そのようなHasse図的な補題の主張の解釈をしていきます. (今回はZornの補題の証明の話ではありません. 証明が気になる人は, 何か適切な教科書を読んでください. )
1. Hasse図と順序について
Hasse図とは, 半順序集合に対して考えられる, 順序関係を表す図のことです. 例えば, 以下の図は半順序$(2^{\{a,b,c\}},\subseteq)$のHasse図です.
\begin{xy}
\xymatrix {
&\{a,b,c\}&\\
\{a,b\}\ar[ru]&\{a,c\}\ar[u]&\{b,c\}\ar[lu]\\
\{a\}\ar[u]\ar[ru]|{\text{ }}&\{b\}\ar[lu]\ar[ru]&\{c\}\ar[lu]|{\text{ }}\ar[u]\\
&\emptyset \ar[lu]\ar[u]\ar[ru]&
}
\end{xy}
この図は小さい方から大きい方に矢印がついています.
見てわかる通り, これは推移律で分解される部分には矢印は書かれていません(例えば$\{a\}\subseteq\{a,b,c\}$ですが, $\{a\}\subseteq\{a,b\}\subseteq\{a,b,c\}$などと分解できるので$\{a\}\to\{a,b,c\}$の矢印は書かれていません).
ここで, Hasse図という武器を得たので, 前順序, 半順序, 全順序のHasse図を描いてみます. (これにより, 前順序, 半順序と言われたときに, 図を思い浮かべれば, それが「公理を思い出すための材料」になります. )
$A$を集合とする. $A$上の二項関係$\leqq$が, 任意の$a,b,c\in A$に対して以下の条件1,2を満たすとき, $(A,\leqq)$を前順序集合という. 加えて条件3も満たすとき, $(A,\leqq)$を半順序集合(Poset)という. さらに加えて条件4も満たすとき, $(A,\leqq)$を全順序集合という.
- (反射律) $a\leqq a$.
- (推移律) $a\leqq b,\ b\leqq c\ \Rightarrow\ a\leqq c$.
- (反対称律) $a\leqq b,\ b\leqq a\ \Rightarrow\ a=b$.
- (完全律) $a\leqq b$または$b\leqq a$.
以下のような, ループを許す図になります. (反対称律がないから. ) さらに, 連結でなくてもいいです.
\begin{xy}
\xymatrix{
\bullet&&\bullet&\bullet\ar@/_12pt/[d]\\
&\bullet\ar[ul]\ar[ur]&&\bullet\ar@/_12pt/[u]\\
\bullet\ar@/_12pt/[r]&\bullet\ar[u]\ar@/_12pt/[r]\ar@/_12pt/[l]&\bullet\ar@/_12pt/[l]&\bullet\ar[u]\\
&\bullet\ar[u]&&
}
\end{xy}
実は前順序集合にはHasse図は定義されていませんが, ここではそれに相当する上のような図をHasse図ということにします.
反対称律により, ループは許されなくなり, 1点につぶれます.
\begin{xy}
\xymatrix{
\bullet&&\bullet\\
&\bullet\ar[ul]\ar[ur]&&\bullet\\
&\bullet\ar[u]&&\bullet\ar[u]\\
&\bullet\ar[u]&
}
\end{xy}
完全律により, 枝分かれや連結でない図が許されなくなります.
\begin{xy}
\xymatrix{
&\bullet\\
&\bullet\ar[u]\\
&\bullet\ar[u]\\
&\bullet\ar[u]
}
\end{xy}
ここまで読んで, 「$\mathbb Q$や$\mathbb R$はHasse図でかけないじゃないか!」と思う人もいると思います. このような順序集合に対しては, Hasse図のかわりに滑らかな線を思い浮かべてほしいです.
\begin{xy}
\xymatrix{
\mathbb Q\text{ or }\mathbb R&&\\
&&\\
&&\\
&\ar[uuu]&
}
\end{xy}
他にも, $\mathbb R$のように連続な"半順序"集合に対しても, 枝分かれのあるサンゴ礁のような形の線がたくさんある様子を思い浮かべればいいと思います(非連結でも良い).
\begin{xy}
\xymatrix{
&&&&&&\\
&\ar@/_5pt/[ul]\ar@/_-5pt/[ur]&&&&&\\
&&&&{}\ar@{-}@/_5pt/[ur]&&\\
&\ar[uuu]&\ar@/_20pt/[uuur]&&\ar@/_-20pt/[uuul]&\ar[uuu]&{}\ar@{-}@/_-5pt/[ul]
}
\end{xy}
2. Zornの補題
まずはZornの補題の主張を思い出しましょう.
空でない帰納的半順序集合は極大元を持つ.
この主張を理解するための最低限の言葉の定義は以下の通りです.
$P$を半順序集合とする.
- $P$の任意の部分全順序集合が上界を持つとき, $P$を帰納的半順序集合という.
- $Q\subseteq P$とする. ある$p\in P$が存在して, 任意の$q\in Q$に対して$q\leqq p$のとき, $p$を$Q$の上界という.
- $p\in P$が任意の$p'\in P$に対して$p< p'$が成り立たないとき, $p$を$P$の極大元という.
例2のHasse図を例に, 上界とは何か見てみましょう.
以下の図の, 白丸の部分をみてみます.
\begin{xy}
\xymatrix{
\bullet&&\bullet\\
&\bullet\ar[ul]\ar[ur]&&\bullet\\
&\circ\ar[u]&&\bullet\ar[u]\\
&\circ\ar[u]&
}
\end{xy}
上の図の白丸の点全体は, 部分半順序集合となっています. この部分集合に対する上界とは, 以下の図の星形の元です. (定義と照らし合わせて確認してみてください. )
\begin{xy}
\xymatrix{
\star&&\star\\
&\star\ar[ul]\ar[ur]&&\bullet\\
&\star\!\!\!\circ\ar[u]&&\bullet\ar[u]\\
&\circ\ar[u]&
}
\end{xy}
極大元が複数ある可能性があることに注意しましょう. 例2で見たHasse図をもう一度表示します.
\begin{xy}
\xymatrix{
\star&&\star\\
&\bullet\ar[ul]\ar[ur]&&\star\\
&\bullet\ar[u]&&\bullet\ar[u]\\
&\bullet\ar[u]&
}
\end{xy}
この図の星形の点が, この半順序集合の極大元です. (こちらも定義と照らし合わせて確認してみてください. )
3. Zornの補題の図的な解釈
以下では帰納的半順序集合とは何かを, 図で考えていきます.
以下の形をした半順序集合を考えます.
\begin{xy} \xymatrix{ &&&&&&\\ &\ar@/_5pt/[ul]\ar@/_-5pt/[ur]&&&&&\\ &&&&{}\ar@{-}@/_5pt/[ur]&&\\ &\ar[uuu]&\ar@/_20pt/[uuur]&&\ar@/_-20pt/[uuul]&\ar[uuu]&{}\ar@{-}@/_-5pt/[ul] } \end{xy}
この中の部分全順序集合をピックアップします. 例えば, 波線の部分は部分全順序集合です.
\begin{xy} \xymatrix{ &&&&&&\\ &\ar@/_5pt/[ul]\ar@/_-5pt/[ur]&&&&\ar[u]&\\ &&&&{}\ar@{-}@/_5pt/[ur]&&\\ &\ar[uuu]&\ar@/_20pt/[uuur]&&\ar@/_-20pt/[uuul]&{}\ar@{-}[u]&{}\ar@{~}@/_-13pt/[uul] } \end{xy}
すると, 波線部分は以下の2重波線のような上界の集合を持ちます.
\begin{xy} \xymatrix{ &&&&&&\\ &\ar@/_5pt/[ul]\ar@/_-5pt/[ur]&&&&*{}\ar@2{~}[u]&\\ &&&&{}\ar@{-}@/_5pt/[ur]&&\\ &\ar[uuu]&\ar@/_20pt/[uuur]&&\ar@/_-20pt/[uuul]&{}\ar@{-}[u]&{}\ar@{~}@/_-13pt/[uul] } \end{xy}
帰納的半順序集合とは, つまりどの鎖を選んでも, それより上に上界があるような半順序集合のことです.
選んだ鎖がちぎれていても, 推移律で比較可能であれば, それは全順序集合になります. 例えば以下の波線は全順序集合です.
\begin{xy}
\xymatrix{
&&&&&&\\
&\ar@/_5pt/[ul]\ar@/_-5pt/[ur]&&&&*{}\ar@{~>}[u]&\\
&&&&{}\ar@{-}@/_5pt/[ur]&&\\
&\ar[uuu]&\ar@/_20pt/[uuur]&&\ar@/_-20pt/[uuul]&{}\ar@{-}[uu]&{}\ar@{~}@/_-5pt/[ul]
}
\end{xy}
帰納的であるには, このようなちぎれた鎖も上界を持つかどうかを調べなければなりません.
ここまで読むと, なんとなくZornの補題の主張が直感的に分かるようになります.
つまり, どんな鎖を選んでも上界があるんだったら, 極大元を持ちそう$!$ということを, 図の解釈で受け入れられそうです.
例えば例2をみてください. これは有限半順序集合なので自明ですが, どの鎖を選んでも上界があります. さらに, Zornの補題の主張通りに極大元があります.
4. おわりに
説明が分かりづらいところもあると思いますが, 誰かの理解の一助になれば幸いです. (あと, XY-pic使うの難しかったです. )
