離散数学及び演習 講義2順序対（ordered pair）
離散数学及び演習講義 2 2014. 4.24（木）

順序対



決められた順序に並べられた対象からなる対対象 a と対象 b からなる順序対 （ a，b ）

a … 第 1 成分（1st component）
b … 第 2 成分（2nd component）

例：（2，5），（－3，2.5）… 座標平面上の点（太郎，100），（次郎，50）… 学生とその得点
 （太郎，花子），（太郎，次郎） … 兄弟



直積・関係
2 項関係の性質（教科書 pp.9-12）

一般に，（ a，b ）≠（ b， a ）教科書･･･野崎昭弘：離散系の数学、近代科学社

（ a，a ）も順序対



cf. { a，b } ＝{ b， a }cf. { a，a } ＝{ a }2n 項組（n-tuple）

等しい順序対

順序対（ a，b ）と順序対（ c，d ）は等しい（equal）（ （ a，b ）＝（ c，d ） ）




n 項組


a＝c かつ b＝d

各成分がそれぞれ等しい

決められた順序に並べられた n 個の対象からなる列（ a1，a2， …， an ）対象 ai … 第 i 成分（i-th component）
2 項組 … 順序対のこと

n 項組（a1，a2， …， an）と n 項組（b1，b2， …， bn）は等しい


任意の i （ i＝1，…，n ）に対して， ai ＝ bi

34直積（cartesian product）


集合 A と集合 B の直積

A×B ＝ { （ x，y ）｜x∈A かつ y∈B }例： A＝{ a，b }，B＝{ 1，2，3 }A×B ＝ { （a，1），（a，2），（a，3），（b，1），（b，2），（b，3）}
 B×A ＝ { （1，a），（1，b），（2，a），（2，b），（3，a），（3，b）}

一般に， A×B ≠ B×A ．

Aab

直積（続き）
B
1



2


3
B
12

集合 A1，…， An の直積

A1 ＝…＝ An （＝ A）のとき
Aa

A1 ×…× An ＝ { （ x1，…，xn ）｜xi∈Ai，i＝1，…，n }A1 ×…× An ＝ An

例： A＝{ a，b }b3

A×A ＝ A2 ＝ { （a，a），（a，b），（b，a），（b，b） }5

A×A×A ＝ A3＝ { （a，a，a ），（a，a，b），（a，b，a），（a，b，b），（b，a，a ），（b，a，b），（b，b，a），（b，b，b） }61

離散数学及び演習 講義22 項関係（binary relation）

定理
 集合 A，B，C に対して，次の（1），（2）が成り立つ．
（1） A×（B∩C）＝（A×B）∩（A×C）（2） A×（B∪C）＝（A×B）∪（A×C）



集合 A から集合 B への 2 項関係 RR ⊆ A×B

例： A＝{ 1，2，3，4 }… 学生の集合
B＝{ a，b，c，d，e }… 科目の集合
 順序対（ 1，a ） … 学生 1 は科目 a を受講している
 A×B … 学生と科目のすべての組み合わせからなる集合 R＝{（1，a），（2，b），（2，c），（3，b），（3，c），（3，d） }⊆ A×B… 学生とその学生が受講している科目

有限集合 A，B に対して，｜A×B｜＝｜A｜・｜B｜

782 項関係のグラフ表現

2 項関係（続き）

A＝{ 1，2，3，4 } ， B＝{ a，b，c，d，e }R＝{（1，a），（2，b），（2，c），（3，b），（3，c），（3，d） }⊆ A×B
BA
Ra1b2c3d4

集合 A から集合 A への 2 項関係 R ⊆ A×A R ⊆ A×A＝A2 … 集合 A 上の 2 項関係 （ a，b ）∈R … a R b

例： N＝{ 1，2，3，… }（すべての自然数からなる集合）
R＝{（1，2），（1，3），（1，4），…， （2，3），（2，4），… }⊆N2 （1，2）∈R … 1 は 2 より真に小さい 1 R 2，1 R 3，1 R 4，…，2 R 3，2 R 4，…
e

R の代わりに＜を使うと … 1＜2，1＜3，1＜4，…，＜＝{（1，2），（1，3），（1，4），…，（2，3），（2，4），…}⊆N2910

2 項関係の定義域，値域

2 項関係の定義域，値域（続き）

関係 R⊆A×B に対して，
 R の定義域（domain）


dom（R） ＝{ x∈A｜ある y∈B に対して，xRy } range（R）＝{ y∈B｜ある x∈A に対して，xRy }dom（R）＝{ x∈A｜ある y∈B に対して，xRy }例：R の値域（range）
BArange（R）＝{ y∈B｜ある x∈A に対して，xRy }1dom（R） 2
34Rab range（R）
cde

11

122

離散数学及び演習 講義2n 項関係（n-ary relation）
集合 A1，…， An の間の n 項関係 R

関係の演算R ⊆ A1 ×…× An関係 R1，R2 ⊆ A×BR ⊆ A ×…× A ＝ An … 集合 A 上の n 項関係

例： A＝{ 1，2，3，4 }… 学生の集合
B＝{ a，b，c，d，e }… 科目の集合
R1 ＝{（1，a），（2，b），（2，c），（3，b），（3，c），（3，d） }… 学生とその学生が受講している科目
R2 ＝{（1，a），（1，d），（2，b），（3，b），（4，d），（4，e） }… 学生とその学生が興味を持っている科目 R1∩R2 ＝{（1，a），（2，b），（3，b）}… 学生とその学生が興味を持って受講している科目
 R1－R2 ＝{（2，c），（3，c），（3，d）}… 学生とその学生が受講しているが興味のない科目

例： R … すべての実数からなる集合
x2

R1∩R2，R1∪R2， R1－R2z
L ＝ {（ x，y，z ）｜ ＝ y ＝ } ⊆ R3
3

… R 上の 3 項関係（座標空間上の直線）1314

逆関係（inverse）
補関係（complement）

関係 R⊆ A×B の逆関係 R-1-1
 R ＝{（y，x）｜（x，y）∈R }（⊆ B×A ）関係 R⊆ A×B の補関係


例： A＝{ 1，2，3，4 }… 学生の集合
B＝{ a，b，c，d，e }… 科目の集合
R ＝{（1，a），（2，b），（2，c），（3，b），（3，c），（3，d） }… 学生とその学生が受講している科目-1
 R ＝{（a，1），（b，2），（c，2），（b，3），（c，3），（d，3）}… 科目とそれを受講している学生

Rc ＝（A×B）－R （⊆ A×B ）例： A＝{ 1，2，3，4 }… 学生の集合
B＝{ a，b，c，d，e }… 科目の集合
R ＝{（1，a），（2，b），（2，c），（3，b），（3，c），（3，d） }… 学生とその学生が受講している科目c R ＝{（1，b），（1，c），（1，d），（1，e），（2，a），（2，d），（2，e），（3，a），（3，e），（4，a），（4，b），（4，c），（4，d），（4，e） }… 学生とその学生が受講していない科目
1516定理証明

関係 R，S ⊆ A×B に対して，次の（1）～（5）が成り立つ．
（1） （ R-1 ）-1 ＝ R（2） R ⊆ S ならば， R-1 ⊆ S-1（3） （ R∪S ）-1 ＝ R-1∪ S-1（4） （ R∩S ）-1 ＝ R-1∩ S-1（5） （ R－S ）-1 ＝ R-1－ S-1（3） （ R∪S ）-1 ＝ R-1∪ S-1a） 「（ R∪S ）-1 ⊆ R-1∪ S-1」とb） 「 R-1∪ S-1 ⊆ （ R∪S ）-1 」の両方を示す．
-1-1-1 a） 「任意の （x，y）∈（ R∪S ） に対して，（x，y）∈R ∪ S 」を示す．
a） 任意の （x，y）∈（ R∪S ）-1 に対して， （y，x）∈R∪S．
ゆえに， （y，x）∈R，または，（y，x）∈S．
このとき， （x，y）∈R-1 ，または，（x，y）∈S-1だから，（x，y）∈ R-1∪ S-1．
したがって，（ R∪S ）-1 ⊆ R-1∪ S-1．

17

18

3

離散数学及び演習 講義2関係の合成（composition）

証明（続き）（3） （ R∪S ）-1 ＝ R-1∪ S-1



-1-1-1
 a） 「（ R∪S ） ⊆ R ∪ S 」と-1-1-1
 b） 「 R ∪ S ⊆ （ R∪S ） 」の両方を示す．
関係 R⊆ A×B と関係 S⊆ B×C の合成関係
b） 「任意の （x，y）∈R-1∪S-1 に対して，（x，y）∈（R∪S ）-1 」を示す．

S・R＝ {（x，z）｜ある y ∈B に対して，（x，y）∈R かつ （y，z）∈S }（ ⊆A×C ）b） 任意の （x，y）∈ R-1∪ S-1 に対して，（x，y）∈R-1 ，または，（x，y）∈S-1．
ゆえに， （y，x）∈R，または，（y，x）∈S．
このとき，（y，x）∈ R∪S だから， （x，y）∈（ R∪S ）-1．
したがって， R-1∪ S-1 ⊆ （ R∪S ）-1 ．

S ・ R ＝ {（x，z）｜ある y ∈B に対して，（x，y）∈ S かつ （y，z）∈ R }と定義する場合もある

AB
RyC
Sxz
S・R

1920

合成関係（続き）
定理

S・ R ＝ {（x，z）｜ある y∈B に対して，（x，y）∈R，（y，z）∈S }関係 R⊆ A×B， S⊆ B×C， T⊆ C×D に対して，（ T ・ S ）・ R ＝ T ・（ S ・R ）例： A＝{ 1，2，3，4 }… 学生の集合
B＝{ a，b，c，d，e }… 科目の集合
C＝{ α，β，γ }… 先生の集合
R ＝{（1，a），（2，b），（2，c），（3，b），（3，c），（3，d） }… 学生とその学生が受講している科目
S ＝{（a，α），（b，β），（b，γ），（c，γ），（d，γ） }… 科目とそれを担当している先生
S・ R ＝{（1，α），（2，β），（2，γ），（3，β），（3，γ）}… 学生とその学生の受講科目を担当している先生（関係の合成に関する結合則）
が成り立つ．

21

22

反射的な関係

反射的な関係（続き）

2 項関係 R⊆A2 は反射的（reflexive）である



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

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

例： A＝{ 1，2，3 }

A



……

xRx

x

1R1R13R1R12R1（1，1）， （2，2）， （3，3）∈ R1
任意の x∈A に対して（x，x）∈ R1 だから， R1 は反射的である．

R2 ＝{（1，1）,（1，2）,（1，3）,（2，1）,（3，3）,（3，1）}
（2，2）  R2 だから，R2 は反射的でない．

R2R24R21R2R
23

R1R1＝{（1，1）,（1，3）,（2，1）,（2，2）,（2，3）,（3，3）,（3，1）}
R

R12 項関係 R⊆A2 は反射的である

R223 R224

離散数学及び演習 講義2

反射的な関係（続き２）

対称的な関係2 項関係 R⊆A2 は反射的である



任意の x∈A に対して，（x，x）∈R2 項関係 R⊆A2 は対称的（symmetric）である


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

例： N＝{ 1，2，3，… }2 S1＝{ （x，y）∈N ｜x は y を割り切る } 任意の x∈ N に対して（x，x）∈ S1 だから，S1 は反射的である．
2
 S2 ＝{（x，y）∈N ｜x ＜ y } （1，1）S2 （ 1＜1 でない） だから，S2 は反射的でない．
2
 S3 ＝{（x，y）∈N ｜ x  y } は反射的である．

Rxy……

RxyR

RRxyR

2526

対称的な関係（続き）


反対称的な関係
R12 項関係 R⊆A2 は対称的である

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

1R1R1

R12

2 項関係 R⊆A2 は反対称的（antisymmetric）である


R13R1R1
例： A＝{ 1，2，3 } R1＝{（1，1）,（1，3）,（2，1）,（2，2）,（2，3）,（3，3）,（3，1）}


A（2，1）∈ R1 であるが， （1，2） R1 だから， R1 は対称的でない．

R2 ＝{（1，1）,（1，2）,（1，3）,（2，1）,（3，3）,（3，1）}（1，1）∈R2 に対して （1，1）∈R2 ，（1，2）∈R2 に対して （2，1）∈R2 ，（2，1）∈R2 に対して （1，2）∈R2 ，：（3，1）∈R2 に対して （1，3）∈R2
ゆえに，R2 は対称的である．

xR2R223 R2yx

R＝R……

x

R＝Ryy2728

反対称的な関係（続き）

対称的な関係・反対称的な関係

2 項関係 R⊆A2 は反対称的である


R＝R

R21R2R2

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

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

2 項関係 R⊆A2 は対称的である

2 項関係 R⊆A2 は反対称的である


例： N＝{ 1，2，3，… }2 S3 ＝{（x，y）∈N ｜ x  y } 任意の x，y∈N に対して，x  y かつ y  x ならば，x＝y ゆえに， S3 は反対称的である．

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

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

29

5

1T12
3

T1T2
1T2

2T2
330

離散数学及び演習 講義2

推移的な関係

推移的な関係（続き）

2 項関係 R⊆A2 は推移的（transitive）である


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



RyRz…… xR

Ryz

RR



Rxy

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

R1R1R

z

R2 は推移的でない．

R2

推移的な関係（続き２）R2

1R223 R232

関係の冪（べき）関係 R ⊆ A2 に対して，
 R1 ＝ R Rn ＝ R・Rn－1 （ n  2 ）2 項関係 R⊆A2 は推移的である
任意の x，y，z∈A に対して，（x，y）∈R かつ （y，z）∈R ならば，（x，z）∈R

例： A＝{ 1，2，3，4，5 }例： A：すべての人からなる集合 R＝{（x，y）｜y は x の先祖である } R は推移的である．
 S＝{（x，y）｜y は x の親である } S は推移的でない．

R＝{（1，3），（2，4），（3，2），（3，5）}

4R1 ＝ R

R3 ＝ R・R2 ＝ { （1，4） }R4 ＝ R・R3 ＝ φ：

恒等関係

5R22R32
 R ＝ R・R ＝ { （1，2），（1，5），（3，4）}
R2
33



2R1R
R2 ＝{（1，1）,（1，2）,（1，3）,（2，1）,（3，3）,（3，1）} 2
 （2，1），（1，3）∈R2 に対して （2，3） R2 だから，R231



R1R1（1，1），（1，1） ∈R1 に対して （1，1）∈R1 ，（2，1），（1，3） ∈R1 に対して （2，3）∈R1 ，：（3，1），（1，3） ∈R1 に対して （3，3）∈R1
ゆえに，R1 は推移的である．

R13R1R1
例： A＝{ 1，2，3 } R1＝{（1，1）,（1，3）,（2，1）,（2，2）,（2，3）,（3，3）,（3，1）}

Ax

2 項関係 R⊆A2 は推移的である

3R2
134

推移閉包・反射推移閉包
関係 R ⊆ A2 に対して，
 R の推移閉包（transitive closure）
R＋

A 上の恒等関係（identity relation）
 IA ＝ {（x，x）｜x∈A}∞R＋＝∪ Rn （＝ R1 ∪ R2 ∪ R3∪… ）n＝1

例： A＝{ 1，2，3，4，5 }IA

R＝{（1，3），（2，4），（3，2），（3，5）}

4

IA ＝ {（1，1），（2，2），（3，3），

R の反射推移閉包（reflexive transitive closure） R＊IA

2（4，4），（5，5）}R＊＝ IA ∪ R＋5

3IA ＝ R0 とおくと，∞

IA（1） R＋＝∪ Rn

IAn＝1

1∞

（2） R＊＝∪ Rn

IAn＝035366

離散数学及び演習 講義2

推移閉包（続き）

推移閉包（続き）

例１： A＝{ 1，2，3，4，5 }例２： R＝{（x，y）｜y は x の先祖である }S＝{（x，y）｜y は x の親である }＋ R は S の推移閉包 （ R ＝ S ）R＝{（1，3），（2，4），（3，2），（3，5）}
1 R ＝ R

R2 ＝ R・R ＝ { （1，2），（1，5），（3，4）}
R＋

R3 ＝ R・R2 ＝ { （1，4） }4R4 ＝ R・R3 ＝ φ

2 ＋3R
R＋R＋＋R
R＋1：


R＋＝ R1 ∪ R2 ∪ R3 ∪ R4 ∪ …

R＋関係 R ⊆ A2 の推移閉包

R＋ 5

R＋＝{（x，y）｜ある x0, …, xn （n  1）に対して，
x0＝x, xn＝y, （ xi , x i+1 ）∈R （i＝0，1，…，n－1）}

教科書では推移閉包を R＊で表している
x0（＝x）＝ {（1，2），（1，3），（1，4），（1，5），

Rx1

Rx2

R…

R

xn-1

Rxn（＝y）

R+（2，4），（3，2），（3，4），（3，5）}3738

反射推移閉包（続き）反射推移閉包（続き）

例２： N＝{ 1，2，3，… }，R＝{（x，y）｜y＝x＋1}（ ⊆N2 ）＋ ＝＜＝{（x，y）｜ x ＜ y } R＊ ＝ ＝{（x，y）｜ x Ry}


例１： A＝{ 1，2，3，4，5 }R＝{（1，3），（2，4），（3，2），（3，5）}
R＋＝ R1 ∪ R2 ∪ R3 ∪ R4 ∪ …
＝ {（1，2），（1，3），（1，4），（1，5），

R＊
R＊
4

（2，4），（3，2），（3，4），（3，5）}
IA ＝ {（1，1），（2，2），（3，3），（4，4），（5，5）}R＊

R＊＝ IA ∪ R＋
＝ {（1，1），（1，2），（1，3），（1，4），（1，5），（2，2）， （2，4），（3，2），（3，3），（3，4），（3，5）， （4，4），（5，5）}

R＊

関係 R ⊆ A2 の反射推移閉包
R＊5
R＊2 ＊3R＊R

R＊ ＊R

R＊＝{（x，y）｜ある x0, …, xn（n  0）に対して，x0＝x, xn＝y, （ xi , x i+1 ）∈R （i＝0，1，…，n－1）}


R＊
1 R＊

x＝y の場合でも，（x，y）∈R＊とする

x0（＝x）

R＊

Rx1

R＊

Rx2

R

R＊

39…

Rxn-1

Rxn
（＝y）
40

定理

まとめ関係 R ⊆ A2 に対して，次の（1），（2）が成り立つ．
（1） R＋は推移的である．
（2） R＊は反射的かつ推移的である．

今回の講義

直積・関係
2 項関係の性質

次回の講義
同値関係（教科書 pp.19-23）
 半順序（教科書 pp.12-16）


今回の演習


41

直積・関係
42

7