1. 高校数学の美しい物語
  2. 同値関係といろいろな例

同値関係といろいろな例

更新日時 2021/03/07

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

目次
  • 二項関係とは

  • 同値関係とは

  • 同値関係のいろいろな例

二項関係とは

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

集合 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 は仲間)。

同値関係のいろいろな例

例題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 は相似であると言います。→行列の対角化の意味と具体的な計算方法

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

人気記事
  1. 高校数学の美しい物語
  2. 同値関係といろいろな例