Comments
Description
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