...

同値関係 - 電気通信大学

by user

on
Category: Documents
14

views

Report

Comments

Transcript

同値関係 - 電気通信大学
今日の概要
この講義の目標
離散数学 第 10 回
関係 (2):同値関係
I
語学としての数学,コミュニケーションとしての数学
今日の目標
岡本 吉央
[email protected]
I
同値関係と分割の関係を理解する
I
I
電気通信大学
I
分割とは?
分割から同値関係へ
同値関係から分割へ
• 同値分割と商集合
2014 年 7 月 15 日
最終更新:2014 年 7 月 14 日
岡本 吉央 (電通大)
10:19
離散数学 (10)
2014 年 7 月 15 日
岡本 吉央 (電通大)
1 / 31
離散数学 (10)
2014 年 7 月 15 日
同値関係
同値関係を表す記号
集合 A と A 上の関係 R
同値関係を表すために,R ではなくて,特別な記号を使うことが多い
同値関係とは?
I
R は反射性を持つ
I
R は対称性を持つ
I
R は推移性を持つ
I
反射性:任意の x ∈ A に対して,x R x
I
対称性:任意の x, y ∈ A に対して,x R y ならば y R x
I
推移性:任意の x, y , z ∈ A に対して,x R y かつ y R z ならば x R z
岡本 吉央 (電通大)
その否定を表す記号の例
I 6=
同値関係を表す記号の例
I =
R が同値関係であるとは,次を満たすこと
離散数学 (10)
2014 年 7 月 15 日
I
≡
I
6≡
I
∼
I
6∼
I
'
I
6'
I
≈
I
6≈
I
...
I
...
状況に応じて,使い分けられたりする
岡本 吉央 (電通大)
5 / 31
同値関係をグラフで描くとき...
4 / 31
離散数学 (10)
2014 年 7 月 15 日
6 / 31
2014 年 7 月 15 日
8 / 31
同値関係が与える「かたまり」への分割
これが同値関係を表すグラフだとすると?
a
b
a
f
b
e
c
f
a
c
b
f
d
a
a
b
c
e
e
d
c
f
b
e
c
d
f
e
d
d
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
岡本 吉央 (電通大)
7 / 31
離散数学 (10)
分割
今日の目標
目次
今から行うこと
次を証明する
I
「同値関係」から「『かたまり』への分割」が得られること
I
「『かたまり』への分割」から「同値関係」が得られること
つまり,
「同値関係」と「分割」は同じものを別の方法で表現している
a
b
c
a
f
b
e
c
d
岡本 吉央 (電通大)
1
分割
2
分割から同値関係へ
3
同値関係から分割へ
4
今日のまとめ
f
e
d
離散数学 (10)
2014 年 7 月 15 日
9 / 31
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
10 / 31
分割
分割
集合の分割
分割とは?
:例 (続き)
分割とは?
次の 4 つはどれも {1, 2, 3, 4, 5, 6} の分割
集合 A の分割とは次を満たすような集合 P のこと
I
任意の X ∈ P に対して,X ⊆ A かつ X 6= ∅
I
任意の X , Y ∈ P に対して,X 6= Y ならば X ∩ Y = ∅
I
任意の x ∈ A に対して,ある X ∈ P が存在して,x ∈ X
{{1, 2}, {3, 4, 5, 6}}
(非空性)
2
6
2
(被覆性)
3
5
3
1
6
3
5
1
(素性)
例:A = {1, 2, 3, 4, 5, 6} のとき,{{1, 2}, {3, 4, 5, 6}} は A の分割
2
{{1, 4, 5}, {2, 3, 6}}
1
6
5
4
4
{{1, 2, 3}, {4, 6}, {5}}
{{1}, {2}, {3}, {4}, {5}, {6}}
1
4
1
2
6
2
3
5
3
6
5
4
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
4
岡本 吉央 (電通大)
11 / 31
離散数学 (10)
分割
2014 年 7 月 15 日
12 / 31
分割
分割の例 1:日本の八地方区分
分割の例 2:カレンダー
1ヵ月の 31 日をいろいろな方法で分割している
日
月
火
水
木
金
土
1
8
15
22
29
2
9
16
23
30
3
10
17
24
31
4
11
18
25
5
12
19
26
6
13
20
27
7
14
21
28
I
1 日 1 日で分割 (31 個の集合へ分割)
I
週ごとに分割 (5 個の集合へ分割)
I
曜日ことに分割 (7 個の集合へ分割)
I
...
http://www.craftmap.box-i.net/
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
岡本 吉央 (電通大)
13 / 31
離散数学 (10)
分割から同値関係へ
2014 年 7 月 15 日
14 / 31
分割から同値関係へ
目次
分割から同値関係へ
集合 A の分割 P を考える
1
分割から同値関係へ
分割
I
2
A 上の関係 R を,任意の x, y ∈ A に対して x R y であることを
ある X ∈ P が存在して,
x ∈ X かつ y ∈ X である
分割から同値関係へ
こととして定義する
3
同値関係から分割へ
4
今日のまとめ
I
このとき,R は A 上の同値関係である
1
1
2
6
2
3
5
3
4
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
岡本 吉央 (電通大)
15 / 31
分割から同値関係へ
6
5
4
離散数学 (10)
2014 年 7 月 15 日
分割から同値関係へ
分割から同値関係へ:証明 (反射性)
分割から同値関係へ:証明 (対称性)
証明すべきこと (1):反射性
証明すべきこと (2):対称性
任意の x ∈ A に対して,x R x
任意の x, y ∈ A に対して,x R y ならば y R x
定義に立ち戻って書きなおす
定義に立ち戻って書きなおす
任意の x ∈ A に対して,ある X ∈ P が存在して,x ∈ X かつ x ∈ X
任意の x, y ∈ A に対して,
「ある X ∈ P が存在して,x ∈ X かつ y ∈ X 」ならば
「ある X ∈ P が存在して,y ∈ X かつ x ∈ X 」
証明:任意に x ∈ A を選ぶ.
I
P は A の分割なので,分割の被覆性から,ある X ∈ P が存在して,
x ∈ X.
I
したがって,ある X ∈ P が存在して x ∈ X かつ x ∈ X .
I
R の定義から,ある X ∈ P が存在して,x ∈ X かつ y ∈ X .
I
したがって,x R x .
I
すなわち,ある X ∈ P が存在して,y ∈ X かつ x ∈ X .
I
したがって,y R x .
岡本 吉央 (電通大)
離散数学 (10)
16 / 31
2014 年 7 月 15 日
17 / 31
証明:任意に x, y ∈ A を選び,x R y と仮定する.
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
18 / 31
分割から同値関係へ
同値関係から分割へ
分割から同値関係へ:証明 (推移性)
目次
証明すべきこと (3):推移性
任意の x, y , z ∈ A に対して,x R y かつ y R z ならば x R z
1
分割
2
分割から同値関係へ
3
同値関係から分割へ
4
今日のまとめ
証明:任意に x, y , z ∈ A を選び,x R y かつ y R z と仮定する.
I
R の定義から,ある X ∈ P が存在して,x ∈ X かつ y ∈ X .
I
同様に,ある X 0 ∈ P が存在して,y ∈ X 0 かつ z ∈ X 0 .
I
y ∈ X と y ∈ X 0 から,y ∈ X ∩ X 0 .
I
特に,X ∩ X 0 6= ∅.
X 0.
I
分割の素性から,X =
I
したがって,x ∈ X かつ z ∈ X .
I
したがって,x R z .
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
岡本 吉央 (電通大)
19 / 31
離散数学 (10)
同値関係から分割へ
2014 年 7 月 15 日
20 / 31
2014 年 7 月 15 日
22 / 31
同値関係から分割へ
同値類
商集合
集合 A 上の同値関係 R を考える
商集合とは?
同値類とは?
集合 A 上の同値関係 R に対して,
同値関係 R における要素 a ∈ A の同値類とは
A / R = {[a]R | a ∈ A}
{x | x ∈ A かつ x R a}
を R に関する A の商集合と呼ぶ.
という集合のことであり,これを [a]R とも書く
1
a
b
f
c
e
d
1
I
[a]R = {a, b, c, d}
2
6
2
I
[b]R = {a, b, c, d}
3
5
3
I
[c]R = {a, b, c, d}
I
[d]R = {a, b, c, d}
I
[e]R = {e, f }
I
[f ]R = {e, f }
岡本 吉央 (電通大)
4
6
5
4
A / R = {{1, 2}, {3, 4, 5, 6}}
離散数学 (10)
2014 年 7 月 15 日
岡本 吉央 (電通大)
21 / 31
同値関係から分割へ
離散数学 (10)
同値関係から分割へ
同値関係から分割へ
同値関係から分割へ:証明 (非空性)
集合 A 上の同値関係 R を考える
証明すべきこと (1):非空性
同値関係から分割へ
任意の X ∈ A / R に対して,X ⊆ A かつ X 6= ∅
商集合 A / R は A の分割である
証明:任意に X ∈ A / R を選ぶ.
これゆえ,R に関する A の商集合のことを,R に関する A の同値分割と
も呼ぶ
1
1
I
商集合の定義から,ある a ∈ A が存在して,X = [a]R .
I
同値類の定義から,[a]R ⊆ A.
I
したがって,X ⊆ A.
2
6
2
6
I
同値関係の反射性から,a R a.
3
5
3
5
I
同値類の定義から,a ∈ [a]R .
I
したがって,[a]R 6= ∅.
I
したがって,X 6= ∅.
4
岡本 吉央 (電通大)
4
離散数学 (10)
2014 年 7 月 15 日
岡本 吉央 (電通大)
23 / 31
同値関係から分割へ
離散数学 (10)
2014 年 7 月 15 日
同値関係から分割へ
同値関係から分割へ:証明 (素性)
同値関係から分割へ:証明 (被覆性)
証明すべきこと (2):素性
証明すべきこと (3):被覆性
任意の X , Y ∈ A / R に対して,X 6= Y ならば X ∩ Y = ∅.
任意の x ∈ A に対して,ある X ∈ A / R が存在して,x ∈ X
証明:任意に X , Y ∈ A / R を選ぶ.
I 対偶を証明するために,X ∩ Y 6= ∅ を仮定する. . . . . . . . . . . . . . . . (1)
I 商集合の定義から,ある a ∈ A が存在して,X = [a]R .
I 同様に,ある a0 ∈ A が存在して,Y = [a0 ]R .
I 仮定 (1) より,ある a00 ∈ A が存在して,a00 ∈ X かつ a00 ∈ Y .
I すなわち,a00 ∈ [a]R かつ a00 ∈ [a0 ]R .
I 同値類の定義から,a00 R a かつ a00 R a0 .
I a00 R a と同値関係の対称性から,a R a00 .
I a R a00 ,a00 R a0 と同値関係の推移性から,a R a0 .
I a R a0 から,[a]R = [a0 ]R .
(演習問題)
I したがって,X = Y .
I したがって,X 6= Y ならば X ∩ Y = ∅.
証明:任意に x ∈ A を選ぶ.
岡本 吉央 (電通大)
離散数学 (10)
24 / 31
2014 年 7 月 15 日
25 / 31
I
X = [x]R とする.
I
反射性から,x R x .
I
同値類の定義から,x ∈ [x]R .
I
したがって,x ∈ X .
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
26 / 31
今日のまとめ
今日のまとめ
目次
今日のまとめ
この講義の目標
1
分割
2
分割から同値関係へ
I
語学としての数学,コミュニケーションとしての数学
今日の目標
I
同値関係と分割の関係を理解する
I
I
3
同値関係から分割へ
4
今日のまとめ
I
分割とは?
分割から同値関係へ
同値関係から分割へ
• 同値分割と商集合
格言
本質的に同一であるものが,異なる表現を持つことはよくある
同値関係
局所的 (local)
微視的 (micro)
岡本 吉央 (電通大)
離散数学 (10)
2014 年 7 月 15 日
27 / 31
岡本 吉央 (電通大)
分割
大域的 (global)
巨視的 (macro)
離散数学 (10)
2014 年 7 月 15 日
28 / 31
Fly UP