PDFをダウンロード - Yuta IKUBO

同値関係
Yuta IKUBO
http://ikubo.oﬃcial.jp/
最終更新日：平成 27 年 6 月 10 日
目次
1
同値関係
2
1.1
同値関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.1
同値関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.2
同値律の特徴付け . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
類別 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.2.1
同値類 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.2.2
商集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.3
類別 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.2.4
分割が生成する同値関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
射影 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.3.1
射影 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.3.2
射影が生成する同値関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.3.3
写像の分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
1.2
1.3
1
1
同値関係
1.1
1.1.1
同値関係
同値関係
同値関係
• 本節では同値関係（equivalence relation）と呼ばれる特別な二項関係1 について考察しよう．具体的には，集合 X
上の二項関係 R が以下の 3 つの条件を満たすとき，これを X 上の同値関係と呼ぶ：
(a) ∀x ∈ X : xRx
(b) ∀x, y ∈ X : (xRy ⇒ yRx)
(c) ∀x, y, z ∈ X : [(xRy ∧ yRz) ⇒ xRz]
• 条件 (a) は，X の任意の要素 x が自身と関係を持つことを意味し，これを反射律（reﬂexive law）と呼ぶ．条件 (b)
は，X の任意の 2 つの要素 x, y について，x が y と関係を持つ場合には，逆に y は x と関係を持つことを意味し，
これを対称律（symmetric law）と呼ぶ．条件 (c) は，X の 3 つの要素 x, y, z について，x が y と関係を持ち，y が
z と関係を持つ場合には，x は z と関係を持つことを意味し，これを推移律（transitive law）と呼ぶ．
• 同値関係を規定する上の 3 つの性質を総称して同値律（equivalence law）と呼ぶ．また，集合 X 上の同値関係 R が
与えられたとき，順序対 (x, y) ∈ X × X に関して xRy が真である場合には，x と y は R のもとで同値（equivalent）
であると言う．
• 一般に，集合 X 上の二項関係 R は直積 X × X の部分集合と同一視できる（第??節）．ゆえに，それぞれの順序対
(x, y) ∈ X × X に対して，
(x, y) ∈ R ⇔ xRy
という関係が成立するため，同値律を以下のように表現することもできる：
(a) ∀x ∈ X : (x, x) ∈ R
(b) ∀x, y ∈ X : [(x, y) ∈ R ⇒ (y, x) ∈ R]
(c) ∀x, y, z ∈ X : {[(x, y) ∈ R ∧ (y, z) ∈ R)] ⇒ (x, z) ∈ R}
• 集合 X 上の同値関係 R は ∼ という記号で表記されることもある．ただし，任意の順序対 (x, y) ∈ X × X に対して，
x ∼ y ⇔ xRy
と定める．このような表記のもとでは，同値律を以下のように表現することもできる：
(a) ∀x ∈ X : x ∼ x
(b) ∀x, y ∈ X : (x ∼ y ⇒ y ∼ x)
(c) ∀x, y, z ∈ X : [(x ∼ y ∧ y ∼ z) ⇒ x ∼ z]
1 二項関係に関する詳細は，本ウェブサイトで公開中の関係に関するテキスト（http://ikubo.oﬃcial.jp/relation/）を参照せよ．
2
例 1.1 (相等関係)
• すべての実数からなる集合 R が与えられたとき，順序対 (x, y) ∈ R × R に対して以下のように R を定義する．
def
xRy ⇔ x = y
ただし，= は実数どうしを比較する通常の相等関係である．
• 任意の (x, y) ∈ R × R に対して，x = y は真か偽のいずれか一方であるから，R は R 上の二項関係である．さらに，
任意の x ∈ R に対して，
xRx ⇔ x = x
∵ R の定義
となるが，x = x は真であるから R は反射律を満たす．また，任意の x, y ∈ R に対して，
xRy ⇔ x = y
∵ R の定義
⇔y=x
⇔ yRx
∵ R の定義
ゆえに，R は対称律を満たす．また，任意の x, y, z ∈ R に対して，
(xRy ∧ yRz) ⇔ (x = y ∧ y = z)
∵ R の定義
⇒x=z
⇔ xRz
∵ R の定義
ゆえに，R は推移律を満たす．したがって，R は R 上の同値関係である．
例 1.2 (相似関係)
• 平面上のすべての三角形からなる集合 X が与えられたとき，順序対 (x, y) ∈ X × X に対して以下のように R を定
義する．
def
xRy ⇔ x ∼ y
ただし，∼ は三角形どうしが相似であることを表す相似関係である．
• 任意の (x, y) ∈ X × X に対して，x ∼ y は真か偽のいずれか一方であるから，R は X 上の二項関係である．さら
に，任意の x ∈ X に対して，
xRx ⇔ x ∼ x
∵ R の定義
となるが，x ∼ x は真であるから R は反射律を満たす．また，任意の x, y ∈ X に対して，
xRy ⇔ x ∼ y
∵ R の定義
⇔y∼x
⇔ yRx
3
∵ R の定義
ゆえに，R は対称律を満たす．また，任意の x, y, z ∈ X に対して，
(xRy ∧ yRz) ⇔ (x ∼ y ∧ y ∼ z)
∵ R の定義
⇒x∼z
⇔ xRz
∵ R の定義
ゆえに，R は推移律を満たす．したがって，R は X 上の同値関係である．
例 1.3 (合同式)
• すべての整数からなる集合 Z が与えられたとき，順序対 (x, y) ∈ Z × Z に対して以下のように R を定義する．
def
xRy ⇔ x ≡ y (mod 2)
ただし， x ≡ y (mod 2) は，x は 2 を法（mod）として y と合同であること，すなわち，x − y が 2 の整数倍であ
ることを意味する．
• 任意の (x, y) ∈ Z × Z に対して，x ≡ y (mod 2) は真か偽のいずれか一方であるから，R は Z 上の二項関係であ
る．さらに，任意の x ∈ Z に対して，
xRx ⇔ x ≡ x (mod 2)
∵ R の定義
⇔ ∃k ∈ Z : x − x = 2k
となるが，k = 0 の場合に上の命題は真になるため，R は反射律を満たす．また，任意の x, y ∈ Z に対して，
xRy ⇔ x ≡ y (mod 2)
∵ R の定義
⇔ ∃k ∈ Z : x − y = 2k
⇔ ∃ − k ∈ Z : y − x = 2 (−k)
⇔ y ≡ x (mod 2)
⇔ yRx
∵ R の定義
ゆえに，R は対称律を満たす．また，任意の x, y, z ∈ X に対して，
(xRy ∧ yRz) ⇔ [x ≡ y (mod 2) ∧ y ≡ z (mod 2)]
∵ R の定義
⇔ [(∃k ∈ Z : x − y = 2k) ∧ (∃l ∈ Z : y − z = 2l)]
⇒ ∃k + h ∈ Z : x − z = 2 (k + l)
⇔ x ≡ z (mod 2)
⇔ xRz
∵ R の定義
ゆえに，R は推移律を満たす．したがって，R は X 上の同値関係である．
4
1.1.2
同値律の特徴付け
同値律の特徴付け
• 集合 X 上の二項関係 R を直積 X × X の部分集合と解釈するならば，同値関係 R はどのような性質を満たす集合
として特徴付けられるだろうか．この問いに答えるのが以下の命題である．
命題 1.1 二項関係 R ⊂ X × X に関して以下が成り立つ：
(a)
R が反射律を満たす ⇔ ∆X ⊂ R
(b)
R が対称律を満たす ⇔ R = R−1
(c)
R が推移律を満たす ⇔ R ◦ R ⊂ R
ただし，∆X は恒等関係，R−1 は逆関係，R ◦ R は合成関係である．
• 恒等関係 ∆X ⊂ X × X とは，任意の (x, y) ∈ X × X に対して，
def
x∆X y ⇔ x = y
と定義される X 上の二項関係である．すなわち，x と y が一致するとき，そしてそのときにのみ真となるような
二項関係が恒等関係である．上の命題中の条件 (a) は，集合 X 上の二項関係 R が同値関係であることは，R が X
上の恒等関係 ∆X を部分集合として含むことを意味する．
• 集合 X 上の二項関係 R が与えられたとき，任意の (x, y) ∈ X × X に対して，
def
xR−1 y ⇔ yRx
と定義される X 上の二項関係 R−1 を R の逆関係と呼ぶ．すなわち，R のもとで y が x と関係するとき，そしてそ
のときにのみ R−1 のもとで x と y が関係するような二項関係が R の逆関係である．上の命題中の条件 (b) は，集
合 X 上の二項関係 R が同値関係であることは，R がその逆関係 R−1 と一致することを意味する．
• 集合 X 上の二項関係 R が与えられたとき，任意の (x, y) ∈ X × X に対して，
def
xR ◦ Ry ⇔ [∃z ∈ X : (xRz ∧ zRy)]
と定義される X 上の二項関係 R ◦ R を R と R の合成関係と呼ぶ．すなわち，R のもとで x, y に対して xRz と zRy
をともに満たす z が存在するとき，そしてそのときにのみ R ◦ R のもとで x と y が関係するような二項関係が R
と R の合成関係である．上の命題中の条件 (c) は，集合 X 上の二項関係 R が同値関係であることは，R がその合
成関係 R ◦ R を部分集合として含むことを意味する．
(a) の証明：
5
• R が反射律を満たすならば，任意の (x, y) ∈ X × X に対して，
(x, y) ∈ ∆X ⇔ x = y
∵ ∆X の定義
⇒ (x, y) ∈ R
∵ R の反射律
となるので ∆X ⊂ R が成り立つ．
• 逆に，∆X ⊂ R が成り立つとする．∆X の定義より，
∀x ∈ X : (x, x) ∈ ∆X
であるが，∆X ⊂ R であるから，
∀x ∈ X : (x, x) ∈ R
すなわち R は反射律を満たす．
(b) の証明：
• R が対称律を満たすならば，任意の (x, y) ∈ X × X に対して，
(x, y) ∈ R ⇒ (y, x) ∈ R
∵ R の対称律
⇔ (x, y) ∈ R−1
∵ R−1 の定義
(x, y) ∈ R−1 ⇔ (y, x) ∈ R
∵ R−1 の定義
⇒ (x, y) ∈ R
∵ R の対称律
となるので R ⊂ R−1 が成り立ち，逆に，
となるので R−1 ⊂ R が成り立つ．したがって，R = R−1 である．
• 逆に，R = R−1 が成り立つとする．R−1 の定義より，
∀ (x, y) ∈ X × X : (x, y) ∈ R ⇔ (y, x) ∈ R−1
であるが，仮定より R = R−1 であるから，
∀ (x, y) ∈ X × X : (x, y) ∈ R ⇔ (y, x) ∈ R
が得られるので，R は対称律を満たす．
(c) の証明：
• R が推移律を満たすならば，任意の (x, y) ∈ X × X に対して，
(x, y) ∈ R ◦ R ⇔ {∃z ∈ X : (xRz ∧ zRy)}
⇒ xRy
∵ R の推移律
⇔ (x, y) ∈ R
6
∵ R ◦ R の定義
となるので R ◦ R ⊂ R が成り立つ．
• 逆に，R ◦ R ⊂ R が成り立つとする．また，任意の (x, y) , (y, z) ∈ X × X に対して，推移律の条件に相当する，
xRy ∧ yRz
が成り立つとすると，このとき，
∃y ∈ X : (xRy ∧ yRz)
すなわち，
(x, z) ∈ R ◦ R
が成り立つので，R ◦ R ⊂ R より，
(x, z) ∈ R
すなわち xRz が成り立つので，R は推移律を満たす．
1.2
類別
1.2.1
同値類
同値類
• 集合 X 上の同値関係 ∼ が与えられたとき，∼ のもとで要素 x ∈ X と同値である X のすべての要素からなる集合
[x] = {y ∈ X|x ∼ y}
を x を代表元（representative）とする同値類（equivalence class）と呼ぶ．
• 同値関係は対称律を満たすことを踏まえると，集合 X 上の同値関係 ∼ から定義される要素 x ∈ X の同値類を，
[x] = {y ∈ X|y ∼ x}
としてもよい．
• 定義より，任意の要素 x ∈ X に対してその同値類 [x] は X の部分集合である．すなわち，
∀x ∈ X : [x] ⊂ X
が成り立つ．
代表元の交換可能性
7
• 集合 X 上の同値関係 ∼ と要素 x ∈ X が与えられれば，その要素 x を代表元とする同値類 [x] ⊂ X を構成できる
が，[x] の要素を任意に選んだ上で，その新たな要素を代表元とする同値類を構成すると，それは [x] と一致する．
ゆえに，同値類は代表元を取り替えても変わらない．
命題 1.2 集合 X 上の同値関係 ∼ が与えられたとき，
∀x ∈ X, ∀y ∈ [x] : [y] = [x]
が成り立つ．
証明：
• 集合 X 上の同値関係 ∼ が与えられたとき，要素 x ∈ X を任意に選んだ上で，それを代表元とする同値類 [x] を構
成する．さらに，この同値類に属する要素 y ∈ [x] を任意に選んだ上で，それを代表元とする同値類 [y] を構成する．
• このとき，任意の z ∈ X について，
z ∈ [x] ⇔ x ∼ z
∵ [x] の定義
⇔x∼z ∧ x∼y
∵ y ∈ [x]
⇒z∼x ∧ x∼y
∵ 対称律
⇒z∼y
∵ 推移律
⇒y∼z
∵ 対称律
⇔ z ∈ [y]
∵ [y] の定義
ゆえに，[x] ⊂ [y] が成り立つ．
• 反対に，任意の y ∈ X について，
z ∈ [y] ⇔ y ∼ z
∵ [y] の定義
⇔x∼y ∧ y∼z
⇒x∼z
⇔ z ∈ [x]
ゆえに，[y] ⊂ [x] が成り立つ．
• したがって，[x] = [y] が成り立つ．
1.2.2
商集合
商集合
8
∵ y ∈ [x]
∵ 推移律
∵ [x] の定義
• 集合 X 上の同値関係 ∼ が与えられれば，それぞれの要素 x ∈ X に対して，それを代表元とする同値類 [x] ⊂ X を
特定できるため，以下の集合族
X\ ∼= {[x] |x ∈ X} = {[x]}x∈X
を構成できる．これを X の ∼ による商集合（quotient set）と呼ぶ．
• つまり，X 上の同値関係 ∼ が与えられたとき，X のそれぞれの要素を代表元とする同値類をすべて集めてできる
集合族が商集合 X\ ∼ である．
例 1.4 (合同式から構成される商集合)
• すべての整数からなる集合 Z が与えられたとき，順序対 (x, y) ∈ Z × Z に対して，
def
xRy ⇔ x ≡ y (mod 2)
と定義される合同関係 R は Z 上の同値関係である．
• この R に関しては，以下の 2 つの同値類のみが存在する：
[0] = {x ∈ X|x ≡ 0 (mod 2)} = {x ∈ X|∃k ∈ Z : x − 0 = 2k} = {0, ±2, ±4, · · · }
[1] = {x ∈ X|x ≡ 1 (mod 2)} = {x ∈ X|∃l ∈ Z : x − 1 = 2l} = {±1, ±3, ±5, · · · }
• ゆえに，X の R による商集合は，
X\R = {[0] , [1]}
となる．
1.2.3
類別
商集合は分割
• 集合 X の空でない部分集合からなる部分集合族 A が以下の 2 つの条件
(a)
(b)
∪
A=X
∀A, B ∈ A : (A ̸= B ⇒ A ∩ B = φ)
を満たすとき，A を X の分割（partition）と呼ぶ．すなわち，集合 X の分割 A とは，A の和集合が X 全体と一
致し，なおかつ，A に属するどの 2 つの互いに集合も交わらないことを意味する．
• 以下で示すように，集合 X 上の同値関係 ∼ から定義される商集合 X\ ∼ は X の分割である．まずは以下の補題
を示そう．
9
補題 1.1 集合 X 上の同値関係 ∼ が与えられたとき，以下が成り立つ：
(a)
(b)
∀x ∈ X : x ∈ [x]
∪
X=
[x]
(c)
∀x, y ∈ X : (x ∼ y ⇔ [x] = [y])
(d)
∀x, y ∈ X : {¬ (x ∼ y) ⇔ [x] ∩ [y] = φ}
x∈X
(a) の証明：
• 要素 x ∈ X を任意に選ぶ．このとき，反射律より x ∼ x が成り立つが，同値類 [x] の定義より，これは x ∈ [x] を
意味する．
(b) の証明：
• 任意の y ∈ X について，
y ∈ X ⇒ y ∈ [y]
∵ (a)
⇒ ∃x ∈ X : y ∈ [x]
∪
[x] ∵ ∪の定義
⇔ y∈
x∈X
ゆえに，X ⊂
∪
x∈X
[x] が成り立つ．
• 逆に，任意の y ∈ X について，
y∈
∪
x∈X
[x] ⇔ ∃x ∈ X : y ∈ [x]
⇒ y∈X
∵ ∪の定義
∵ [x] ⊂ X
∪
ゆえに， x∈X [x] ⊂ X が成り立つ．
• したがって，X =
∪
x∈X
[x] が成り立つ．
(c) の証明：
• ⇒ を示す．x, y ∈ X を任意に選ぶ．このとき，x ∼ y が成り立つ場合には，任意の z ∈ X について，
z ∈ [x] ⇔ x ∼ z
∵ [x] の定義
⇔ x∼z ∧ x∼y
∵x∼y
⇒ x∼z ∧ y∼x
∵ 対称律
⇒ y∼z
⇔ z ∈ [y]
∵ 推移律
∵ [y] の定義
ゆえに，[x] ⊂ [y] が成り立つ．[y] ⊂ [x] も同様にして示せるため，[x] = [y] が成り立つ．
10
• ⇐ を示す．x, y ∈ X を任意に選び，[x] = [y] が成り立つ場合を想定する．(a) より x ∈ [x] であるが，このとき，
x ∈ [x] ⇔ x ∈ [y]
∵ [x] = [y]
⇔ y∼x
∵ [b] の定義
⇒ x∼y
∵ 対称律
ゆえに，x ∼ y が成り立つ．
• したがって，x ∼ y ⇔ [x] = [y] が成り立つ．
(d) の証明：
• ⇒ の対偶を示す．x, y ∈ X を任意に選び，[x] ∩ [y] ̸= φ を仮定する．このとき，
[x] ∩ [y] ̸= φ ⇔ ∃z ∈ X : (z ∈ [x] ∧ z ∈ [y])
⇔ ∃z ∈ X : (x ∼ z ∧ y ∼ z)
∵ [x] , [y] の定義
⇒ ∃z ∈ X : (x ∼ z ∧ z ∼ y)
∵ 対称律
⇒ x∼y
∵ 推移律
すなわち，[x] ∩ [y] ̸= φ ⇒ x ∼ y が成り立つため，その対偶である ¬ (x ∼ y) ⇒ [x] ∩ [y] = φ もまた真である．
• ⇐ を示す．x, y ∈ X を任意に選び，[x] ∩ [y] = φ を仮定する．(a) より，x ∈ [x] ̸= φ かつ y ∈ [y] ̸= φ であるが，こ
れと [x] ∩ [y] = φ を踏まえると x ̸= y となる．ゆえに，[x] ̸= [y] であるから，(c) より ¬ (x ∼ y) が成り立つ．
• したがって，¬ (x ∼ y) ⇔ [x] ∩ [y] = φ が成り立つ．
• この補題を踏まえた上で，一般に，商集合 X\ ∼ が X の分割であることを示そう．
命題 1.3 集合 X 上の同値関係 ∼ が与えられたとき，商集合 X\ ∼ は X の分割である．
• この命題は以下のように図解できる．下図において，集合 X は 4 つの互いに素な部分集合 [a] , [b] , [c] , [d] の和集合
として表されているが，これらは X 上の同値関係 ∼ から構成される同値類である．
X
d
C (d )
C (a )
a
c
C (c )
C (b ) b
証明：
11
• 任意の要素 x ∈ X に対して，補題 1.1 の (a) より，x ∈ [x] ⊂ X が成り立つため，商集合 X\ ∼= {[x]}x∈X は X
の空でない部分集合からなる部分集合族である．さらに，X/ ∼ が分割であるためには，
(a)
(b)
∪
X/ ∼= X
∀A, B ∈ X/ ∼: (A ̸= B ⇒ A ∩ B = φ)
を示せばよい．
• まずは，
X=
∪
x∈X
[x]
∵ 補題 1.1 の (b)
= ∪X/ ∼ ∵ X/ ∼ の定義
ゆえに (a) が成り立つ．
• 続いて，任意の A, B ∈ X/ ∼ をとると，X/ ∼= {[x]}x∈X ゆえに，A = [a] , B = [b] であるような a, b ∈ X がそ
れぞれ存在する．このとき，
A ̸= B ⇔ [a] ̸= [b]
⇔ ¬ (a ∼ b)
⇔ [a] ∩ [b] = φ
∵ 補題 1.1 の (c)
∵ 補題 1.1 の (d)
⇔A∩B =φ
ゆえに (b) も成り立つ．
• したがって，X/ ∼ は X の分割である．
類別
• 集合 X 上の同値関係 ∼ から構成される商集合 X\ ∼ は X の分割であることが明らかになった．すなわち，
(a)
(b)
∪
X\ ∼= X
∀A, B ∈ X\ ∼: (A ̸= B ⇒ A ∩ B = φ)
が成り立つ．
• そこで，集合 X 上の同値関係 ∼ から X の分割である商集合 X\ ∼ を構成することを，X の ∼ による類別（classiﬁcation）と呼ぶ．
1.2.4
分割が生成する同値関係
分割が生成する同値関係
12
• 集合 X 上の同値関係 ∼ から類別される商集合 X\ ∼ は X の分割であることが明らかになった．つまり，X は ∼
を用いることで左下の図のように互いに重ならない複数の同値類に分割される．では逆に，X 全体が右下図のよう
に互いに重ならない複数の集合に分割可能であるならば，すなわち，X の分割が与えられれば，そこから X 上の
同値関係 ∼ を構成できるだろうか．
X
X
d
C (d )
C (a )
a
D
c
A
C (c )
C (b ) b
C
B
• 一般に，集合 X の分割 A が与えられたとき，分割の定義より，それぞれの順序対 (x, y) ∈ X × X に対して，
x ∈ A, y ∈ B を満たす集合 A, B ∈ A が存在する．そこで，
def
xRy ⇔ A = B
と R を定義すると，以下で示すように，これは X 上の同値関係となる．そこで，X の分割 A から上のように定義
される X 上の同値関係を，分割A が生成する同値関係（equivalence relation induced by partition）と呼び，これ
を RA で表す．
命題 1.4 集合 X の分割 A が与えられたとき，それぞれの順序対 (x, y) ∈ X × X に対して，x ∈ A, y ∈ B を満たす集合
A, B ∈ A が存在する．ゆえに，
def
xRy ⇔ A = B
として R を定義できるが，これは X 上の同値関係である．
証明：
【R が二項関係であることの確認】
• 集合 X の分割 A が与えられたとき，分割の定義より，それぞれの x ∈ X に対して，x ∈ A であるような集合
A ∈ A が一意的に定まる．ゆえに，X のそれぞれの要素は A に属する 1 つの集合に必ず属する．したがって，順
序対 (x, y) ∈ X × X に対して，x ∈ A, y ∈ B を満たす集合 A, B ∈ A が必ず存在するため，
def
xRy ⇔ A = B
(1)
という R が定義可能である．つまり，X の 2 つの要素 x, y について，それらが属する A の集合が等しいとき，そ
してその場合にのみ，x と y は R のもとで関係するものと定義する．
• 分割 A に属する 2 つの集合 A, B について A = B は成り立つか否かのどちらか一方であるから，上のように定義
される R は X 上の二項関係である．そこで以降では，上のように定義される二項関係 R が X 上の同値関係であ
ることを示そう．
13
【R が同値関係であることの証明】
• 要素 x ∈ X を任意にとると，それに対して x ∈ A を満たす集合 A ∈ A が存在する．このとき，
xRx ⇔ A = A
∵ (1)
となるが，A = A は明らかに真であるから，R は反射律を満たす．
• 要素 x, y ∈ X を任意にとると，これらに対して x ∈ A, y ∈ B を満たす集合 A, B ∈ A が存在する．このとき，
xRy ⇔ A = B
∵ (1)
⇔ B=A
⇔ yRx
∵ (1)
ゆえに，R は対称律を満たす．
• 要素 x, y, z ∈ X を任意にとると，これらに対して x ∈ A, y ∈ B, z ∈ C を満たす集合 A, B, C ∈ A が存在する．こ
のとき，
xRy ∧ yRz ⇔ (A = B ∧ B = C)
∵ (1)
⇒ A=C
⇔ xRz
∵ (1)
ゆえに，R は推移律を満たす．
• 集合 X の分割 A から (1) のように定義される R は X 上の同値関係としての要件を満たすため，これは A が生成
する X 上の同値関係である．
同値関係と分割の関係
• 集合 X 上の同値関係 ∼ が与えられたとき，
X\ ∼= {[x]}x∈X
と定義される X の部分集合族は X の分割である．ただし，それぞれの x ∈ X に対して，
[x] = {y ∈ X|x ∼ y}
である．この X\ ∼ は X の ∼ による商集合と呼ぶ．
• 逆に，集合 X 上の分割 A が与えられたとき，順序対 (x, y) ∈ X × X に対して，x ∈ A, y ∈ B を満たす集合 A, B ∈ A
が必ず存在するため，
def
xRA y ⇔ A = B
として RA を定義できるが，これは X 上の同値関係である．この RA を A が生成する X 上の同値関係と呼ぶ．
14
• 以上の議論を総合すると，集合 X 上の同値関係 ∼ から X の分割 X\ ∼ を生成できるだけでなく，逆に，X の分
割 A から X 上の同値関係 RA を生成できるため，集合 X 上の同値関係と X の分割は本質的に等しい概念である
と言える．
1.3
1.3.1
射影
射影
同値関係の射影
• 集合 X 上の同値関係 ∼ を用いると，X を商集合 X\ ∼= {[x]}x∈X へと類別できる．そこで，それぞれの要素 x ∈ X
に対して，それを代表元とする同値類
π (x) = [x]
を像として定める写像 π : X → X\ ∼ を，∼ の射影（projection）と呼ぶ．
同値関係の射影は全射
• 商集合 X\ ∼ の要素 A ∈ X\ ∼ を任意に選ぶと，商集合の定義 X\ ∼= {[x]}x∈X より，
A = [a]
を満たす要素 a ∈ X が存在する．さらに，a は X の要素であるから，∼ の射影 π : X → X\ ∼ はこの a に対して，
π (a) = [a]
を定める．以上を総合すると，
∀A ∈ X\ ∼, ∃a ∈ X : π (a) = A
が成り立つ．つまり，同値関係 ∼ の射影 π : X → X\ ∼ は全射である．
1.3.2
射影が生成する同値関係
写像が生成する同値関係
• 集合 X, Y と写像 f : X → Y が与えられたとき，それぞれの順序対 (x, y) ∈ X × X に対して，
def
xRy ⇔ f (x) = f (y)
と R を定義すると，以下で示すように，これは X 上の同値関係となる．そこで，写像 f : X → Y から上のように
定義される X 上の同値関係を，写像f が生成する同値関係（equivalence relation induced by mapping）と呼び，
これを Rf で表す．
15
命題 1.5 集合 X, Y と写像 f : X → Y が与えられたとき，それぞれの順序対 (x, y) ∈ X × X に対して，
def
xRy ⇔ f (x) = f (y)
と定義される R は，X 上の同値関係である．
証明：
【R が二項関係であることの確認】
• 写像 f : X → Y が与えられたとき，写像の定義より，それぞれの x ∈ X に対して，像 f (x) ∈ Y が一意的に定ま
る．したがって，順序対 (x, y) ∈ X × X に対して，f (x) , f (y) という Y の要素が必ず存在するため，
def
xRy ⇔ f (x) = f (y)
(1)
という R が定義可能である．
• 集合 Y に属する 2 つの要素 f (x) , f (y) について，f (x) = f (y) は成り立つか否かのどちらか一方であるから，上
のように定義される R は X 上の二項関係である．そこで以降では，上のように定義される二項関係 R が X 上の
同値関係であることを示そう．
【R が同値関係であることの証明】
• 要素 x ∈ X を任意にとると，それに対して f (x) ∈ Y が存在する．このとき，
xRx ⇔ f (x) = f (x)
∵ (1)
となるが，f (x) = f (x) は明らかに真であるから，R は反射律を満たす．
• 要素 x, y ∈ X を任意にとると，これらに対して f (x) , f (y) ∈ Y が存在する．このとき，
xRy ⇔ f (x) = f (y)
∵ (1)
⇔ f (y) = f (x)
⇔ yRx
∵ (1)
ゆえに，R は対称律を満たす．
• 要素 x, y, z ∈ X を任意にとると，これらに対して f (x) , f (y) , f (z) ∈ Y が存在する．このとき，
(xRy ∧ yRz) ⇔ [f (x) = f (y) ∧ f (y) = f (z)]
⇒ f (x) = f (z)
⇔ xRz
∵ (1)
ゆえに，R は推移律を満たす．
16
∵ (1)
• 写像 f : X → Y から (1) のように定義される R は X 上の同値関係としての要件を満たすため，これは f が生成す
る X 上の同値関係である．
同値関係の射影が生成する同値関係
• 集合 X 上の同値関係 ∼ から定義される射影 π : X → X\ ∼ もまた写像であるから，直前の命題 1.5 より，射影 π
から X 上の同値関係 Rπ を生成できるが，この同値関係に関して以下の命題が成り立つ．
命題 1.6 集合 X 上の同値関係 ∼ から定義される射影 π : X → X\ ∼ から生成される X 上の同値関係 Rπ は ∼ に等しい．
証明：
• 集合 X 上の同値関係 ∼ から定義される射影 π : X → X\ ∼ が生成する X 上の同値関係 Rπ は，順序対 (x, y) ∈ X ×X
に対して，
def
xRπ y ⇔ π (x) = π (y)
すなわち，
def
xRπ y ⇔ [x] = [y]
(1)
と定義される．
• 一方，同値関係 ∼ に関しても，補題 1.1 の (c) より，(x, y) ∈ X × X に対して，
x ∼ y ⇔ [x] = [y]
(2)
が成り立つ．
• (1) , (2) より，(x, y) ∈ X × X に対して，
xRπ y ⇔ x ∼ y
が成り立つ．ゆえに，射影 π が生成する X 上の同値関係 Rπ は，π を構成するもととなった同値関係 ∼ に等しい．
1.3.3
写像の分解
写像の分解
• 写像 f : X → Y が与えられたとき，これを 3 つの写像の合成写像として表すことができる．
17
定理 1.1 集合 X, Y と写像 f : X → Y が与えられたとき，全射 g : X → X\Rf ，全単射 h : X\Rf → R (f )，単射
i : R (f ) → Y が存在して，
f =i◦h◦g
と表すことができる．ただし，Rf は f から生成される X 上の同値関係，X\Rf は X を Rf によって類別して得られる
商集合，R (f ) は f の値域をそれぞれ表す．
証明：
【全射g : X → X\Rf の候補を特定する】
• 集合 X, Y と写像 f : X → Y が与えられたとき，f から生成される X 上の同値関係を Rf で表す．すなわち，順序
対 (x, y) ∈ X × X に対して，
def
xRf y ⇔ f (x) = f (y)
(1)
と定める．さらに，この Rf によって X を類別して得られる商集合を，
X\Rf = {[x]}x∈X
で表す．ただし，それぞれの x ∈ X に対して，
[x] = {y ∈ X|xRf y}
である．
• このとき，それぞれの要素 x ∈ X に対して，それを代表元とする同値類
g (x) = [x]
を像として定める Rf の射影 g : X → X\Rf を定義することができ，なおかつ，射影の性質より，g は全射となる．
【全単射h : X\Rf → V (f ) の候補を特定する】
• Rj の射影 g : X → X\Rf は写像であるから，そこから X 上の同値関係 Rg を生成できる．すなわち，順序対
(x, y) ∈ X × X に対して，
def
xRg y ⇔ g (x) = g (y)
(2)
である．
• 命題 1.6 より，射影 g から生成された同値関係 Rg は射影 g を構成するもととなる同値関係 Rf に等しいため，順
序対 (x, y) ∈ X × X に対して，
xRg y ⇔ xRf y
が成り立つ．
18
(3)
• (1) , (2) , (3) より，写像 f : X → Y と全射 g : X → X\Rf は，任意の順序対 (x, y) ∈ X × X に対して，
f (x) = f (y) ⇔ g (x) = g (y)
(4)
を満たす．
• 同値関係 Rf の射影 g : X → X\Rf は全単射であるから，
∀A ∈ X\Rf , ∃x ∈ X : A = g (x)
(5)
が成り立つ．さらに，それぞれの g (x) ∈ X\Rf に対して，(4) より，f (x) ∈ Y が一意的に定まるため，それぞれ
の要素 x ∈ X に対して，
h′ (g (x)) = f (x)
(6)
を像として定める写像 h′ : X\Rf → Y を構成できる．
• この写像 h′ : X\Rf → Y は，任意の g (x) , g (y) ∈ X\Rf に対して，
g (x) ̸= g (y) ⇒ f (x) ̸= f (y)
∵ (4)
⇔ h′ (g (x)) ̸= h′ (g (y))
∵ h′ の定義
を満たすため単射である．
• 単射 h′ : X\Rf → Y の終集合を h′ の値域 R (h′ ) へと縮小して得られる写像を h : X\Rf → R (h′ ) とすると，こ
れは明らかに全単射となる．
• 写像 h′ : X\Rf → Y の値域は，
R (h′ ) = {y ∈ Y |∃A ∈ X\Rf : y = h′ (A)}
= {y ∈ Y |∃x ∈ X : y = h′ (g (x))}
= {y ∈ Y |∃x ∈ X : y = f (x)}
= R (f )
∵ R (h′ ) の定義
∵ (5)
∵ (6)
∵ R (f ) の定義
を満たすため，h : X\Rf → R (f ) としてもよい．そして，繰り返しになるが，これは全単射である．
【単射i : R (f ) → Y の候補を特定する】
• 写像 f : X → Y の値域 R (f ) は明らかに R (f ) ⊂ Y を満たす．そこで，それぞれの要素 y ∈ R (f ) に対して，
i (y) = y
を像として定める写像 i : R (f ) → Y を定義する．
• この写像 i : R (f ) → Y は，任意の y, z ∈ R (f ) に対して，
y ̸= z ⇒ i (y) ̸= i (z)
19
∵ i の定義
を満たすため単射である．
【f = i ◦ h ◦ g の証明】
• 写像 f : X → Y が与えられたとき，以上の全射 g : X → X\Rf ，全単射 h : X\Rf → V (f )，そして単射
i : R (f ) → Y が存在することが明らかになった．このとき，任意の x ∈ X について，
(i ◦ h ◦ g) (x) = (i ◦ h) (g (x))
= i (h (g (x)))
= h (g (x))
= f (x)
が成り立つため，f = i ◦ h ◦ g が成り立つ．
20
∵ ◦の定義
∵ ◦の定義
∵ i の定義
∵ h の定義
参考文献
[1] Seymour, L. (1995). 『一般位相』. オーム社出版局.
[2] 松坂和夫. (1968). 『集合・位相入門』. 岩波書店.
[3] 杉浦光夫. (1980). 『解析入門 I』. 東京大学出版会.
21

Download Report