同値関係(反射率、対称律、推移律)

同値関係(反射率、対称律、推移律)

 今までの数学で用いてきた等号 ( = ) について、次のような関係が成り立つことは暗黙の了解としてきたはずです(普段は意識することもないと思います)。

 ① 反射律 $a=a$
 ② 対称律 $a=b$ ならば $b=a$
 ③ 推移律 $a=b,\:b=c$ ならば $a=c$

 ある集合の2元同士の関係 R が上の条件を全て満たせば 同値関係 (equivalence relation) にあるといいます。もちろん関係の種類によっては ① ~ ③ の全てを満たさない場合もあります。たとえば自然数 $b$ が自然数 $a$ で割り切れる、すなわち $a\:|\:b$ という関係を考えたときに上の3つの条件を順にチェックしていくと

 ① $a\:|\:a$ が成り立つので、反射律を満たします。
 ② $a\:|\:b$ だからといって、$b\:|\:a$ は成立しないので対称律は満たしていません。
 ③ $a\:|\:b,\:\:b\:|\:c$ ならば $a\:|\:c$ が成り立つので推移律を満たしています。

 ② の条件を満たさないので、$a\:|\:b$ は同値関係ではありません。
 

合同記号の同値関係

 結論を先に言えば、整数の合同は同値関係を満たします。

 ① 反射律 $a\equiv a\quad (\mathrm{mod}\;m)$
 ② 対称律 $a\equiv b\quad (\mathrm{mod}\;m)$ ならば $b\equiv a\quad (\mathrm{mod}\;m)$
 ③ 推移律 $a\equiv b,\:b=c\quad (\mathrm{mod}\;m)$ ならば $a\equiv c\quad (\mathrm{mod}\;m)$

[① 反射律の証明]
 $m\:|\:a-a\quad (\mathrm{mod}\;m)$ なので $a\equiv a\quad (\mathrm{mod}\;m)$

[② 対称律の証明]
 $m\:|\:a-b\quad (\mathrm{mod}\;m)$ より
 $m\:|\:-(a-b)\quad (\mathrm{mod}\;m)$
 $m\:|\:b-a\quad (\mathrm{mod}\;m)$
 $\therefore b\equiv a\quad (\mathrm{mod}\;m)$

[③ 推移律の証明]
 $a\equiv b\quad (\mathrm{mod}\;m)$ なので $b=a+sm$
 $b\equiv c\quad (\mathrm{mod}\;m)$ なので $c=b+tm$
 $c=a+(s+t)m\quad\therefore a\equiv c\quad (\mathrm{mod}\;m)$

 ちなみに「合同」と聞けば小学校の時に習った「三角形の合同」を思い浮かべるかたも多いと思いますが、もちろん「三角形の合同」は同値関係にあります。ぜひ確認してみてください。

 ≫ 剰余類 ≫ 初等整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください