関係 (relation) 集合Ａの要素aとＢの要素bとが、ある条件Ｒを満たすとき「Ｒの関係にある」といい、aRb と書く。

Presentation on theme: "関係 (relation) 集合Ａの要素aとＢの要素bとが、ある条件Ｒを満たすとき「Ｒの関係にある」といい、aRb と書く。"— Presentation transcript:

1 関係 (relation) 集合Ａの要素aとＢの要素bとが、ある条件Ｒを満たすとき「Ｒの関係にある」といい、aRb と書く。
Ver.２ 関係 (relation) このように “,” で区切って書くときには「かつ」(and)の意味になる。 集合Ａの要素aとＢの要素bとが、ある条件Ｒを満たすとき「Ｒの関係にある」といい、aRb と書く。 Ｒの関係にある要素の対<a,b>の全体は 直積ＡＸＢの部分集合　　　　　　　　　　　と同一視できる。 例：二つの実数の関係 　　は，集合 　　　　　　　　　　　のことである。 x y グー 別の例： パー チョキ

2 n項関係 x と y が関係 R を満たす、つまり のとき、良く と書く (infix notation)。これは二項関係。
集合ＡからＢへの関数 f (写像) のグラフは、直積 　　　の部分集合であり、一つの二項関係である。 Ａの要素aの関数 f による像 f(a)は A と A の間の関係を A 上の関係ともいう。 前出の例題「ジャンケンの関係」 3 項以上の関係もある。 例: a氏がb氏にcというメールを出した <a,b,c> 例: 夫aと妻bには子供cがいる<a,b,c>

3 二項関係の性質 二項関係 においては、次の性質が基本的 反射律 推移律 対称律 反対称律 関係Ｒが反射律を満たすとき、Ｒは反射的という。
∀x すべてのx 二項関係　　　　　においては、次の性質が基本的 反射律 推移律 対称律 反対称律 関係Ｒが反射律を満たすとき、Ｒは反射的という。 例： Ｎ上の大小関係　は反射的、推移的、反対称的 平面上の二直線の平行関係は反射的、推移的、対称的

4 同値関係 (equivalence relation)
反射的、推移的、対称的な関係を同値関係という 例：平面上の直線の間の「平行関係」 二つの三角形が「合同である」「相似である」 例：自然数 m, 整数 x, y に対して 　　　　　　　　　　 例：関数 が与えられた時　　　　　に対 して 例：自然数の上の等号（＝）　 x と y は m を法として合同

5 同値類 集合 A 上の同値関係 R とが与えられたとき （x の属する同値類） x と R の関係にある y の集合 x を代表元という
集合 A の任意の同値関係 R に対して、 R の定める同値類の全体の集合は A の直和分割＊。 逆に A の任意の直和分割は A のある同値関係の 定める同値類の全体の集合に一致する。

6 商集合 A の R による分割，商集合 例： ３を法として合同な整数 の集合 Z の商集合 は
集合Aから、AのRによる商集合　　への写像f を　　　　　により定義すると、この f は全射。 Aから への標準的な(canonicalな)全射という.。

7 関係の合成 集合 A 上の関係の合成（積ともいう） 合成の繰返しをベキ乗として定義する （idA : A上の恒等関係）

8 関係の閉包 推移的閉包 (reflexive closure) 反射推移的閉包 (reflexive transitive closure)
推移的閉包は推移的である。 反射推移的閉包は反射的かつ推移的である。 性質：Rが推移的であれば、R+=Rである。

9 このa, b, c, dは注釈であり、行列の一部ではない
関係と隣接行列 このa, b, c, dは注釈であり、行列の一部ではない a b c d 有向グラフ (directed graph) 関係の合成は行列の積の０でない成分に対応 a b c d

10 Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学
次回の予告 基本的な仕組は数学的 グラフの行列による表現 　隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学 S学部 C学科 G研究室 WEBページのリンクの関係 行列の上と左のW, S, C, Gは注釈 であり行列に含まれない

11 隣接行列と閉包 隣接行列の定義 隣接行列の性質
行列Rnの(i,j)成分は、aiからajに至る長さnの相異なる道の数。（道のことを経路ともいう） 行列R*の(i,j)成分が０でないとき、 aiからajに至る道がある。到達可能。（長さ０の道もあり） Rを否定している斜線

12 二項関係と順序 () 次の三つの性質を満たす二項関係  を半順序 (partial order) という。半順序集合を posetという。 反射律 推移律 反対称律 さらに次の性質も満たすとき全順序 (total order) という。全順序を線形順序 (linear order) ともいう。 単に順序という場合には半順序のことを指す。 論理記号 or

13 順序集合 N, Z, R：数の大小関係 これは自明な順序。 複素数の集合 C：ここには自明な順序がない。
文字 (a～z, A～Z)の集合：それほど自明でない。 単語（文字列）：自明でない。 学校の成績：いろいろな計算法があり自明でない。 {red, green, blue} : 関係の定義が必要。 部分集合の間の順序：包含関係⊂は順序である。 {{ }, {red}, {green}, {blue}, {red,green}, {red,blue}, {green,blue}, {red,green,blue}} C や学校の成績にも特定の要素間には順序あり。

14 順序集合（部分集合、直積） 集合 A とその上の半順序  の組 < A,  > のこと。
例：順序集合の直積を順序集合にする方法は複数通り考えられる 直積順序：　 辞書式順序：lexicographic order

15 順序集合（N, 関数） N の自明な順序ではない順序がある。
例：m | n （m は n の約数という二項関係） これは順序である。ただし全順序ではない ［演習のヒント］反射的、推移的、反対称的。 Bが順序集合のとき、関数 f , g  A  B の間の順序を B 上の順序を使って定義できる。

16 狭義の順序 狭義の順序を、以下の二つの性質を満たす関係として定義する。 推移的： 非反射的：
演習：Rを狭義の順序とする。二項関係R*を次のように定義すると、R*は順序になる。 否定 not （詳しい説明は省略）

17 ハッセ (Hasse) の図式 Aの各要素a, bに対して平面上の点Pa , Pbをとる。a<b の時、PbをPaよりもY座標を大きな位置に描く。 b が a の直後の要素であるとき、PaとPbとを線分で結ぶ。この線分上にはPa , Pb以外の点は描かない。

18 直前の要素、直後の要素 順序集合 (A, ) において xA が aA の直後の要素 (successor) であるとは、次の性質を満たすこと。 同様に、直前の要素 (predecessor) を定義できる。 例：n ( N, n  0) の直前の要素は n  1 例：a (Q)の直前の要素は存在しない。 順序集合(A, )が稠密（ちゅうみつ）であるとは、任意のa, bAに対してa<bならば必ずa<c<bとなる c が存在することである。Qは稠密。 {1,2,3,5,30} {1,2,3,4,6,12} {1,2,4,8,16} {1,2,3,4,6,10,15,30}

19 ハッセ (Hasse) の図式の例 {red,green,blue} {red,green} {green,blue} {red,blue}
全順序 比較不能 {red,green,blue} {red,green} {green,blue} {red,blue} {red} {green} {blue} { }

20 擬順序 (quasi-order, preorder)
Jane(100) Smith(92) Tom(85) Mary(85) Pat(80) Bob(77) 別の例： 反射律と推移律を満たす関係（反対称律は満たさ なくてよい）を擬順序という。 　　　　　　　　　　　で定義される関係 ~ は同値関係になる。商集合 A/~ の上の二項関係 　　　　　　　　　は順序になる。

21 最大と極大 順序集合 (A, ) と、その部分集合Bがある。Bの要素 b が次の性質を満たすとき、bをBの最大元という。 ∀x∈B ( x  b ) maximum Bの要素 b が次の性質を満たすとき、bをBの極大元という。 ∀x∈B ( b  x ⇒ x=b ) maximal x y 極大元（２つある） z w u 最小元＝極小元 最大元が存在すれば、それが極大元。最大元は存在すれば一つ。 極大元は複数個が存在することがある。