←講義のツボメニューへ
情報学基礎Ａ
【2000.10.17】 【第４回】 【菊池大輔】
集合〜set〜
（３）
（１）二項関係
-
大小関係、前後関係などというように２つの対象の間に成り立つ関係を二項関係という。
-
あるaとbの間に二項関係が成り立っているとき aRb と書く。
例）
Ａ＝{青森県,岩手県,秋田県},Ｂ＝{青森市,盛岡市,秋田市},Ｒ＝{a∈Ａの県庁所在地はb∈Ｂである}
青森県Ｒ青森市
直積集合Ａ×Ｂの部分集合{(a,b)|a∈A,b∈B,aRb}
この集合を関数Ｒのグラフという。
G(R)={(a,b)|a∈A,b∈B,aRb}
先の例において二項関係Ｒのグラフで表すと、
Ｇ（Ｒ）＝{（青森県,青森市）,（岩手県,盛岡市）,（秋田県,秋田市）}
- 二項関係の性質。Ｒを集合Ａ上の二項関係とする。
- 反射律・・・全てのx∈ＡについてxＲx
- 推移律・・・x,y,z∈Ａについて
xＲyかつyＲz⇒（ならば）xＲz
- 対称律・・・x,y∈Ａについて
xＲy⇒yＲx
- 反射律、推移律、対称律を全て満たした関係を同値関係という。
（２）写像
写像〜mapping〜
集合ＳとＴがあってＳの任意の要素に対しても、あるＴの要素が１つ対応するとき、この対応のさせ方を写像という。写像をfとするとf:S→Tと書く。
Ｓ：定義域（domain）
Ｔ：終域（値域）（codomain）
（３）関数の分類
- 単射・・・関数f:X→YにおいてXの異なる要素xとx’のfによる像f(x),f(x')がいつも異なるとき、すなわち、x≠x'⇒f(x)≠f(x')がいつも成り立つとき、fはＸからＹへの単射（ＸからＹへの１体１の関数）という。
- 全射・・・関数f:X→Yの値域f(x)が終域Ｙと一致するとき、すなわち、f(X)=YのときfはＸからＹへの全射（ＸからＹ上への関数）という。