Animated Logo

同値関係

目次

関係とは

半順序集合

同値関係

写像のグラフ

テストの前に

TEST

 半順序関係に並んで重要な関係に同値関係( equivalence relation)があります。これは反射的、対称的かつ推移的な関係をいいます。すなわち、

  1. x 〜R x

  2. x 〜R y imp y 〜R x

  3. x 〜R y and y 〜R z imp x 〜R z

の3つの条件がいえるとき、R は同値関係と言われるのです。

 同値関係は必ずしも反対称的ではありません。

 例1: X を整数全体の集合とする。すなわち、X = { ...,-2,-1,0,1,2,3,...} である(整数全体の集合は Z または INT などと書いて表す)。今整数 p を一つ固定して考える。 R = {(n,m): n ≡ m (mod p)} とする。 ここで、n ≡ m (mod p) というのは n と m の差が整数 p で割り切れる、ということを表す式である。 n ≡ m (p) と略記することもある。「n と m はモジュラー p で等しい(n equals m modulo p)」と読む。このとき R は同値関係である。

 上の例は、整数の集合においてモジュラーで等しい、という関係が同値関係になっていることを言っています。このように、同値関係というのは異なるもの同士でもある意味で等しい、ということを表します。

 同値関係 R があれば集合 X の中を分類することができます。同値とみなせる要素同士を集め、X のひとつの部分集合と考えるのです。今 X の要素 x に対して次のような集合 A(x) を考えます。

  A(x)={ y: y ∈ X and x 〜R y}

 A(x) に属する全ての要素は互いに同値です(論理式で書くと、(∀z1)(∀z2)(z1∈ A(x) and z2 ∈ A(x) imp z1 〜R z2))。

 このような部分集合 A(x) を同値類(どうちるい equivalence class)と言います。

 同値類に関しては次のような式が成立します。

 1.x 〜R y eqv A(x) = A(y)

 2.A(x) ≠ A(y) eqv A(x) ∩ A(y) = φ

 3.x 〜R y eqv (∃z)(x ∈ A(z) and y ∈ A(z))

 同値類の全体の集合は集合 X の分割(partition)になっています。分割とは X の部分集合を要素とする集合 α で、

 1.(∀B1)(∀B2)(B1∈α and B2 ∈ α imp B1 = B2 or B1 ∩ B2 = φ)

 2.(∀x)(x ∈ X imp (∃B)(x ∈ B))

の2つの式が成立するものです。1.の条件は分割の要素は互いに重ならないこと、2.の条件は X が分割の要素で覆われていることを表します。イメージを図にしますと、

これは α = {A1,A2,A3,A4,A5} が X の分割になっている例です。