同値関係（数学）

形式的定義と直接の帰結

X を集合、R を X×X の部分集合とする。X のすべての x について x R x が成り立つとき、R は反射的であるという。x R y ならば y R x も成り立つとき、R は対称的であるという。さらに、x R y かつ y R z ならば x R z が成り立つとき、R は推移的であるという。この三条件がそろうことにより、R は首尾一貫した同値の概念として振る舞う。すなわち、各要素は自分自身と同値であり、同値は双方向に成り立ち、連鎖に沿って伝わる。各性質については、対称性および推移性の項目も参照されたい。

X 上の同値関係 R と X の要素 a が与えられたとき、[a] と表す a の同値類とは、a と関係をもつ X のすべての要素からなる部分集合である。同値類は、互いに一致するか、または互いに素である。すなわち、任意の二つの類は同じ集合であるか、共通部分が空集合であるかのいずれかである。すべての同値類からなる族は X の分割を形成する。逆に、X の任意の分割は同値関係を定める。二つの要素が同値であるのは、それらが同じブロックに属するとき、かつそのときに限る。この対応の背景については、分割を参照されたい。

すべての同値類からなる集合は、しばしば X/~ または X/R と表される。X から X/~ への自然な全射があり、これはしばしば標準射影または商写像と呼ばれる。この写像は各要素をその同値類へ写す。多くの代数的・圏論的文脈において、この射影は普遍性をもつ。すなわち、各同値類上で定数である X 上の写像は、商を経由して一意に因子化する。

例

以下の例は、同値関係が広く現れる理由を示している。

1. 整数における n を法とする合同：二つの整数の差が n で割り切れるとき、それらは同値である。同値類は n を法とする剰余類であり、数論および合同算術の中心的な概念である。
2. 剛体運動を除いて同じ形であること：二つの幾何学図形について、一方を伸縮させずに移動して他方と重ね合わせられるとき、それらは同値である。この考え方は幾何学における合同の基礎となる。
3. ある個体群において同じ種に属すること：動物を種によって分類することは直観的な例である。二匹の動物は、同じ種に属するときに同値である。簡単な動物の種の図解はこちら、説明はこちらを参照されたい。
4. 関数の核：関数 f:X→Y が与えられたとき、f(x)=f(y) である場合に x~y と定める。これは同値関係であり、その類は f のファイバーである。この構成は、多くの代数的商を説明する。

同値関係は、ある性質がほとんど至る所で成り立つことを要求する場合にも現れる。たとえば、二つの関数が測度ゼロの集合を除いて一致するとき、それらを同値と定めることがある。このような関係は、関数解析学と測度論において基本的である。

商と代数的構成

同値類の集合、すなわち商を作ることは、多くの数学的構成における重要な段階である。代数学では、二つの要素の差が固定された正規部分群またはイデアルに属するときに両者を同値と定めることで、商群、商環、商加群が得られる。位相数学では、同値関係に従って点を同一視し、類の集合に商位相を与えることで商空間が構成される。このような商構成は、同値な対象を一つの対象へとまとめることにより、複雑さを体系的に減少させる。

商へ移る過程には自然な制約がある。X 上の追加構造、たとえば代数演算や位相は、同値関係がその構造と両立するときにのみ、しばしば商へ構造を誘導する。群論では、この両立性は正規部分群という概念によって捉えられる。位相数学では、商写像が適切な性質をもつ連続写像となるような同値関係であることが求められる。

実用と計算上の側面

計算機科学では、同値関係は有限オートマトンの状態最小化、分割を効率よく維持する union-find アルゴリズム、ならびに同値なプログラム状態や型を同定する必要がある型システムとプログラム解析に現れる。効率的なデータ構造は、同値関係が分割であるという性質を利用する。要素対ごとの関係を記憶する代わりに、各ブロックとその代表要素を表現するのである。

さらなる学習や初等的な演習については、集合論、抽象代数学、位相数学の標準的な教科書が、分割および商構成とともに同値関係の理論を展開している。概説記事や講義ノートには、解答を伴う例や応用が掲載されている。同値類の簡潔な概説はこちらを参照されたい。

要するに、同値関係は、対象間のある差異を無視することを簡潔に形式化する方法である。数学の多くの分類方式を支え、問題を単純化する商対象の形成を可能にし、分割という組合せ論的概念、ならびにグループ化と同定のための実用的なアルゴリズムと直接結び付いている。