2015/12/16

同値関係といろいろな例

分野: 代数,情報・暗号理論  レベル: 大学数学

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

二項関係とは

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

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

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

同値関係とは

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

  • 反射律:$a\sim a$
  • 対称律:$a\sim b$ ならば $b\sim a$
  • 推移律:$a\sim b$ かつ $b\sim c$ ならば $a\sim c$

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

同値関係のいろいろな例

例題1(整数論)

$A$ を整数全体の集合,$n$ を正の整数とする。 $a,b\in A$ に対して
$a\sim b$ $\iff$ $a-b$ が $n$ の倍数
とするとき $\sim$ は同値関係であることを証明せよ。

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

解答

反射律:$a-a=0$ は $n$ の倍数
対称律:$a-b$ が $n$ の倍数なら $b-a$ も $n$ の倍数
推移律:$a-b,b-c$ が $n$ の倍数なら,その和 $a-c$ も $n$ の倍数

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


例題2(図形)

$A$ を三角形全体の集合とする。 $a,b\in A$ に対して
$a\sim b$ $\iff$ $a$ と $b$ は合同
とするとき $\sim$ は同値関係であることを確認せよ。


例題3(グラフ理論)

$A$ を有向グラフ $G$ の頂点集合とする。 $a,b\in A$ に対して
$a\sim b$ $\iff$ 頂点 $a$ から $b$ に道があり,$b$ から $a$ にも道がある
とするとき $\sim$ は同値関係であることを確認せよ。

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


例題4(線形代数)

$M_n$ を $n\times n$ 行列全体の集合とする。 $A,B\in M_n$ に対して
$A\sim B$ $\iff$ ある正則行列 $P$ が存在して $B=P^{-1}AP$
とするとき $\sim$ は同値関係であることを確認せよ。

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

「友達」は同値関係ではありません。 $a$ は $b$ を友達だと思っていても $b$ は $a$ のことを友達だと思っていないかもしれません。
分野: 代数,情報・暗号理論  レベル: 大学数学