離散数学及び演習 講義32 項関係の性質（復習）2 項関係 R⊆A2
 R は反射的（reflexive）である

離散数学及び演習
講義 3 2014. 5. 1（木）





同値関係
半順序（教科書 pp.12-16, 19-23）

任意の x，y∈A に対して，（x，y）∈R かつ （y，x）∈R ならば， x ＝ y

R は推移的（transitive）である


教科書･･･野崎昭弘：離散系の数学、近代科学社

任意の x，y∈A に対して，（x，y）∈R ならば （y，x）∈R

R は反対称的（antisymmetric）である


任意の x∈A に対して，（x，x）∈R

R は対称的（symmetric）である

任意の x，y，z∈A に対して，（x，y）∈R かつ （y，z）∈R ならば ，（x，z）∈R2

同値関係（equivalence relation）

対称的な関係・反対称的な関係
例： A＝{ 1，2，3 } T1 ＝{（1，1），（2，2）}
 T1 は対称的かつ反対称的である．
 T2 ＝{（1，2），（1，3），（3，1）}
 T2 は対称的でも反対称的でもない．
（ 1≠3 ）

1T123



T1



T21T2T3 ＝{（1，2），（2，1）}
 T3 は対称的であり，反対称的でない．
（ 1≠2 ）
 T4 ＝{（1，1），（1，2）}
 T4 は対称的でなく，反対称的である．
1T4x R y … x ≡R y， x ～R y
（R の意味で x と y は等しい）

T2
3T3

例： A＝{ a，b，c，d，e，f }R＝{（a，a）,（a，b）,（b，a）,（b，b）,（c，c）,（d，d ）,（d，e）,（d，f ）,（e，d ）,（e，e）,（e，f ）,（f，d ）,（f，e）,（f，f ） }2T3T432ed≡p ＝{（m，n）｜ m と n は p で割ったときの余りが等しい }（⊆ Z2 ）
R は反射的，対称的，かつ推移的だから，R は同値関係である．

例： R＝{（m，n）｜ m と n は 3 で割った余りが等しい } ⊆ N2
c

Z … すべての整数（integer，ganze Zahl）からなる集合
 整数 p を法（modulo）とする合同関係 ≡pR は反射的，対称的，かつ推移的である





f

整数を法とする合同関係

例： A： 平面上のすべての三角形からなる集合
R＝{（x，y）｜ x と y は相似 } ⊆ A2b42 項関係 R⊆A2 は A 上の同値関係である


R は反射的，対称的，かつ推移的だから，R は同値関係である

Aa3同値関係（続き）
R は反射的，対称的，かつ推移的である

23
12 項関係 R⊆A2 は A 上の同値関係である

1 R 4，1 R 7，…2 R 5，2 R 8，…，3 R 6，3 R 9，…
R は反射的，対称的，かつ推移的だから，R は同値関係である．
m R n … m ≡R n， m ≡3 n， m ≡ n （mod 3）（m と n は 3 を法（modulo）として等しい（合同である））

ある d1，d2∈Z に対して，m ＝ d1・p + r，n ＝ d2・p + r だから，m－n ＝ （ d1－ d2 ）・p ，d1－ d2 ∈Z≡p＝{（m，n）｜ m － n は p の倍数である }＝{（m，n）｜ ある d∈Z に対して，m － n ＝ d・p }m ≡p n， m ≡ n （mod p）（m と n は p を法として等しい（合同である））

例：


51365 ≡７ 1 ，365 ≡ 1 （mod 7）1000 ≡13 －1， 1000 ≡ －1 （mod 13）6離散数学及び演習 講義3定理

証明
整数 p を法とする合同関係 ≡p は， Z 上の同値関係である．

整数 p を法とする合同関係 ≡p は， Z 上の同値関係である．

a） 任意の m∈Z に対して，m－m＝0・p だから， m ≡p m ．
b） 任意の m，n∈Z に対して， m ≡p n と仮定する．
このとき，ある d∈Z に対して，m－n＝d・p だから，n－m＝（－d ）・p．
－d∈Z だから，n ≡p m ．
c） 任意の m，n，k∈Z に対して， m ≡p n かつ n ≡p k と仮定する．
ゆえに，ある d，d’∈Z に対して，m－n＝d・p かつ n－k＝d’・p．
このとき，m－k＝（m－n）＋（n－k）＝（ d＋d’ ）・p．
d ＋d’∈Z だから，m ≡p k．
以上から，≡p は反射的，対称的，かつ推移的だから， ≡p は同値関係である．87同値類（equivalent class）
同値分割（equivalent partition）

集合 A 上の同値関係 R による a ∈ A の同値類 ［a］R［a］R ＝ { x ∈ A｜ （a，x）∈ R }＝ { x ∈ A｜ a ≡R x } a …
［a］R の代表元（representative element）

［a］R ＝［b］R ＝{ a，b } ［c］R ＝ { c } ［d ］R ＝［e］R ＝［ f ］R ＝{ d，e，f }集合 A 上の同値関係 R による A の同値分割 A／R（同値類系，商集合（quotient set））
［c］R ＝ { c }b［c］Reda［a］Rbf［c］Recd［d］R

910集合の分割（partition）

同値分割（続き）
集合 A 上の同値関係 R による A の同値分割 A／R

A［d ］R ＝［e］R ＝［ f ］R ＝{ d，e，f }
A／R ＝ { ［a］R，［b］R，［c］R，［d ］R，［e］R，［ f ］R }＝ { ［a］R，［c］R，［d ］R }＝ {{a ，b}，{c}，{d，e，f }}c［d］R

R によるすべての同値類からなる集合例： ［a］R ＝［b］R ＝{ a，b }fA／R ＝ { ［x］R｜ x∈ A }Aa［a］R例：≡p は反射的，対称的，かつ推移的であることを示す．
 a） 「任意の m∈Z に対して， m ≡p m 」を示す．
 b） 「任意の m，n∈Z に対して， m ≡ n ならば n ≡ m 」を示す．
pp c） 「任意の m，n，k∈Z に対して， m ≡p n かつ n ≡p k ならば，m≡p k 」を示す．

A／R ＝ { ［x］R｜ x∈ A }集合 A（≠φ） の分割（直和分割） π
次の（1）～（3）を満たす集合のクラスπ＝{ A1，…，An }（1） 任意の Ai ∈π に対して，Ai ≠φ．
例： R ＝{（x，y）｜ x と y は 3 で割った余りが等しい } ⊆ N2
［1］R＝［4］R ＝［7］R ＝ … ＝ { 1，4，7，… }［2］R＝［5］R ＝［8］R ＝ … ＝ { 2，5，8，… }［3］R＝［6］R ＝［9］R ＝ … ＝ { 3，6，9，… }
N／R ＝ {［1］R，［2］R，［3］R}N
1 4 7 10 …
＝ {{ 1，4，7，… }， ［1］R
{ 2，5，8，… }， ［2］2 5 8 11 …
R{ 3，6，9，… }}3 6 9 12 …
［3］Rn（2） ∪ Ai ＝A．

Ai＝1A1（3） 任意の Ai，Aj ∈πに対して，Ai≠Aj ならば Ai ∩ Aj ＝φ．
A を互いに素な非空部分集合に分けること A1，…，An … 分割πのブロック
AnA2Ai11…
Aj122離散数学及び演習 講義3定理

証明

集合 A （≠φ） 上の同値関係 R による A の同値分割
A／R は，A の分割である．
 A／R が条件（１）～（3）を満たすことを示す．
（1） 任意の［x］R∈A／R に対して，［x］R≠φ．

（2） ∪ ［x］R ＝A．

（1） 任意の［x］R∈A／R に対して，［x］R≠φ．
R は同値関係だから反射的であり，任意の x∈A に対して，（x，x）∈R．
A
ゆえに，x∈ ［x］R ．
［x］RA≠φだから，x∈A は必ず存在する．
x
したがって，［x］ ≠φ．

A［x］Rx∈AR（3） 任意の［x］R，［y］R∈ A／Rに対して，［x］R≠［y］R ならば ［x］R∩［y］R ＝φ．

R…
［y］R1314

証明（続き）

証明（続き２）（2） ∪x∈A ［x］R ＝A（3） 任意の［x］R，［y］R∈ A／R に対して，［x］R≠［y］R ならば ［x］R∩［y］R ＝φ．
 「［x］R∩［y］R ≠φ ならば ［x］R＝［y］R 」（対偶）を示す．
 「［x］R∩［y］R ≠φ」を仮定して，「［x］R⊆［y］R」かつ「［y］R ⊆［x］R」を示す．

1） 「∪x∈A ［x］R ⊆ A 」 と 2） 「A ⊆ ∪x∈A ［x］R 」 の両方を示す．
 1） 「任意の y∈∪x∈A［x］R に対して， y∈A」 と 2） 「任意の y∈A に対して， y∈∪x∈A［x］R 」 を示す．
［x］R∩［y］R ≠φと仮定する．このとき，ある a∈ ［x］R∩［y］R が存在する．
ゆえに， a∈［x］R かつ a∈［y］R だから，（x，a）∈R かつ （y，a）∈R．
R は対称的だから，（a，x）∈R．
さらに，R は推移的だから，（y，x）∈R．
1） 任意の z∈ ［x］R に対して，（x，z）∈R．
R は推移的だから，（y，z）∈R．
ゆえに， z∈［y］R だから， ［x］R⊆［y］R ．
2） 同様に， ［y］R ⊆［x］R．
1），2）から， ［x］R＝［y］R．

1） 任意の y∈∪x∈A［x］R に対して，ある x’が存在して，y∈［x’］R．
このとき，（x’，y）∈R⊆A2 だから，y∈A．
ゆえに， ∪x∈A ［x］R ⊆ A．
2） 任意の y∈A に対して， R は反射的だから （y，y）∈R．
y∈［ y ］R ⊆∪x∈A ［x］R だから， A ⊆ ∪x∈A ［x］R．
1），2）から， ∪x∈A ［x］R ＝A．
15

分割の細分（refinement）

分割が定める同値関係
集合 A の分割π＝{ A1，…，An } が定める A 上の同値関係 Rπ

集合 A の分割 π1，π2 に対して，π1はπ2の細分である．
Rπ＝{ （x，y）｜ある Ai∈πが存在して，x，y∈Ai }（x，y）∈ Rπ… πの同じブロックに属しているA



A1

Rπは反射的，対称的，かつ推移的

π1，π2 がそれぞれ定める A 上の同値関係 Rπ1，Rπ2 に対して， Rπ1⊆ Rπ2 ．
任意の x，y∈A に対して，（x，y）∈ Rπ1 ならば（x，y）∈ Rπ2 ．

An

16π1
A1xRπA

BA11An…

（すなわち，同値関係）である．

π2A

Bk…

Ai

π1はπ2 より細かい π2 はπ1 より粗いy17x
Rπ1Aiy…
x
Rπ2Bjy183

離散数学及び演習 講義3半順序（partial order）
2 項関係 R⊆A2 は A 上の半順序である


半順序（続き）R は反射的，反対称的，かつ推移的である

x R y … x  R y， x

Aec



db

R は反射的，反対称的，かつ推移的だから，
R は半順序である

R は反射的，反対称的，かつ推移的である

例： R ＝ {（m，n）｜m は n を割り切る（ n は m の倍数） } ⊆N2＝ {（m，n）｜ある d∈N が存在して，n＝d ・m }＝ {（1，1）,（1，2）,（1，3），…，（2，2）,（2，4）,（2，6），…，（3，3）,（3，6）,（3，9），… } 任意の m∈N に対して，m＝1・m だから，R は反射的である．
 任意の m，n∈N に対して， m R n かつ n R m と仮定する．
このとき，ある d，d’∈N に対して，n＝d ・m かつ m＝d’・n ．
ゆえに， m＝d’・（ d ・ m ）だから， d’ ・ d ＝ 1．
d，d’∈N だから，d ＝ d’＝ 1．
ゆえに，n＝m だから，R は反対称的である．
 任意の m，n，k∈N に対して， m R n かつ n R k と仮定する．
このとき，ある d，d’∈N に対して，n＝d ・m かつ k＝d’・n ．
ゆえに，k＝d’ ・（ d ・ m ）＝ （d’ ・d ）・ m ．
d’ ・ d ∈N だから， m R k．ゆえに，R は推移的である．

Ry（R の意味で y は x より大きい） 教科書では半順序のことを単に順序と呼んでいる．
例： A＝{ a，b，c，d，e }R＝{（a，a）,（a，b）,（a，c）,（a，d ）,（a，e）,（b，b）,（b，c）,（b，e）,（c，c）,（c，e）,（d，d）,（d，e）,（e，e） }2 項関係 R⊆A2 は A 上の半順序である

a19

20

Hasse 図半順序（続き２）
2 項関係 R⊆A2 は A 上の半順序である


R は反射的，反対称的，かつ推移的である

例： （m，n）∈ N2 … 英語の得点と数学の得点の対（ m1，n1 ） R （ m2，n2 ） iff m1  m2 かつ n1  n2

半順序のグラフ表現における約束半順序は反射的かつ推移的



半順序は反対称的… 英語と数学の両方の得点が多い方が席次が上位

（50，80）  R （80，100）（50，80） と （80，50）の間に順序は付かないR は反射的，反対称的，かつ推移的だから，半順序である．

R ＝{（（m1，n1），（m2，n2 ））｜m1m2 かつ n1 n2 }⊆（N2）2



それらを表す矢印を省略
矢印は上向きと約束し，矢を省略

eeceeccc

半順序では，すべての要素の間に順序が付いているとは限らない．

db（（50，80），（80，100））∈R （（50，80），（80，50）） R


adbadbdbaa2122

全順序（total order）
順序集合（ordered set）

2 項関係 R⊆A2 に対して，x と y （ x，y∈A） は比較可能（comparable）である

（x，y）∈R または （y，x）∈R 2 項関係 R⊆A2 は A 上の全順序（total order）である
対（A，R）は半順序集合（partial order set）である
2 項関係 R は A 上の半順序である

対（A，R）は全順序集合（total order set）である


2 項関係 R は A 上の全順序である

R は A 上の半順序であり，かつ，任意の x，y∈A に対して，x と y は比較可能である

例： 大小関係 は N 上の全順序である．
  は N 上の半順序であり，かつ，任意の m，n∈N に対して，m と n は比較可能である．

23244

離散数学及び演習 講義3

極大元・極小元

最大元・最小元a半順序集合（A， ），B⊆A に対して，
 a∈B は B の極大元（maximal element）である
A



×Ba

x  a かつ a ≠xであるような x ∈ B は存在しない

例： （A， ）：右図，B＝{ 2，3，6 }半順序集合（A， ），B⊆A に対して，
 a∈B は B の最大元（maximum element）である B … x …
… a＝max B… x …

a  x かつ a ≠ x であるような x ∈ B は存在しないa∈B は B の極小元（minimal element）である


B の極大元 … 6
B の極小元 … 2，3



4



3 B

2

任意の x ∈ B に対して，a  x

例： （A， ）：右図，B＝{ 2，3，6 }6

極大（小）元は複数存在することがある 異なる ２ つの極大（小）元は比較可能
でない

任意の x ∈ B に対して，x  aa∈B は B の最小元（minimum element）である… a＝min B
12A

A



112A

B の最大元 … 6B の最小元 … 存在しない

4623 B最大（小）元は存在するとは限らない
最大（小）元は存在すれば唯一である

12526

定理

証明
半順序集合（A， ）に対して， B⊆A の最大（小）元は，存在すれば唯一である

半順序集合（A， ）に対して， B⊆A の最大（小）元は，存在すれば唯一である



最大元は唯一でないと仮定して，矛盾を導く．
 最大元は 2 つ存在すると仮定して，それらが同一であることを示す．

B の最大元は 2 つ存在すると仮定する．
そこで，b1，b2 ∈B （ b1≠b2 ）を B の最大元とする．
b1 は最大元だから，任意の x∈B に対して，x  b1．特に， b2 b1．
b2 も最大元だから，任意の x∈B に対して，x b2．特に， b1 b2．
ところが， は半順序だから反対称的である．
ゆえに， b1＝b2 ．これは矛盾．
すなわち，B の最大元は，存在すれば唯一である．
同様に，B の最小元は，存在すれば唯一である．
27上界，上限



aB
… x …

任意の x ∈ B に対して，x  a

B の上界 … 6，12
B の上限 … 6

上限は上界集合の最小元である

半順序集合（A， ），B⊆A に対して，
 a∈A は B の上界（upper bound）である

B

a は B の上界であり，かつ，B の任意の上界 x に対して，a  x

例： （A， ）：右図，B＝{ 2，3，6 }Aaa∈A は B の最小上界（least upper bound）（上限（supremum））
である … a＝lub B， sup B上界，上限（続き）

A

半順序集合（A， ），B⊆A に対して，
 a∈A は B の上界（upper bound）である


2812A43 B2



1… x …

任意の x ∈ B に対して，x  aa は B の上界であり，かつ，B の任意の上界 x に対して，a  x

例： （A， ）：右図，C＝{ 2，3 }6aa∈A は B の最小上界（least upper bound）（上限（supremum））
である … a＝lub B， sup B

Bの上界集合aC の上界 … 6，12C の上限 … 6 （ C ）上限は上界集合の最小元である

12A

Cの上界集合

462

3 C
12930

5

離散数学及び演習 講義3上界，上限（続き２）A

半順序集合（A， ），B⊆A に対して，
 a∈A は B の上界（upper bound）である

B



上界，上限（続き３）aa

例：半順序集合（P （{a，b，c}），⊆）
B＝{{a}，{a，b}}… x …

任意の x ∈ B に対して，x  aa∈A は B の最小上界（least upper bound）（上限（supremum））
である … a＝lub B， sup Ba は B の上界であり，かつ，B の任意の上界 x に対して，a  x

例： （A， ）：右図，C＝{ 2，3 }

12A

C の上界 … 4，6，12
C の上限 … なし

上限は上界集合の最小元である
 上界が存在しても，上限が存在するとは限らない．


Cの上界集合4623 CB の上界 … {a，b}，{a，b，c}
B の上限 … {a，b}{a，b，c}

{a，b}

{a，c}

{b，c}

B {a}

{b}{c}

1

φ31

下界，下限…

…

半順序集合（A， ），B⊆A に対して，
 a∈A は B の下界（lower bound）である

B

例：半順序集合（P（{a，b，c}），⊆），B＝{{a}，{a，b}}a

任意の x ∈ B に対して，a  xaa∈A は B の最大下界（greatest lower bound）（下限（infimum））
である … a＝glb B， inf B

B の下界 … {a}，φB の下限 … {a}P（{a，b，c}）a は B の下界であり，かつ，B の任意の下界 x に対して，x  a

例： （A， ）：右図，B＝{ 2，3，6 }{a，b，c}12A

B の下界 … 1B の下限 … 132

下界，下限（続き）

Ax

P（{a，b，c}）

Bの上界集合42
下限は下界集合の最大元である 下界が存在しても，下限が存在するとはBの限らない．
6

B {a，b}

{a，c}

{b，c}

3 B{a}{b}{c}

Bの下界集合

φ

1下界集合

33

34

定理

まとめ

半順序集合（A， ），B⊆A に対して，次の（1），（2）が成り立つ．
（1） sup B ∈ B ならば，sup B＝max B．
（2） inf B ∈ B ならば，inf B＝min B．

今回の講義


次回の講義


束（教科書 pp.16-19）

今回の演習
35

同値関係
半順序2 項関係の性質366