うさぎでもわかる離散数学　第5羽　半順序・ハッセ図

こんにちは！　ももやまです！

今回は半順序・ハッセ図についてまとめてみたいと思います。

１．半順序関係・集合
２．ハッセ図
- 例題1
- 解説1
３．半順序集合の8つの言葉の定義
- (1) 上界（じょうかい）　upper bound
４．さいごに

前回の第4羽はこちらから↓

www.momoyama-usagi.com

１．半順序関係・集合

集合 $S$ 上の関係 $R$ が次の3つを満たすとき、半順序ということができます。

関係 $R$ が反射性を満たす
関係 $R$ が反対称性を満たす
関係 $R$ が推移性を満たす

この３つってどんな関係だっけと思った方は第4羽の二項関係をご覧ください。

また、半順序関係を表す際には、記号 $R$ ではなく、 $\leqq$ , $\preceq$ , $\subseteq$ などの特殊な記号を使うことが多いです。

集合 $S$ に対して、半順序関係 $\preceq$ が定められたものを半順序集合といい、 $(S,\preceq)$ と表します。

２．ハッセ図

半順序関係を比較するためにハッセ図というものが使われます。ハッセ図のルールを下に示します。

☆ルール☆

集合 $S$ の各要素を頂点とする
半順序 $\preceq$ の大きい要素ほど上に来る
$x \preceq y$ で、 $x$ から $y$ へ遠回りで行くルートがないときだけ2点を頂点で結ぶ

この3つのルールがあります。ルール3は少しわかりにくいので具体例で説明します。

例えば $x \preceq y$ だけが定義されていたら $x$ と $y$ の2点だけを結べばOKです。

f:id:momoyama1192:20190519084512g:plain

図１：遠回りなしパターン

ですが、 $x \preceq y$ の他に $x \preceq z$ , $z \preceq y$ のような推移性を満たすように第3の頂点 $z$ がある場合は、 $x$ から $y$ の遠回りルートができてしまいますね。

このようなときは $x \preceq y$ を直接結んではいけません。（図２）

f:id:momoyama1192:20190519084513g:plain

図２：遠回りありパターン

この3つのルールを踏まえて試しに1つハッセ図を書いてみます。

例えば、集合 $S$ を $S = \{a,b,c,d,e\}$ とし、 $a \preceq c$ , $d \preceq c$ , $b \preceq e$ , $a \preceq b$ , $c \preceq e$ の5つの半順序 $\preceq$ が定義されているとします。

このときのハッセ図は図３のようになります。わかりやすく色もつけてみたので参考までにしてください。

f:id:momoyama1192:20190519084514g:plain

図３：集合 $S$ のハッセ図

図を見ると、どの要素が比較できて、どの要素が比較できないかが見ただけでわかります。

例えば $d$ より大きい要素は $c,e$ の2つですね。

（ $d \preceq c$ , $c \preceq e$ より $d \preceq e$ となる[推移性]）

また、 $a,b$ の2つの要素とは $d$ からたどるときに上がったり下がったりするので比較可能とは言えません。

（ $d \preceq c$ と $a \preceq c$ を比べても $a$ と $d$ のどっちが大きいかはわかりませんよね。）

それでは、例題を1つ解いてみましょう。

例題1

集合 $S$ を $S = \{a,b,c\}$ とする。

(1) 集合 $S$ のべき集合 $2^{S}$ を求めなさい。
(2) べき集合 $2^{S}$ 上の包含関係 $\subseteq$ は半順序関係を持つことを示しなさい。
(3) 半順序集合 $(2^{S},\subseteq)$ のハッセ図を書きなさい。

解説1

(1)

第1羽の復習です。
$2^{S} = \{\phi,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$

(2)

半順序関係を持つということは、反射性・反対称性・推移性の3つを持つことを示せばよい。
(i) $\forall A \in 2^{S}$ に対して、 $A \subseteq A$ が成立する。よって包含関係 $\subseteq$ は反射性を満たす。

（ $2^{S}$ のどの集合を持ってきても、自分自身とは必ず部分集合）

(ii) $\forall A ,\forall B \in 2^{S}$ に対して、 $A \subseteq B$ かつ $B \subseteq A$ ならば、 $A=B$ が成り立つので、包含関係 $\subseteq$ は反対称性も満たす。

(iii) $\forall A ,\forall B,\forall C \in 2^{S}$ に対して、 $A \subseteq B$ かつ $B \subseteq C$ ならば $A \subseteq C$ が成り立つので、、包含関係 $\subseteq$ は推移性も満たす。

(i),(ii),(iii) より、包含関係 $\subseteq$ は半順序関係を持つことが証明された。

※ $\forall A\in 2^{S}$ などの式を「 $2^{S}$ のすべての要素 $A$ に対して」と日本語で説明してももちろんOKです。

しかし、大学の先生は記号をつかって証明を説明することが多いです。

(3)

f:id:momoyama1192:20190519084515g:plain

となる。

半順序 $\subseteq$ が全部で12箇所あるので線を書き漏らしたり余計な線を書かないように十分注意すること。

３．半順序集合の8つの言葉の定義

半順序集合を $X$ とし、 $X$ の部分集合を $S$ とします。

具体例として、下の図で表される半順序集合を $X = \{a,b,c,d,e,f,g\}$ , 部分集合を $S = \{b,c,d\}$ とします。

今回は、わかりやすく部分集合の要素を囲っています。もし囲ってなかったら囲うとわかりやすくなると思うのでぜひ囲ってください。

f:id:momoyama1192:20200529143431g:plain

(1) 上界（じょうかい）　upper bound

すべての $y \in S$ に対して、 $y \preceq x$ を満たすような $x \in X$ のこと

つまり、 $X$ の要素の中で、 $S$ のどの要素よりも大きい、もしくは $S$ と同じ要素のものが上界となります。

f:id:momoyama1192:20200529143436g:plain

上図の例場合、 $e,f,g$ の3つはどの $S$ の要素よりも大きいというのがわかりますよね。よって上界は $e,f,g$ となります。

(2) 下界（かかい）　lower bound

すべての $y \in S$ に対して、 $x \preceq y$ を満たすような $x \in X$ のこと

つまり、 $X$ の要素の中で、 $S$ のどの要素よりも小さい、もしくは $S$ と同じ要素のものが下冥となります。ちなみに「げかい」ではなく「かかい」ですよ。

f:id:momoyama1192:20200529143442g:plain

上の図の場合、まず $a$ は $S$ のどの要素よりも小さいと言えますよね。さらに $b$ に関しても $S$ のどの要素よりも小さい、もしくは $b$ と同じといえますよね。よって下界は $a,b$ となります。

(3) 最大元（さいだいげん）greatest element

すべての $y \in S$ に対して、 $y \preceq x$ を満たすような $x \in S$

$S$ の要素の中で、 $S$ の他のどの要素よりも大きいものが最大元となります。最大元は存在する場合、1つしかありません。

f:id:momoyama1192:20200529143446g:plain

上の図の場合、 $c,d$ の要素はどっちが大きいかはわかりませんよね。よって最大元はありません。

(4) 最小元（さいしょうげん）smallest element

すべての $y \in S$ に対して、 $x \preceq y$ を満たすような $x \in S$

$S$ の要素の中で、 $S$ の他のどの要素よりも小さいものが最小元となります

f:id:momoyama1192:20200529143450g:plain

最大元と同じく最小元は存在する場合、1つしかありません。

今回の場合は $b$ が他の $S$ の要素である $c$ , $d$ に比べて小さいですね。そのため、最小元は $b$ となります。

(5) 上限（じょうげん） [最小上界]　supremum

すべての $S$ の上界 $y \in S$ に対して、 $x \preceq y$ を満たす $x\in S$

$S$ の上界の要素の中で、 $S$ の他のどの上界よりも小さいものです。存在する場合は1つしかありません。

f:id:momoyama1192:20200529143455g:plain

上の図の場合、上界 $e,f,g$ の中で、 $e$ は、他の2つの上界の要素と比べて小さいというのがわかりますよね。よって上限は $e$ となります。

(6) 下限（かげん） [最大下界]　infimum

すべての $S$ の下界 $y \in S$ に対して、 $y \preceq x$ を満たす $x\in S$

$S$ の下界の要素の中で、 $S$ の他のどの下界よりも大きいもの。存在する場合は1つのみ。

f:id:momoyama1192:20200529144427g:plain

上の図の場合、下界 $a,b$ の中で $b$ は $a$ よりも大きいことがわかりますよね。よって下限は $b$ となります。

(7) 極大元（きょくだいげん）maximal element

すべての $y \in S$ に対して、 $x \preceq y$ ならば $x = y$ を満たす $x \in S$

$S$ の要素の中で、 $S$ の他の要素より大きいものがないもの、と言えます。

上の図の場合、 $c,d$ の2つよりも大きい $S$ の要素は見つかりませんよね。よって極大元は $c,d$ となりますよね。

f:id:momoyama1192:20200529143510g:plain

(8) 極小元（きょくしょうげん）minimum element

すべての $y \in S$ に対して、 $y \preceq x$ ならば $x = y$ を満たす $x \in S$

$S$ の要素の中で、 $S$ の他の要素より小さいものがないもの、と言えます。

f:id:momoyama1192:20200529144432g:plain

上の図の場合、 $b$ より小さい $S$ の要素は見つかりませんよね。よって極小元は $b$ となります。

この8つはよく出てくるので定義や意味を覚えておきましょう。

特に最大元と極大元、最小元と極小元は間違えやすいので気をつけましょう！

では、また例題を1つ解いてみましょう。

例題2

半順序 $\preceq$ に対して、下の図で表される半順序集合 $X$ を、 $X = \{a,b,c,d,e,f,g,h,i\}$ とし、 $X$ の部分集合 $S$ を、 $S = \{d,e,f,i\}$ とする。

f:id:momoyama1192:20190519084516g:plain

(A) 要素 $d$ について、
(1) $d \preceq x$ を満たすような $x$
(2) $x \preceq d$ を満たすような $x$
(3) $\lnot ((x \preceq d) \lor (d \preceq x) )$ を満たすような $x$
をすべて求めなさい。ただし、 $x \in X$ とする。

(B) $S$ の (1) 上界, (2) 下界, (3) 最大元, (4) 最小元, (5) 上限, (6) 下限, (7) 極大元, (8) 極小元をすべてもとめなさい。ただし、存在しない場合は「×」と答えること。

(A) のヒント
(1)は、要素 $d$ より $\preceq$ の関係で大きい、もしくは同じもの
(2)は、要素 $d$ より $\preceq$ の関係で小さい、もしくは同じもの
(3)は、要素 $d$ からは $\preceq$ の関係で比較できないもの

のことを表しています。

解答2

(A)
(1) $a,b,d$ が答え。同じ要素の $d$ を忘れないように。
(2) $d,f,g,h,i$
$h \preceq f$ と $f \preceq d$ より、 $h \preceq d$ であり、 $i \preceq g$ と $g \preceq d$ より、 $i \preceq d$ であることがわかる。
(3) $c,e$ が答え。いずれもハッセ図をたどるときに上がったり降りたりしてますよね。