離散数学

順序集合 と 束落合 秀也

前回の復習: 関係 と 関数
• キーワード
2項関係, 単一集合上の関係, 相等性, 全体関係, 空関係,逆関係, 関係の性質, 同値関係, 同値類，分割，商集合,半順序関係, 関数, 単射, 全射, 全単射• 表現方法• 座標図、行列、矢線図、有向グラフ

1a2

b3cRA

• 記法
• aRb, (a,b) ∈ R ⊂ A×B,
[ s ], S / R, f: A→B

B

12342

（復習） 関係の性質• Rを集合A上の関係とし、以下、a ∈A, b ∈ Aとする。
• aRa• Rは反射的(reflexive)である• aRb  bRa• Rは対称的 (symmetric)である• aRb かつ bRa  a=b• Rは反対称的 (anti-symmetric)である• aRb かつ bRc  aRc• Rは推移的 (transitive)である
3

今日のテーマ： 順序集合 と 束• 半順序集合• 直前、直後、図式• 比較可能、全順序•束• 結び、交わり、上限、下限• 半束• 順序の中の束、束の上の順序

4

今日のテーマ： 順序集合 と 束• 半順序集合• 直前、直後、図式• 比較可能、全順序•束• 結び、交わり、上限、下限• 半束• 順序の中の束、束の上の順序

5

半順序集合 (Partially Ordered Set)
• 集合S上の関係Rが、• 反射的である• 反対称的である• 推移的である( aRa )
( aRb かつ bRa  a=b )( aRb かつ bRc  aRc )であれば、この関係を、S上の半順序と呼ぶ。
• S上の半順序を持つ集合Sを、半順序集合または順序集合(partially ordered set, poset)と呼ぶ

6

例1：「自然数全体」の集合 と ≦• 大小関係 ≦ は、自然数全体N上の半順序である• 理由 (a, b, c ∈Nとする)• a≦a であるから、 ≦ は反射的である• a≦bかつb≦aであれば、a=bであるから、 ≦は反対称的である• a≦bかつb≦cであれば、a≦cであるから、≦は推移的である（*) 実際、≦ は実数の任意の部分集合上の半順序である
7

例2：「集合」の集合 と ⊂• 任意の集合族（集合の集合のこと）上の、包含関係⊂ は半順序である• 理由• A⊂A であるから、⊂ は反射的である• A⊂BかつB⊂Aであれば、A=Bであるから、⊂は反対称的である• A⊂BかつB⊂Cであれば、A⊂Cであるから、⊂は推移的である

8

練習： 「自然数全体」の集合 と |• 自然数全体の集合Nを考える。
• a, b ∈ N に対し、”aはbを割り切る”の関係(=整除関係)を a|b と表記することにする。つまり、
a|b ⇔∃n∈N, na=b(*) 例えば、2|8, 3|6, 12|60などがある。

• このとき、整除関係| はN上の半順序であることを示せ。
0 a 2a 3a … naa|b• 解： (a, b, c ∈ Nとする)

bはaの後に存在するb• a|aなので、|は反射的である• a|bかつb|aであればa=bなので、|は反対称的である• a|bかつb|cであれば、a|cなので、|は推移的である(よって、|はN上の半順序である)

9

半順序の記法• 半順序(関係)を、通常は ≲ を使い、a≲bのように書き、aはbの前にあると読む• 関連記号• a≺b:• a≳b:• a≻b:

a≲b かつ a≠b の意味 (aは真にbの前にある)b≲a の意味 (aはbの後にある)b≺a の意味 (bは真にaの後にある)(*) ≳ は ≲ の逆関係である (逆順序: inverse order)
10

今日のテーマ： 順序集合 と 束• 半順序集合• 直前、直後、図式• 比較可能、全順序•束• 結び、交わり、上限、下限• 半束• 順序の中の束、束の上の順序

11

直前、直後• Sを半順序集合とする。
• a,b ∈Sに対し、aがbの直前にある(immediatepredecessor)ことをa≪bと書く。

aの直後にbがある(immediate successor)とも言う• a≪b ことは、a≺bであって、 a ≺ x≺ bとなるようなxが存在しない、と同義である。
12

有限順序集合を ≪ の関係で図示する (基礎的考え方)• 単一集合上の関係は、有向グラフを使って表現可能• 例題： A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}に対し、整除関係による順序を考える
考え方

2315746910

8

1|2  1|x|2 ? (x=1, x=2は除く)
1|3  1|x|3 ? (x=1, x=3は除く)
1|4  1|x|4 ?
….
(x=2がある)2|4  2|x|4 ?
…
4|8  4|x|8 ?
2|10  2|x|10 ?

有向非巡回グラフ
Directed Acyclic Graph (DAG)
13になっている!!

有限順序集合を図示する(一般的な方法)• ハッセ図 (Hasse Diagram)• a → bのように矢印を描く代わりに、bをaより高い位置に書き、aとbを線で結ぶ

82
3157484 69 106910

有向グラフ

235 71ハッセ図

14練習1• A={a, b, c, d, e}とする。a≪c, d≪c, b≪e, a≪b,c≪e の半順序が定義されているとき、これをハッセ図で図示せよ。
•解ebcad15

練習2• A={a, b, c, d, e}とする。a≪b, b≪c, c≪d, d≪e の半順序が定義されているとき、これをハッセ図で図示せよ。

edcba16

練習3• A={a, b, c}とする。べき集合2A上の包含関係⊂で作られる半順序をハッセ図で図示せよ。
• 解：• べき集合 2A = [ {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c},{a, b, c} ]であるので、包含関係で作られる順序を考えると、次のようになる。

{a, b, c}{a,b} {a,c} {b,c}{a} {b} {c}{}17

今日のテーマ： 順序集合 と 束• 半順序集合• 直前、直後、図式• 比較可能、全順序•束• 結び、交わり、上限、下限• 半束• 順序の中の束、束の上の順序18比較可能、比較不可能• 半順序集合上の要素 s, tは、必ずしもs ≲ t または t ≲ s ・・・ (*)となるとは限らない。
• 例：右図において、a と dの関係は( a ≲ d または d ≲ a )でない

ebcad

• (*) であるとき、sとtは比較可能である、と言う。それ以外の場合、sとtは比較不可能である、という。
19

全順序 （線形順序、鎖）z• 半順序(≲)で、集合Aのすべての要素の対が比較可能
 Aは全順序集合 (Totally Ordered Set)
• 全順序の別名• 線形順序 (Linearly Ordered)• 鎖 (Chain)yxwv

全順序集合の例
20

今日のテーマ： 順序集合 と 束• 半順序集合• 直前、直後、図式• 比較可能、全順序•束• 結び、交わり、上限、下限• 半束• 順序の中の束、束の上の順序

21

束 (Lattice)
鎖 (Chain)

引用： http://www.homedepot.ca/product/4-feet-x-8-feet-western-red-cedar-lattice/935813
http://copytomcat.cocolog-nifty.com/photos/uncategorized/2012/06/04/01.jpg

22

束(Lattice)の代数的な定義• 集合Lを、 交わり(meet)、結び(join)と呼ぶ、2項演算子∧ と ∨のもとで閉じている、空でない集合とする。
このとき、Lが束であるのは、∀a, b, c ∈ L に対して、• 交換律(1a) a∧b = b∧a(1b) a∨b = b∨a• 結合律(2a) (a∧b)∧c = a∧(b∧c)(2b) (a∨b)∨c = a∨(b∨c)• 吸収律(3a) a∧(a∨b) = a(3b) a∨(a∧b) = aが成り立つときである（そして、これを束の公理とする）。
• 束Lのことを、(L, ∧,∨)と表すことがある。

23

結び (Join)とは何か？ (1/3)• 演算記号: ∨• 便宜上、以下、a∨b を ∨(a, b) と表現する• 半順序集合における∨の定義として、以下を考える：• Sを半順序集合とし、{a, b} をSの部分集合とする、いま、a, b ≲ mが成り立つすべてのm∈SをMとするとき、すべてのm∈Mに対し、x ≲ m が成り立つx∈Mがあれば、それを∨(a,b) とする。
• ∨(a,b) = {x|∀m∈M (x ≲ m), x∈M}, M={m | a,b≲m, m∈S}

• 重要：
• 上記において、Mは{a, b}の上界の集合であり、∨(a,b)は{a, b}の上限(supremum)と言われる。
• 上限は、通常は、sup(a,b)と表記する。
• つまり、上記の定義のもとでは、a∨b = sup(a,b) である。

• ∨(a,b)は、高々一つであり、存在しないこともある。
24

結び (Join)とは何か？ (2/3)• ∨を、ハッセ図上で捉えてみる• ∨(a,b) = {x|∀m∈M (x ≲ m), x∈M}, M={m|a,b≲m, m∈S}
M={m|a,b≲m∈S}

M∨(a,b)= {x|∀m∈M (x ≲ m), x∈M}

abS25

結び (Join)とは何か？ (3/3)• ∨を、上方向(後方)に働く力、と捉えてみる。
• 要素a, b、それぞれの後方を考えていく。
• 要素a, bからの両方の力が重なる場所に、∨(a,b)の結果がある。
• ただし、それらの場所の中で、 （順序が比較可能で）最小であるもの∨(a,b)abS26

a∨b = sup(a,b) が存在しない例• 右図の順序集合において∨(a,b)を考える。
{a,b}の上界は{c,d,e,f}である。
しかし、cもdも上限ではない。
そして、上限は存在しない。

efcdab• 理由：
仮にcを上限としてみる。このとき、c≲dが成立しなければならない。
右図の場合では、cとdは比較不可能であり、これは成立しない。
また、dを上限と仮定した場合も同様のことが言える。

27

練習1
• 右図の半順序集合Lにおいて、• sup({a}, {b})• sup({a,b}, {b,c})• sup({a}, {b,c})• sup({}, {a,b})• sup({a}, {a,b,c})• sup({a}, {a}){a, b, c}{a,b} {a,c} {b,c}をそれぞれ求めよ。
• 解:• sup({a}, {b}) = {a,b}• sup({a,b}, {b,c}) = {a,b,c}• sup({a}, {b,c}) = {a,b,c}• sup({}, {a,b}) = {a,b}• sup({a}, {a,b,c}) = {a,b,c}• sup({a}, {a})={a}{a} {b}
{}{c}

28

練習2
• 右図の半順序集合Pにおいて、• (1,0,0) ∨ (0,1,0)• (1,1,0) ∨ (0,1,1)• (1,0,0) ∨ (0,1,1)• (0,0,0) ∨ (1,1,0)• (1,0,0) ∨ (1,1,1)• (1,0,0) ∨ (0,0,0)(1, 1, 1)(1, 1, 0) (1, 0, 1) (0, 1, 1)をそれぞれ求めよ。
(ただし、ここでの∨は、Pの部分集合に対するsupの意味とする)• 解:• (1,0,0) ∨ (0,1,0) ： 存在しない• (1,1,0) ∨ (0,1,1) = (1,1,1)• (1,0,0) ∨ (0,1,1) = (0,1,1)• (0,0,0) ∨ (1,1,0) = (1,1,0)• (1,0,0) ∨ (1,1,1) = (1,1,1)• (1,0,0) ∨ (0,0,0) = (1,0,0)(1, 0, 0) (0, 1, 0) (0, 0, 1)(0, 0, 0)29交わり (meet)とは何か？
• 結び (Join)に対し、逆順序で定義されるもの。
• 結び(Join):∨(a,b) = {x|∀m∈M (x ≲ m), x∈M}, M={m|a,b≲m, m∈S}

• 交わり (Meet):∧(a,b) = {x|∀m∈M (x ≳m), x∈M}, M={m|a,b≳m, m∈S}

• 上限(supremum): ∨(a,b) = sup(a,b)• 下限(infimum): ∧(a,b) = inf(a,b)
30

束の特徴
• 束(L, ∧, ∨) は∧および∨のもとで閉じている必要があった。

• 集合Lが、 ∧のもとで閉じているとは、 a∀a,b∈L, a∧b∈L• 集合Lが、 ∨のもとで閉じているとは、∀a,b∈L, a∨b∈L• つまり、束(L, ∧, ∨)には、∀a,b∈L, a∧b∈L, a∨b∈Lという制限がある

a∨bba∧b

束L31

半束• 結び半束 (join-semilattice)∀a,b∈L, a∨b∈Lであるときa∨ba∨bbabaa∧b• 交わり半束(meet-semilattice)∀a,b∈L, a∧b∈Lであるとき

a∨bbaa∧bbaa∧b32

順序集合の中の束 (1/2)• ∨の定義の時に、半順序≲を用いていたことを思い出そう。その定義は簡略すると、
a∨b = sup(a,b) : (半順序集合における)上限a∧b = inf(a,b) : (半順序集合における)下限であった。

• 実は、束とは、任意の要素a, bの対に対して、a∨b = sup(a,b) と a∧b = inf(a,b)
が存在する半順序集合のことである。
33

順序集合の中の束 (2/2)• 半順序集合Pの、任意の要素a, bの対に対して、a∨b = sup(a,b) と a∧b = inf(a,b)
が存在すれば、Pは束(P, ∧, ∨)である。
• 理由（詳細な証明は割愛するが）：任意の要素a, bの対に対して a∨b = sup(a,b) と a∧b = inf(a,b) が存在すれば、
1. sup(a,b)=sup(b,a)なので、交換律： a∨b= b∨a
2. sup(sup(a,b), c) = sup(a, sup(b,c)) なので、結合律: (a∨b)∨c = a∨(b∨c)
3. sup(a,inf(a,b))=aなので、吸収律: a∨(a∧b) = aがそれぞれ成立する。双対についても同様。

34

束の上の順序• 束Lに対しては、a∨b = b ならば a≲bという順序を定義することができる。
• ≲は反射的か？

• a∨a = a であるので(次ページで束の公理(吸収律)から証明しよう)、どんなaに対してもa≲aであり、 ≲は、反射的である• ≲は反対称的か？

• a∨b = b かつ b∨a = a であれば、束の公理(交換律)より、a=b である。
つまり、 a≲bかつb≲aであればa=bであるから、 ≲は反対称的である。

• ≲は推移的か？

• a∨b = b かつ b∨c = c であれば、a∨c = a∨(b∨c) = (a∨b)∨c =b∨c = c である(結合律)。つまり、 a≲bかつb≲cであればa ≲ c であるから、 ≲は推移的である。

よって、束Lに対しては、a∨b = b ならば a≲b という順序≲を定義することができる。
35

練習1• 束の公理を使い、a∨a = a (べき等律)を示せ• 解：a∨a = a∨(a∧(a∨b))(a=a∧(a∨b)を利用)= a∨(a∧c)(c= a∨bとおいた)=a(a∨(a∧b)=aを利用)
よって、 a∨a = a である。

36

練習2
• 束(L,∧,∨)において、a∨b = b ならば a≲bはa∧b = a ならば a≲bに置き換えられることを示せ。
• 解：• 束の公理(吸収律)より、a∧(a∨b)=a が成り立つ。ここに、a∨b = bを代入すると、a∧b = aである。逆も同様。つまり、
a∨b = b ならば a≲bは、a∧b = a ならば a≲bに置き換えられる。
37

5月の講義予定• 5月6日: 命題計算
• 5月13日: 休講 (5月際準備のため)• 5月16日: ブール代数• 5月27日: グラフの構造と種類

38