Hasse図

同義語：Hasse diagramハッセ図

概要

前提知識: 半順序集合, 有向グラフ, 有向非巡回グラフ

Hasse図（Hasse diagram）は、半順序集合の大小関係を、「すぐ上にある」という被覆関係だけを線で結んで描いた図である。$x< y$ のすべての組に線を引くと、推移律から分かる線まで描くことになり図が埋まってしまう。Hasse 図はそうした線を省き、$x$ のすぐ上に $y$ があるときだけ $x$ を下、$y$ を上に置いて線分で結ぶ。順序は「下から上へ線をたどれること」として読み取る。
有限の半順序集合では、この省略で情報は失われない。主定理（thm-hasse-main）は、有限集合の上の半順序と、有向閉路も「回り道で代わりのきく辺」ももたない有向グラフとが、Hasse 図をとる対応でちょうど一対一に対応することを述べる。さらに、直積の Hasse 図は成分の Hasse 図の「箱型の積」になること（thm-hasse-product）を示し、冪集合や約数の順序の図がなぜ立方体や格子の形になるかを説明する。

定義

$(P,\le)$ を半順序集合とし、$x\le y$ かつ $x\ne y$ を $x< y$ と書く。

被覆関係とHasse図

$x,y\in P$ について、$x< y$ であり、かつ $x< z< y$ となる $z\in P$ が存在しないとき、$y$ は $x$ を被覆するといい、$x\lessdot y$ と書く。
頂点の集合を $P$、有向辺の集合を $\{(x,y)\in P\times P\mid x\lessdot y\}$ とする有向グラフを $(P,\le)$ の Hasse図 といい、$H(P)$ と書く。辺 $(x,y)$ を $x\to y$ と書く。
$H(P)$ の辺の向きを忘れた無向グラフを $(P,\le)$ の被覆グラフ（cover graph）という。

被覆関係は半順序集合の定義「被覆関係」と同じものである。紙の上に描くときは、$P$ の各元を平面上の点に置き、$x\lessdot y$ ならば $y$ の点を $x$ の点より真に高い位置に置いて、両者を線分で結ぶ。線分はその両端以外の点を通らないようにする。この描き方では辺の向きは「下から上」と決まっているので矢印を省く。描いた絵も Hasse 図と呼ぶ。有向グラフとしての $H(P)$ は描き方によらず $P$ だけで決まり、絵はその一つの表し方である（KT17 §6.1, pp. 114–116 は被覆グラフを上の規則で描いた絵を Hasse 図と呼んでいる）。
以下の有向グラフ $G=(V,A)$ は、頂点の集合 $V$ と有向辺の集合 $A\subset V\times V$ の組で、同じ向きの辺は高々 1 本である。有向歩道・有向道・有向閉路・到達可能性 $u\rightsquigarrow v$（長さ $0$ の歩道も含め、$u$ から $v$ への有向歩道があること）は有向グラフの記事の定義に従い、長さは辺の本数で数える。ループ $(v,v)$ は長さ $1$ の有向閉路である。

冗長な辺

有向グラフ $G=(V,A)$ の辺 $u\to v$ について、$u$ から $v$ への長さ $2$ 以上の有向道があるとき、この辺は冗長であるという。

この用語は有向非巡回グラフの定義「推移的簡約」と同じである。

直感

Hasse 図は順序の「骨組み」である。$x\le y$ を確かめたいときは、$x$ から線を上へたどって $y$ に着けるかを見ればよい。比較できない 2 元は、どちらからどちらへも上向きにたどれない 2 点として見える。最小元は一番下の 1 点、極大元は上に線が出ていない点である。描き方には自由度があり、同じ半順序集合でも見た目の違う絵がいくつも描ける。逆に、見た目が違っても有向グラフとして同型なら、元の半順序集合は順序同型である（cor-hasse-isomorphism）。

例

鎖・反鎖・数の大小

$\{0,1,\dots,n\}$ に通常の大小を入れた鎖の Hasse 図は $0\to1\to\cdots\to n$ の 1 本の道である。整数全体 $\mathbb{Z}$ でも $k\lessdot k+1$ だけが被覆なので、Hasse 図は両側に無限に延びた道である。比較できる組のない反鎖の Hasse 図は辺のないグラフである。有理数全体 $\mathbb{Q}$ では $p< q$ なら $p<(p+q)/2< q$ なので被覆が一つもなく、Hasse 図も辺のないグラフになる（半順序集合の注意「有限性が本質的である理由：稠密な順序との対比」）。

冪集合と立方体

$X=\{1,2,3\}$ の冪集合 $\mathcal{P}(X)$ を包含で並べると、$A\lessdot B$ は「$B$ が $A$ にちょうど 1 元を加えたもの」のことである（$A\subsetneq C\subsetneq B$ となる $C$ がないのは $|B\setminus A|=1$ のときに限るので）。Hasse 図は次のとおりで、立方体の 8 頂点と 12 辺の形をしている。
$$ \xymatrix{ & \{1,2,3\} & \\ \{1,2\} \ar@{-}[ur] & \{1,3\} \ar@{-}[u] & \{2,3\} \ar@{-}[ul] \\ \{1\} \ar@{-}[u] \ar@{-}[ur] & \{2\} \ar@{-}[ul] \ar@{-}[ur] & \{3\} \ar@{-}[ul] \ar@{-}[u] \\ & \emptyset \ar@{-}[ul] \ar@{-}[u] \ar@{-}[ur] & } $$
$30$ の正の約数 $\{1,2,3,5,6,10,15,30\}$ を整除関係で並べたものも同じ絵になる。$p_1=2$、$p_2=3$、$p_3=5$ とおくと、$A\mapsto\prod_{a\in A}p_a$（$\emptyset\mapsto1$）は素因数分解の一意性により $A\subset B$ と「$\prod_{a\in A}p_a$ が $\prod_{b\in B}p_b$ を割り切る」ことを対応させる全単射、すなわち順序同型であり、順序同型は被覆を被覆に移すからである。

五角形と段のそろわない図

5 元 $\{0,a,b,c,1\}$ に、$0< a< b<1$、$0< c<1$ から反射律と推移律で決まる関係だけを入れた半順序集合 $N_5$ を考える（$c$ は $a,b$ と比較できない）。被覆は $0\lessdot a\lessdot b\lessdot1$ と $0\lessdot c\lessdot1$ の 5 組で、Hasse 図は五角形になる。
$$ \xymatrix{ & 1 & \\ b \ar@{-}[ur] & & \\ a \ar@{-}[u] & & c \ar@{-}[uul] \\ & 0 \ar@{-}[ul] \ar@{-}[ur] & } $$
$0$ から $1$ への上向きの道は長さ $3$ のものと長さ $2$ のものがある。$0< a< b<1$ も $0< c<1$ もそれ以上細かくできない鎖であり、極大な鎖の長さがそろっていない。これは prop-hasse-graded の結論が成り立たない例である。

有限位相空間の図

有限位相空間は特殊化の前順序で有限前順序集合と同一視され、$T_0$ な有限空間は有限半順序集合と同じものである（有限位相空間）。そこで有限空間はふつう Hasse 図で描かれ、閉点は極小元、最小開近傍が 1 点の開点は極大元として図に現れる。

反例：被覆グラフに三角形はない

3 頂点が互いに辺で結ばれた三角形は、どの半順序集合の被覆グラフにも現れない。実際、3 元 $x,y,z$ のどの 2 元も被覆の関係にあれば、どの 2 元も比較できるので、並べ替えて $x< y< z$ としてよい。すると $x,z$ の間の辺は $x\lessdot z$ を意味するが、$x< y< z$ がこれに反する。とくに三角形を含む無向グラフは被覆グラフではない（KT17 §6.2, p. 121 はこの事実を述べている）。

主定理：Hasse図と順序の一対一対応

有向閉路をもたない有向グラフでは、有向歩道はつねに有向道である（有向非巡回グラフの定義の後の段落。同じ頂点を 2 度通れば、その間の部分が有向閉路になる）。とくに長さが正の有向歩道の始点と終点は異なる。以下ではこの事実を使う。

Hasse図となる有向グラフ

集合 $V$ を固定する。

$V$ 上の任意の半順序 $\le$ について、Hasse 図 $H(V,\le)$ は有向閉路も冗長な辺ももたない。
$V$ 上の有向グラフ $G$ が有向閉路も冗長な辺ももたないとき、到達可能性 $u\le_G v:\iff u\rightsquigarrow v$ は $V$ 上の半順序であり、その Hasse 図は $G$ に等しい。
$V$ が有限なら、$\le\ \mapsto H(V,\le)$ と $G\mapsto\ \le_G$ は、$V$ 上の半順序全体と、$V$ 上の有向閉路も冗長な辺ももたない有向グラフ全体との間の、互いに逆な全単射である。

1。 Hasse 図の辺 $x\to y$ は $x< y$ を意味する。有向閉路 $x_0\to x_1\to\cdots\to x_n=x_0$（$n\ge1$）があったとする。$x_0< x_1$ であり、$x_1< x_2<\cdots< x_n$ と推移律から $x_1\le x_n=x_0$ である。反対称律から $x_0=x_1$ となり、$x_0< x_1$ に反する（$n=1$ のときは $x_0< x_1=x_0$ がすでに矛盾である）。次に、辺 $x\to y$（$x\lessdot y$）と長さ $k\ge2$ の有向道 $x=z_0\to z_1\to\cdots\to z_k=y$ があったとする。$x< z_1$ であり、$z_1< z_2$ と $z_2\le z_k=y$ から $z_1< y$ である。よって $x< z_1< y$ となり、$x\lessdot y$ に反する。したがって冗長な辺はない。
2。長さ $0$ の歩道があるので $\le_G$ は反射的であり、歩道をつなげれば推移的である。$u\le_G v$、$v\le_G u$、$u\ne v$ とすると、2 本の歩道をつないだ $u$ から $u$ への歩道は長さが正で、始点と終点が等しい。これは冒頭の事実に反するので、$\le_G$ は反対称的であり、半順序である。
Hasse 図が $G$ に等しいことを示す。まず $G$ の辺 $u\to v$ をとる。ループは有向閉路なので $u\ne v$ で、$u<_G v$ である。$u<_G w<_G v$ となる $w$ があれば、$u\rightsquigarrow w$ と $w\rightsquigarrow v$ の歩道はどちらも長さ $1$ 以上で、つないだ歩道は長さ $2$ 以上の $u$ から $v$ への歩道、すなわち有向道になる。これは辺 $u\to v$ が冗長であることを意味し、仮定に反する。よって $u\lessdot_G v$ である。逆に $u\lessdot_G v$ とする。$u\ne v$ なので長さ $k\ge1$ の歩道 $u=y_0\to y_1\to\cdots\to y_k=v$ がある。$u\ne y_1$ なので $u<_G y_1$ であり、$y_1\le_G v$ である。$y_1\ne v$ なら $u<_G y_1<_G v$ となって被覆に反するので、$y_1=v$ であり、$u\to v$ は $G$ の辺である。
3。 1 により $H(V,\le)$ は右辺の集合に属し、2 により $G\mapsto\ \le_G\ \mapsto H(V,\le_G)$ は恒等写像である。残りは、$V$ が有限のとき $H(V,\le)$ の到達可能性がもとの $\le$ に一致することである。$H(V,\le)$ で $u\rightsquigarrow v$ であることは「$u=v$ であるか、被覆の列 $u=x_0\lessdot x_1\lessdot\cdots\lessdot x_n=v$ がある」ことであり、これが $u\le v$ と同値であることは半順序集合の命題「有限半順序集合における被覆関係からの復元」である。$\square$

1 と 2 は $V$ が無限でも成り立つ。3 で有限性を使ったのは復元の命題だけであり、その証明は区間 $\{z\mid x\le z\le y\}$ が有限であることしか使わない。したがって、すべての区間が有限な半順序集合（$\mathbb{Z}$、$\mathbb{N}\times\mathbb{N}$ の直積順序など）でも、Hasse 図の到達可能性はもとの順序に一致する。$\mathbb{Q}$ ではこれが崩れる（ex-hasse-chains）。

Hasse図による同型の判定

有限半順序集合 $P,Q$ と全単射 $f\colon P\to Q$ について、$f$ が順序同型であることと、$f$ が Hasse 図の同型（$x\to y$ が辺であることと $f(x)\to f(y)$ が辺であることが同値）であることは同値である。

順序同型 $f$ は $<$ を保ち、逆写像も $<$ を保つので、「$x< z< y$ となる $z$ がある」ことと「$f(x)< w< f(y)$ となる $w$ がある」ことは $w=f(z)$ で対応する。よって $x\lessdot y\iff f(x)\lessdot f(y)$ である。逆に $f$ が Hasse 図の同型なら、歩道は歩道に移り、逆も同じなので、到達可能性が保たれる。thm-hasse-main の 3 により有限半順序集合では到達可能性がもとの順序なので、$x\le y\iff f(x)\le f(y)$ である。$\square$

この系を有向非巡回グラフの定理「推移的簡約の一意性」と組み合わせると、有限の有向非巡回グラフ $D$ の到達可能性を半順序とみたときの Hasse 図は、$D$ の冗長な辺をすべて除いた推移的簡約 $D^{\circ}$ である。実際、$D^{\circ}$ は $D$ の部分グラフなので有向閉路をもたず、$D^{\circ}$ の辺が $D^{\circ}$ の中で長さ $2$ 以上の有向道をもてばその道は $D$ の道でもあって辺は $D$ で冗長になるので、$D^{\circ}$ は冗長な辺をもたない。同定理により $D^{\circ}$ と $D$ の到達可能性は等しいので、thm-hasse-main の 2 から主張が従う。

直積と階数

直積順序の Hasse 図

半順序集合 $P,Q$ の直積 $P\times Q$ に、$(a,b)\le(a',b')\iff a\le a'$ かつ $b\le b'$ で定まる直積順序（順序集合）を入れる。

直積の Hasse 図

$(a,b)\lessdot(a',b')$ であるための必要十分条件は、「$a\lessdot a'$ かつ $b=b'$」または「$a=a'$ かつ $b\lessdot b'$」が成り立つことである。したがって $H(P\times Q)$ は、$H(P)$ の辺を $Q$ の元の数だけ並べたものと、$H(Q)$ の辺を $P$ の元の数だけ並べたものを合わせた有向グラフ（グラフの箱型の積）である。

十分性。 $a\lessdot a'$、$b=b'$ とする（他方も同じ）。$(a,b)<(a',b)$ である。$(a,b)<(c,d)<(a',b)$ となる $(c,d)$ があれば、$b\le d\le b$ から $d=b$、$a\le c\le a'$ であり、$(c,b)$ は両端と異なるので $c\ne a$、$c\ne a'$、すなわち $a< c< a'$ となって $a\lessdot a'$ に反する。
必要性。 $(a,b)\lessdot(a',b')$ とすると $a\le a'$、$b\le b'$ で、少なくとも一方は等号でない。両方とも等号でないなら、$(a,b)<(a',b)<(a',b')$（前の不等号は $a\ne a'$、後の不等号は $b\ne b'$ による）となって被覆に反する。よってちょうど一方が等号であり、たとえば $b=b'$、$a< a'$ である。$a< c< a'$ となる $c$ があれば $(a,b)<(c,b)<(a',b)$ となって被覆に反するので、$a\lessdot a'$ である。$\square$

この定理は有限性を使わない。たとえば $\mathbb{N}\times\mathbb{N}$ の Hasse 図は、各点から右と上へ 1 本ずつ辺の出る格子である。

冪集合と約数の Hasse 図

$n$ 元集合の冪集合を包含で並べた Hasse 図は $n$ 次元立方体のグラフ（頂点 $\{0,1\}^n$、1 成分だけ異なる組を結ぶ）と同型で、辺は $n2^{n-1}$ 本ある。
正の整数 $N=p_1^{a_1}\cdots p_m^{a_m}$（$p_i$ は相異なる素数）の正の約数を整除で並べると、$d\lessdot d'$ は「$d'=dp$ となる素数 $p$ がある」ことであり、Hasse 図の辺は $\sum_{i=1}^m a_i\prod_{j\ne i}(a_j+1)$ 本ある。

1：部分集合 $A$ にその特性関数 $(\mathbf 1_A(1),\dots,\mathbf 1_A(n))$ を対応させると、包含は成分ごとの大小になるので、冪集合は 2 元の鎖 $\{0<1\}$ の $n$ 個の直積と順序同型である。thm-hasse-product を繰り返し使うと、被覆はちょうど 1 成分が $0$ から $1$ に変わる組である。辺の本数は、変える成分の選び方 $n$ 通りと残り $n-1$ 成分の値 $2^{n-1}$ 通りの積である。
2：$d=\prod p_i^{e_i}$ に指数の組 $(e_1,\dots,e_m)$ を対応させると、素因数分解の一意性により整除は成分ごとの大小になるので、約数の順序は鎖 $\{0<1<\cdots< a_i\}$ の直積と順序同型である。鎖の被覆は $e\lessdot e+1$ なので、thm-hasse-product により被覆はちょうど 1 つの指数が $1$ 増える組、すなわち $d'=dp_i$ である。$i$ 番目の指数を増やす辺は、$e_i\in\{0,\dots,a_i-1\}$ の $a_i$ 通りと、他の指数の $\prod_{j\ne i}(a_j+1)$ 通りの積の本数ある。$\square$

$N=12=2^2\cdot3$ では $2\cdot2+1\cdot3=7$ 本で、半順序集合の例「12の正の約数と整除関係」の 7 組と一致する。

階数関数と描き方

階数関数と極大な鎖の長さ

有限半順序集合 $P$ 上の関数 $r\colon P\to\mathbb{Z}$ が、$x\lessdot y$ ならば $r(y)=r(x)+1$ を満たすとする。このとき $x\le y$ なら、区間 $[x,y]:=\{z\in P\mid x\le z\le y\}$ の中で包含について極大な鎖は、すべて $r(y)-r(x)+1$ 個の元からなる。

$C$ を $[x,y]$ の極大な鎖とする。$x$ と $y$ は $[x,y]$ のどの元とも比較できるので、$C$ が含まなければ加えても鎖のままであり、極大性から $x,y\in C$ である。$P$ は有限なので $C$ は有限で、$C=\{x=z_0< z_1<\cdots< z_k=y\}$ と並べられる。各 $i$ で $z_{i-1}\lessdot z_i$ である。実際 $z_{i-1}< w< z_i$ となる $w$ があれば、$w\in[x,y]$ で、$j< i$ なら $z_j\le z_{i-1}< w$、$j\ge i$ なら $w< z_i\le z_j$ なので $C\cup\{w\}$ は鎖になり、極大性に反する。よって $r(z_i)=r(z_{i-1})+1$ で、足し合わせると $r(y)=r(x)+k$、すなわち $C$ の元の個数は $k+1=r(y)-r(x)+1$ である。$\square$

冪集合では $r(A)=|A|$、約数の順序では $r(d)=$「$d$ の素因数の個数（重複を数える）」がこの条件を満たす。五角形 $N_5$（ex-hasse-pentagon）では、この条件を満たす $r$ があれば $a,b$ を通って $r(1)=r(0)+3$、$c$ を通って $r(1)=r(0)+2$ となり矛盾するので、そのような $r$ はない。$r$ がある半順序集合は、Hasse 図を $r$ の値ごとの段に並べて描ける。$r$ がなくても、次のとおり絵はいつでも描ける。

Hasse図はいつでも描ける

有限半順序集合 $P$ について、単射 $\phi\colon P\to\mathbb{R}^2$、$\phi(x)=(s(x),h(x))$ で、$x\lessdot y$ ならば $h(x)< h(y)$ であり、かつ線分 $\phi(x)\phi(y)$ が両端以外の $\phi(z)$ を通らないものがある。

要点：高さ $h(x)$ を「$x$ を最大元とする鎖の元の個数の最大値」（$P$ は有限なので定まる）にとり、横の位置 $s$ を、高さのそろわない 3 点が一直線に並ばないように 1 点ずつ選ぶ。

詳しい証明を開く

$x< y$ なら、$x$ を最大元とする元の個数 $h(x)$ の鎖に $y$ を加えると、元の個数 $h(x)+1$ の $y$ を最大元とする鎖になるので $h(y)\ge h(x)+1$ である。$P=\{x_1,\dots,x_n\}$ と番号を付け、$s(x_1),\dots,s(x_n)$ を相異なる実数として順に選ぶ。$s(x_k)$ を選ぶとき、$i,j< k$ の各組について、高さ $h(x_i),h(x_j),h(x_k)$ がすべて等しくはないのに 3 点 $\phi(x_i),\phi(x_j),\phi(x_k)$ が一直線に並ぶような $s(x_k)$ の値は高々 1 つである。$h(x_i)\ne h(x_j)$ なら、$\phi(x_i),\phi(x_j)$ を通る直線は水平でなく、高さ $h(x_k)$ の水平線と 1 点で交わるからであり、$h(x_i)=h(x_j)\ne h(x_k)$ なら、$\phi(x_i),\phi(x_j)$ を通る直線は水平で $\phi(x_k)$ を通らないからである。除く値は有限個なので、$s(x_k)$ を選べる。こうして高さのそろわない 3 点はどれも一直線に並ばない。$x\lessdot y$ の線分は $h(x)< h(y)$ なので水平でなく、その上に第 3 の点 $\phi(z)$ があれば、高さのそろわない 3 点が一直線に並ぶことになるので、そのような点はない。$\phi$ が単射であることは、$s$ の値が相異なることから従う。$\square$

反例の表

thm-hasse-main の 2・3 の仮定を 1 つずつ外した例である。

外す条件	反例	成り立たなくなること
$V$ が有限（3）	$\mathbb{Q}$ 上の通常の大小と、$\mathbb{Q}$ 上の等号だけの順序	3 の単射性：どちらの Hasse 図も辺のないグラフになる
有向閉路がない（2）	3 頂点の有向閉路 $a\to b\to c\to a$	到達可能性が反対称律を満たさず、Hasse 図になる半順序がない
冗長な辺がない（2）	3 本の辺 $a\to b$、$b\to c$、$a\to c$	到達可能性 $a< b< c$ の Hasse 図は $a\to b\to c$ で、もとのグラフと異なる

1 行目：$\mathbb{Q}$ の通常の順序は被覆をもたず（ex-hasse-chains）、等号だけの順序は $x< y$ となる組がないので、どちらの Hasse 図も辺がない。2 行目：$a$ から出る辺は $a\to b$ だけで、$b,c$ についても同じなので、どの辺にも代わりの長い道はなく冗長な辺はない。しかし $a\rightsquigarrow b$ と $b\rightsquigarrow a$ がともに成り立つ。1 によりどの半順序の Hasse 図も有向閉路をもたないので、このグラフはどの半順序の Hasse 図でもない。3 行目：有向閉路はないが、辺 $a\to c$ には長さ $2$ の有向道 $a\to b\to c$ があり冗長である。

補足

向きの流儀。 大きい元を上に置くのが標準だが、双対順序（大小を逆にした順序）の Hasse 図は、もとの Hasse 図の辺の向きをすべて逆にしたもの、つまり絵を上下に反転したものである。被覆関係は双対順序で向きが逆になるだけなので、被覆グラフは同じである。
単調写像との関係。 単調写像は被覆を被覆に移すとは限らない（$\{0<1<2\}$ を 1 点に潰す写像など）ので、Hasse 図のグラフ準同型ではない。一方、有限半順序集合からの写像が単調であることは、被覆 $x\lessdot y$ のたびに $f(x)\le f(y)$ となることを確かめれば足りる（単調写像の命題「整数の区間からの写像」の後の段落）。