3.5 2項関係

3.5 2 項関係
関係 : R(⊆ A × A) を A 上の 2 項関係という
• 例: {a, b, c} 上の 2 項関係 R = {(a, b), (b, c)}。
逆関係 : R の逆関係 R−1 = {(x, y) | (y, x) ∈ R}
合成 : A 上の関係 R, R′ に対して、
• R ◦ R′ = {(x, z) | ∃y ∈ A (x, y) ∈ R ∧ (y, z) ∈ R′}
• R0 = {(x, x) | x ∈ A}, Rn+1 = Rn ◦ R (n ≥ 0)
• R+ =
[
n≥1
Rn , R∗ =
[
Rn
n≥0
例 : 上の R に対して R∗ = R∪{(a, a), (b, b), (c, c), (a, c)}
1
記法 : (x, y) ∈ R であることを、xRy とも書く
関係の性質
• 反射律： ∀x ∈ A xRx (R0 ⊆ R とも表せる)
• 推移律： ∀x, y, z ∈ A xRy ∧ yRz =⇒ xRz
• 対称律: ∀x, y ∈ A xRy ⇐⇒ xRy
• 反対称律: ∀x, y ∈ A xRy ∧ yRx =⇒ x = y
2
R′ は R の P 閉包 : R′ は、R ⊆ R′ かつ P を満たす最小の
関係
• 例: R+ は、R の推移的閉包
R∗ は、R の反射的推移的閉包
3
3.6 順序関係と同値関係
3.6.1 順序関係
順序 : 反射律、推移律、反対称律を満たす関係
• 例: N 上の順序 ≤,
2A 上の順序 ⊆ (集合の包含)
全順序 : ∀x, y ∈ A xRy ∨ yRx を満たす順序 R
• 例: ≤ ∈ N × N は全順序だが, ⊆ ∈ 2A × 2A は (一般
に) 全順序でない
4
3.6.2 同値関係
同値関係 : 対称律、反射律、推移律を満たす関係
• 例 A = {a, b, c, d} 上の関係 R = {(a, b), (b, c)} に対
して、
∼ = (R ∪ R−1)∗ は同値関係
x ∈ A の同値類 : [x]∼ = {y | x ∼ y}
• 例 [a]∼ = [b]∼ = [c]∼ = {a, b, c}, [d]∼ = {d}
∼ による A の同値分割 : A/∼ = {[x]∼ | x ∈ A}
• 例 A/∼ = {{a, b, c}, {d}}
5

Download Report