ステップ S3-2-1

同値関係と類別

この ページで まなぶ こと

  • 同値関係の3条件（反射・対称・推移）がわかる
  • 同値関係が集合を類別することと mod n の計算がわかる

反射律（自分と同じ）・対称律（向きを返せる）・推移律（つなげる）をみたす関係が同値関係。同値関係は集合をもれなく重複なくグループ（同値類）に切り分ける。代表例が mod n——余りで仕分ける世界。

「同じとみなす」の条件

「＝」以外にも、数学は色々なものを「同じ」扱いしてきた。合同な三角形（G3）、相似な図形、約分したら等しい分数 1/2 と 2/4（N4）、17時と5時（N2の時計）……。

これらの「同じとみなす」に共通する骨格を抜き出そう。関係〜が同値関係であるとは：

  1. 反射律 ：a 〜 a（自分は自分と同じ）
  2. 対称律 ：a 〜 b なら b 〜 a（向きを返せる）
  3. 推移律 ：a 〜 b かつ b 〜 c なら a 〜 c（つなげる）

例1 ：「合同」は3条件をみたす ✓ 「相似」も ✓ では「x ＜ y」は？ 反射律が崩れる（x ＜ x は偽）——同値関係ではない。「xはyの友だち」は？ 推移律があやしい（友だちの友だちは友だちとは限らない）——日常の関係は案外きびしい。

同値関係は、世界を切り分ける

同値関係があると、集合は「互いに同値なものの集まり」——同値類——にもれなく、重複なく分割される（類別）。

なぜ重複しないか。もし2つのグループに共通要素cがあれば、対称律と推移律でグループ全体がつながって1つになってしまうから。3条件は、まさに「きれいに切り分けられる」ための必要十分な骨格なのだ。

最良の見本 — mod n

整数の関係「a 〜 b ⇔ a − b が n の倍数」（a ≡ b (mod n) と書く）は同値関係だ。「nでわった余りが同じ」という意味になる。

例2 ：mod 3 で整数を類別すると——

  • 余り0組：…、−3、0、3、6、9、…
  • 余り1組：…、−2、1、4、7、10、…
  • 余り2組：…、−1、2、5、8、11、…

無限にある整数が、たった3つの同値類に切り分けられた。

例3 ：今日が水曜日なら、100日後は何曜日？ 100 ＝ 7 × 14 ＋ 2 だから 100 ≡ 2 (mod 7)——2日後とおなじ金曜日。無限の日々を7つの類で扱う——曜日は人類最古の mod 計算だ。

例4 ：mod の世界では計算もできる。余り同士をたしてよい：25 ＋ 38 ＝ 63 の mod 7 は、4 ＋ 3 ＝ 7 ≡ 0。実際 63 ＝ 7 × 9 ✓ 「大きい数の余り」が「余りの計算」で出せる——この仕組みは暗号（RSA）の心臓部でもある。

分数の世界も実は類別だった：1/2、2/4、3/6、…は「約分すれば同じ」という同値関係のひとつの同値類。「分数」とは同値類に付けた名前だったのだ（N4の約分の正体！）。

よくあるまちがい

その1：3条件の確認を飛ばす。 「なんとなく同じっぽい」関係が3条件をみたすとは限らない（友だち関係の推移律）。同値関係と呼ぶ前に、3つを1つずつ確かめる。

その2：mod の計算で余りを最後にとる。 どちらでもよい（それが定理のありがたみ）が、大きい数を掛けてから余りをとるより、先に余りにしてから計算するほうが圧倒的に楽。25 × 38 (mod 7) は 4 × 3 ＝ 12 ≡ 5。

れんしゅう

Q1 きほん

同値関係の3条件は？

Q2 きほん

「x ＜ y」が同値関係でない理由は？

Q3 きほん

mod 3 の同値類はいくつある？

個

Q4 ふつう

100 ≡ □ (mod 7)。□は？

Q5 ふつう

25 ＋ 38 ≡ □ (mod 7)。□は？

Q6 ふつう

水曜日の100日後は？

Q7 チャレンジ

25 × 38 ≡ □ (mod 7)。□は？

もっと れんしゅう

ボタンを おすと、あたらしい もんだいが でて くるよ。なんかいでも れんしゅう できるよ。