Presentation is loading. Please wait.

Presentation is loading. Please wait.

補遺:質問への解答(1) 順序対と非順序対(1回目の授業)

Similar presentations


Presentation on theme: "補遺:質問への解答(1) 順序対と非順序対(1回目の授業)"— Presentation transcript:

1 補遺:質問への解答(1) 順序対と非順序対(1回目の授業)
「二つのものを対(ペア)にする」 非順序対で順序対を定義できる <a, b>=def{{a}, {a,b}} そのまま同じになる訳ではありません A={u,v}, B={1,2} の例題で考えます 直積 A×B の要素と 集合 { {{a},{a,b}} }の要素を比べます

2 続:質問への解答(1) A={u,v}, B={1,2} の例題で考えます 直積 A×B = {<u,1>,<u,2>,<v,1>,<v,2>} 集合 { {{a},{a,b}} | a∈A, b∈B}= { {{u},{u,1}}, {{u},{u,2}}, {{v},{v,1}}, {{v},{v,2}} } 上の二つの集合は対等 (equipollent)です

3 補遺:質問への解答(2) 自然数と集合(2回目の授業)「配列と関数」 集合論では自然数を n={0,1,…,n-1}と定義
Wikipedia: 「自然数」が参考になる 自然数と集合(2回目の授業)「配列と関数」 集合論では自然数を n={0,1,…,n-1}と定義 定義: 0={ } (空集合) 1={0}={{ }} 2={0,1}={{ },{{ }}} 3={0,1,2} 5回目の授業に出てくる後者関数 S, successor function, S(n)=n∪{n} (和集合)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21 直前の要素、直後の要素 順序集合 (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}

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

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

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


Download ppt "補遺:質問への解答(1) 順序対と非順序対(1回目の授業)"

Similar presentations


Ads by Google