2. 関係 五島 正裕.

Presentation on theme: "2. 関係 五島 正裕."— Presentation transcript:

1 2. 関係 五島 正裕

2 関係 関係： いくつかのものごとの間に成り立つかどうかを云々 対象とするものごとの集合の直積の部分集合として定義

3 二項関係 (binary relation)
集合 X, Y の要素 x, y について関係 R が成り立つ R ⊆ X × Y （関係 R は，直積 X × Y の部分集合） x R y ⇔ (x, y) ∈ R X = Y の場合, R を「X の上の関係」という

4 二項関係 (binary relation) の例
X = {0, 1, 2, 3} Y = {1, 3, 5, 7} X × Y = { (0, 1), (0, 3), (0, 5), (0, 7), (1, 1), (1, 3), (1, 5), (1, 7), (2, 1), (2, 3), (2, 5), (2, 7), (3, 1), (3, 3), (3, 5), (3, 7)} x R y = 「x は y より 2 小さい」 R = {(1, 3), (3, 5)} 1 3 5 7 2

5 二項関係 (binary relation) の例
例： X = {イヌ, ネコ, クモ} Y = {ネズミ, サカナ, チョウ} X × Y = { (イヌ, ネズミ), (イヌ, サカナ), (イヌ, チョウ), (ネコ, ネズミ), (ネコ, サカナ), (ネコ, チョウ), (クモ, ネズミ), (クモ, サカナ), (クモ, チョウ)} x 捕食 y = 「x は y を捕食する」（補食関係） R = {(イヌ, ネズミ), (ネコ, ネズミ), (ネコ, サカナ), (クモ, チョウ)} ネズミ サカナ チョウ イヌ 1 ネコ クモ

6 重要な関係 同値関係 順序関係 …

7 同値関係

8 同値関係 (equivalence relation)
定義： 反射的 (reflexive) x R x 対称的 (symmetric) x R y ⇒ y R x 推移的 (transitive) x R y and y R z ⇒ x R z 例） x = y 複素数の実部が同じ, 虚部が同じ, 原点からの距離が同じ, ... 合同 ≡ ，平行∥ 同じ国の国民 （二重国籍がなければ）

9 同値関係の写像 写像 f に対して f (x) = f (y) ⇔ x R y と定義すると，R は同値関係 f (x) の例：
x mod 3 real(x), im(x), |x|, ... nationality(x) f (x) = x mod 3 0, 3, 6, ... 1, 4, 7, ... 1 2, 5, 8, ... 2

10 同値類 (equivalence class)
R[x] = { y | x R y } x : 代表元 (representative) x R y ⇒ R[x] = R[y] ⇒ 同値類は代表元の選び方によらない 異なる同値類は共通要素を持たない 例） 奇数，偶数 R[0] = {0, 2, 4, …}, R[1] = {1, 3, 5, …} 7 で割った余りが同じ R[0] = {0, 7, 14, …}

11 順序関係

12 順序関係 (order relation) 定義： 反射的 x R x 反対称的 x R y and y R x ⇒ x = y
推移的 x R y and y R z ⇒ x R z 例) ≦ 数の大小関係 ⊆ 集合の包含関係 数の大上関係以外の一般の順序関係も ≦ で表すことがある

13 全順序 全順序 (total order)，線型順序 (linear order)
すべての x, y ∈ X について x ≦ y または y ≦ x 例) 数の大小関係

14 半順序 半順序 (partial order) 全順序ではない一般の順序
半順序集合 (partially ordered set, po-set) 例） 集合 A = {a, b, c} の巾集合 2A の 要素の包含関係 {a, b, c} {a, b} {c, a} {b, c} {a} {b} {c} {}

15 擬順序 (pseudo-order) 反射的, 推移的だが反対称的でないもの
x R y かつ y R x かつ x ≠ y なる x, y が存在 例） 平面上の点の原点からの距離 P ≦ Q かつ Q ≦ P かつ P ≠ Q y Q P O x

16 ハッセ（線） 図 (Hasse’s diagram)
DAG (Directed Acyclic Graph) 推移律からわかる余分な arc の除去 平面グラフとは限らない 例: 3次元立方体 a ｂ c d e f g h i j k l m n o X p

17 極大元，極小元 上　界，下　界 最大元，最小元 上　限，下　限

18 極大元／極小元 極大元 (maximal element)／極小元 (minimal element)
x ∈ X に対し，x ≦ y かつ x ≠ y という y ∈ X が存在しないとき，つまり， x ∈ X に対し，x < y という y ∈ X が存在しないとき， x を X の極大元という 「X の要素で，X の中にそれより大きい要素がないもの」

19 上界／下界 上界 (upper bound)／下界 (lower bound)
半順序 ≦ が定義されている集合 S の部分集合 X で、 任意の x ∈ X に対し x ≦ a であるような a ∈ S があるとき X は上に有界 a を X の上界という 「X のどの要素『以上』のもの．X の要素であってもなくてもよい」 例） { 0, 1, 2, 3, 4, 5, 6 } の部分集合 {1, 2, 4} の上界は 4, 5, 6 (π, ∞) は下に有界, 上に有界でない

20 最大元／最小元 最大元 (maximum)／最小元 (minimum) 上界／下界 a が X に属するとき，a を最大限／最小限という
max(X)／min(X) 「他のどの要素『以上』の X の要素」 例) [0, π] の最大元は π (0, π) には，π は属さないので，最大元はない 集合全体の最大元／最小元 (あれば) T: トップ ／ ⊥: ボトム

21 上限／下限 上限（supremum, minimum upper bound ：最小上界）／ 下限（infimum, maximum lower bound ：最大下界） 部分集合 X の上界（の集合）の最小元を，上限という／ 部分集合 X の下界（の集合）の最大元を，下限という sup(X), inf(X) 例） (0, π) の上限は π 開区間でも存在する（ことがある）

22 極大元，上界，最大元，上限 極大元 「X の中にそれより大きい要素がないもの．X の要素」 上界
上界（の集合）の最小元

23 最大元と極大元 全順序集合 最大限 ＝ 極大元 半順序集合 最大元がないことがある 右図 X a ｂ c d e f g h i j k l
m n o X p

24 上限/下限の意味 開区間 最大限/最小限 はない 極大元/極小元 もない 上限/下限はある 極小元 極大元 最小元 最大元 下限 上限
[0, 1] 下界 上界 下限 上限 (0, 1) 下界 上界

25 例 上界 上界 最大元 上限 上限 極大元 極大元 最大元なし

26 例題 部分集合 X の 極大元、極小元 上 界、下 界 最大元、最小元 上 限、下 限 をすべて挙げよ X a ｂ c d e f g h
上　界、下　界 最大元、最小元 上　限、下　限 をすべて挙げよ a ｂ c d e f g h i j k l m n o X p

27 答え 極大元：d, g；極小元：i, j 上界：b；下界： m, o, p X のどの要素 x についても x ≦ b
m ≦ x, o ≦ x, p ≦ x 最大元 ：なし；最小元：なし 上界，下界はいずれも X の元ではな い 上限：b；下限：m 上界の集合 {b} の最小限は b 下界の集合 {m, o, p} の最大元は m a ｂ c d e f g h i j k l m n o X p

28 例題 2 部分集合 X の 極大元、極小元 上 界、下 界 最大元、最小元 上 限、下 限 をすべて挙げよ X a ｂ c d e f g
上　界、下　界 最大元、最小元 上　限、下　限 をすべて挙げよ a ｂ c d e f g h i j k l m n o X p