2. 関係 五島 正裕

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

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

二項関係 (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

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

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

同値関係

同値関係 (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 複素数の実部が同じ, 虚部が同じ, 原点からの距離が同じ, ... 合同 ≡ ，平行∥ 同じ国の国民 （二重国籍がなければ）

同値関係の写像 写像 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

同値類 (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, …}

順序関係

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

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

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

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

ハッセ（線） 図 (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

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

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

上界／下界 上界 (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 (π, ∞) は下に有界, 上に有界でない

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

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

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

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

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

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

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

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

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