概念・定理図鑑 · 基礎から応用へ

同値関係:何を同じとみなすかを三つの性質で決める

反射性・対称性・推移性を、整数の余りと近似比較の反例から確かめます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 同じという判断にも規則が必要
  2. 三つの条件を順に調べる
  3. 余りが同じ整数をまとめる
  4. 同値類は重ならず全体を覆う
  5. 近似比較の反例を確認する
  6. 正規化関数から関係を作る
  7. この記事をロゲイアに質問する理解を確かめる

同じという判断にも規則が必要

二つの値を同じと扱う場面でも、何を比較するかは用途で違います。文字列が完全に一致することと、大文字小文字を無視して一致することは別の関係です。同値関係は、この「同じとみなす」規則が満たす三つの性質をまとめたものです。対象となる集合を先に決め、その中の任意の要素について規則が成り立つかを確認します。一部のデータでうまく動いたというだけでは十分ではありません。例えば利用者名を比較するなら、文字コードの正規化、大小文字、空白をどう扱うかも規則の一部です。見た目が似ているという直感だけを、保存済みの識別子の一致へ置き換えないようにします。

三つの条件を順に調べる

反射性は、どの要素aも自分自身と関係することです。対称性は、aがbと関係するならbもaと関係することです。推移性は、aがbと関係し、bがcと関係するならaもcと関係することです。三つの条件は別々に調べます。「近い」という言葉でまとめても、自分に近いことや互いに近いことだけでは推移性は分かりません。また、反射性を省いて対称性と推移性だけを示しても、元の集合の全要素を分類できるとは限りません。すべての要素が自分自身の属する同値類を持つために、反射性が必要です。

余りが同じ整数をまとめる

整数aとbについて、a−bが3の倍数なら関係すると定めます。a−aは0なので反射的です。a−bが3の倍数なら符号を逆にしたb−aも3の倍数で、対称性が成り立ちます。さらにa−bとb−cが3の倍数なら、和のa−cも3の倍数になり、推移性も示せます。例えば1、4、7は同じグループですが、2は別です。ここで、列に並んだ順番や数の大きさはグループを決めません。負の整数も、差が3で割り切れるかという同じ定義で扱えます。プログラミング言語ごとの剰余演算の符号の違いと、数学上の関係を区別して実装します。

同値類は重ならず全体を覆う

aと関係する要素をすべて集めた集合をaの同値類と呼びます。同値関係なら、二つの同値類が一つでも要素を共有すると、実は同じ集合になります。別々の類が一部だけ重なる状態にはなりません。3による合同関係なら、余り0、1、2に対応する三つの類が整数全体を分けます。各類から代表を一つ選ぶことはできますが、代表の選び方が関係の定義を変えるわけではありません。例えば1と4のどちらを代表とするかは便宜上の選択です。集合を分類する問題と、画面に表示する代表値を決める問題を分けると、データ処理の意味を説明しやすくなります。

近似比較の反例を確認する

実数a、bの差の絶対値が1未満なら同じとする規則を考えます。0と0.6は同じ、0.6と1.2も同じですが、0と1.2は同じではありません。反射性と対称性はあっても、推移性がないため同値関係ではありません。この規則を重複排除のキーにすると、比較する順番でグループが変わるおそれがあります。一定の区間へ丸める方法なら別の分類を作れますが、区間の境界付近に近い二点が別類になるという性質も生じます。近似の許容範囲と、一貫した分類という要求は同じではありません。欲しい結果を先に定め、関係の性質と照らし合わせて設計します。

正規化関数から関係を作る

同じ正規化関数cを使い、c(a)=c(b)なら同じとする規則を作れば、等号の三性質から同値関係を説明できます。ただし正規化の仕様が途中で変わると、以前の分類と一致しなくなる場合があります。入力値そのものと正規化後の値を区別し、版を変えたときの既存データの扱いも定めます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 13

学習コースから次を選ぶ