同値関係といろいろな例

数学の様々な場面で登場する重要な概念「同値関係」について解説します。同値関係とは,大雑把には「仲間であるという関係」です。前半は定義なので少し堅苦しいですが,後半はいろいろな例が登場します!

二項関係とは

同値関係についてきちんと定義するために,まずは二項関係について解説します。

集合 AA 上の二項関係とは,AA の要素を2つ並べたものをいくつか集めた集合です。例えば A={1,2,3}A=\{1,2,3\} に対して,{(1,2),(2,1),(3,1),(3,3)}\{(1,2),(2,1),(3,1),(3,3)\} は二項関係です。

(a,b)(a,b) が考えている二項関係に属するとき,aba\sim b と書くことにします。上の例では 121\sim 2212\sim 1313\sim 1333\sim 3 です。

同値関係とは

同値関係とは,以下の3つを満たす二項関係 ~ のことです。

  • 反射律:aaa\sim a
  • 対称律:aba\sim b ならば bab\sim a
  • 推移律:aba\sim b かつ bcb\sim c ならば aca\sim c

1つめはさておき,2つめと3つめは「仲間であるという関係」を表していると理解できます(aabb の仲間なら bbaa の仲間,aabb が仲間で bbcc が仲間なら aacc は仲間)。

なぜ同値関係を考えるのか

「=」は左辺と右辺が(数値・集合として)完全に一致するときに用いられます。これはしばしば条件として「厳しい」場合があります。

例えば,C1C_1 を中心が (0,0)(0,0) で半径が 11 の円,C2C_2 を中心が (1,1)(1,1) で半径が 11 の円としましょう。これらは位置の意味では異なりますが,合同です。

「同じ」であることをもっと幅広く考えたい……そのために同値関係があります。いわば同値関係は 「=」の一般化 と考えられます。

同値関係のいろいろな例

例題1(整数論)

AA を整数全体の集合,nn を正の整数とする。a,bAa,b\in A に対して

ab    aba\sim b\iff a-bnn の倍数

とするとき \sim は同値関係であることを証明せよ。

nn で割った余りによって整数をグループ分けするという考え方です。→合同式

解答

反射律: aa=0a-a=0nn の倍数

対称律: aba-bnn の倍数なら bab-ann の倍数

推移律: ab,bca-b,b-cnn の倍数なら,その和 aca-cnn の倍数

このように,同値関係であることの確認は簡単なことが多いです。以下,例題の解答は省略します。

例題2(図形)

AA を三角形全体の集合とする。a,bAa,b\in A に対して

ab    aa\sim b \iff abb は合同

とするとき \sim は同値関係であることを確認せよ。

例題3(グラフ理論)

AA を有向グラフ GG の頂点集合とする。a,bAa,b\in A に対して

ab    a\sim b \iff 頂点 aa から bb に道があり,bb から aa にも道がある

とするとき \sim は同値関係であることを確認せよ。

この同値関係による頂点のグループ分けをグラフの強連結成分分解と言います。→強連結成分分解の意味とアルゴリズム

例題4(線形代数)

MnM_nn×nn\times n 行列全体の集合とする。 A,BMnA,B\in M_n に対して

AB    A\sim B \iff ある正則行列 PP が存在して B=P1APB=P^{-1}AP

とするとき \sim は同値関係であることを確認せよ。

なお,例題4の意味で ABA\sim B のとき,行列 AABB は相似であると言います。→行列の対角化の意味と具体的な計算方法

例題5(幾何・線形代数)

R3\{O}\mathbb{R}^3 \backslash \{ \mathrm{O} \}xyzxyz 平面から原点を除いたものとする。

(x,y,z),(x,y,z)R3\{O}(x,y,z) , (x' , y' , z') \in \mathbb{R}^3 \backslash \{ \mathrm{O} \} に対して

(x,y,z)(x,y,z)    (x,y,z) \sim (x' , y' , z') \iff ある 00 でない実数 kk があって,x=kxx = kx'y=kyy = ky'z=kzz = kz'

とするとき,\sim は同値関係であることを確認せよ。

この同値関係により,幾何的に極めて重要な概念である射影平面が定義されます。

同値類・商集合

  • もとの集合を「同値な仲間ごと」にグループわけした各グループを同値類と言います。

  • 例えば,上記の例題1の同値関係でグループわけすると「nn の倍数のグループ」「nn で割ったあまりが 11 のグループ」…のようにグループが nn 個できます。もとの集合(整数全体の集合)から同値類が nn 個できました。

  • xx が属する同値類のことを [x][x]xˉ\bar{x} などと書きます。

  • 同値類全体の集合を商集合と言います。もとの集合 SS を同値関係 \sim でグループわけしたときの商集合を S/ ⁣S /\! \sim と書きます。

  • 上記の例題1の場合,S/ ⁣={[0],[1],[2],...,[n1]}S /\! \sim=\{[0],[1],[2],...,[n-1]\} となります。

「友達」は同値関係ではありません。aabb を友達だと思っていても bbaa のことを友達だと思っていないかもしれません。