2. 関係 五島 正裕.

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

1 2. 関係 五島 正裕

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

3 二項関係 (binary relation)
集合 X, Y の要素 x, y について，関係 R ⊂ X × Y が成り立つ x R y ⇔ (x, y) ∈ R 例) X = {0, 1, 2, 3, 4} Y = {2, 3, 5, 7, 11} x R y = 「x は y より 2 小さい」 R = {(0, 2), (1, 3), (3, 5)} X = Y の場合, R を「X の上の関係」という

4 多項間の関係 集合 X1, X2, ..., Xn について，x1, x2, ... , xn の間に
関係 R ⊂ X1× X2 × ... × Xn が成り立つ R(x1, x2, ... , xn) ⇔ (x1, x2, ... , xn) ∈ R

5 同値関係

6 同値関係 (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 複素数の実部が同じ, 虚部が同じ, 原点からの距離が同じ, ... 同じ国の国民 (二重国籍がなければ)

7 同値関係の写像 X から Y への写像 f : X → Y があるとき x R y ⇔ f (x) = f (y)
例） f (x) = x mod 7

8 同値類 (equivalence class)
R[x] = { y | x R y } ⊂ X x : 代表元 (representative) x R y ⇒ R[x] = R[y] ⇒ 同値類は代表元の選び方によらない 異なる同値類は共通要素を持たない 例） 偶数 奇数 7 で割った余りが同じ

9 類別 と 商集合 類別 (classification)：元の集合 X をその同値類の直和に分割すること
X1 ∪ X2 ∪ … ∪ Xn = X i ≠ j ならば Xi ∩ Xj = φ 商集合 (quotient set)：類別の結果得られる部分集合の集合 X/R = {X1, X2, … , Xn}

10 同値関係の強弱 X の上のふたつの同値関係 R1, R2 について R1 は R2 より強い ⇔ R1 ⊂ R2 (より細かく類別)
例） modulo 21 の類別は, modulo 7 の類別より細かい

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 が存在 例） x – y 平面上の点の原点からの距離

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 の極大元という

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

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

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

22 実数 極小元 極大元 最小元 最大元 下限 上限 [0, 1] 下界 上界 下限 上限 (0, 1) 下界 上界

23 例題 部分集合 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

24 答え 極大元：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

25 例題 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