Hasse図
from 論理と集合から始める数学の基礎 読書会
ハッセ図(Hasse Diagram)
有限順序集合$ (U,\le)の可視化方法の一つ
$ Uの要素を点で表す
ある要素$ aからその直後の要素$ bに線分を引く
$ aの直後に$ bがくる$ :\iff a< b\land\forall x\in U.(a\le x\le b\implies a=x\lor x=b)
つまり、経由地点があるルートを飛ばして矢印を書くのは禁止takker.icon
$ bは$ aより上の位置に書く
「直後の要素」という二項関係による有向グラフと言える
もしくは、半順序集合の有向グラフに以下の制限を加えて見やすくしたものともいう
1. 自分自身への矢印を消す
2. 直後の要素を2個以上たどって到達できる要素への矢印を消す
3. 矢印が全て上向きになるよう要素を配置する
4. 矢印の代わりに線分にする
例9.5 Hasse図の例
全順序集合$ (\{1,2,3,4\},\le)
https://scrapbox.io/files/65f39b1f452f540026652627.svg
半順序集合$ (\{1,2,3,4,6,9,12,18\},\backslash)
ここで、$ b\backslash a:\iff\exists k\in\Z;a=kbで、$ aが$ bで割り切れる時真を示す
テキストでは$ b|aが使われるが、ドナルド・クヌースの記法に倣ってみたtakker.icon
https://scrapbox.io/files/65f39deaf71f0e0023f846ee.svg
全順序集合だと一直線に並ぶことがわかる
問：空でない有限全順序集合のHasse図が一直線上に並ぶことを示せ
code:9.5.1.tikz(tex)
\begin{document}
\begin{tikzpicture}domain=0:4
\tikzset{
every node/.style={circle,draw,inner sep=2pt,fill=white},
every path/.style={very thick},
}
\draw (0,0) nodelabel={right:$1$}{}
-- ++(0,1) nodelabel={right:$2$}{}
-- ++(0,1) nodelabel={right:$3$}{}
-- ++(0,1) nodelabel={right:$4$}{};
\end{tikzpicture}
\end{document}
code:9.5.2.tikz(tex)
\begin{document}
\begin{tikzpicture}domain=0:4
\tikzset{
every node/.style={circle,draw,inner sep=2pt,fill=white},
every path/.style={very thick},
}
\coordinate (left) at (-2^-0.5,2^-0.5);
\coordinate (right) at (2^-0.5,2^-0.5);
\draw (0,0) nodelabel={right:$1$}(1){}
-- ++(right) nodelabel={right:$2$}(2){}
-- ++(right) nodelabel={right:$4$}(4){}
-- ++(left) nodelabel={right:$12$}(12){};
\draw (1)
-- ++(left) nodelabel={right:$3$}(3){}
-- ++(left) nodelabel={right:$9$}(9){}
-- ++(right) nodelabel={right:$18$}(18){};
\draw (3)
-- ++(right) nodelabel={right:$6$}(6){};
\draw (2) -- (6) -- (12);
\draw (6) -- (18);
\end{tikzpicture}
\end{document}