同値関係

数学において、同値関係は、反射的、対称的、推移的な二項関係です。幾何学における線分間の同値関係は、同値関係の一般的な例です。より簡単な例は、等式です。任意の数は、それ自体に等しいです (反射的)。 の場合、 です (対称的)。かつの場合、 です(推移的)。 ${\displaystyle a}$${\displaystyle a=b}$${\displaystyle b=a}$${\displaystyle a=b}$${\displaystyle b=c}$${\displaystyle a=c}$

各同値関係は、基になるセットを互いに重ならない同値クラスに分割します。指定されたセットの 2 つの要素は、同じ同値クラスに属する 場合にのみ、互いに同値です。

文献では、集合の 2 つの要素とが同値関係に関して同値であることを示すためにさまざまな表記法が使用されています。最も一般的な表記法は、が暗黙的に指定されるときに使用される「 」と「a ≡ b 」で、明示的に指定する場合は「 」、「a ≡ _R b」、または「 」のバリエーションが使用されます。同値でない場合は、「 a ≁ b」または「 」と記述されることがあります。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle R;}$${\displaystyle a\sim b}$${\displaystyle R}$${\displaystyle a\sim_{R}b}$ ${\displaystyle {a\mathop {R} b}}$${\displaystyle R}$${\displaystyle a\not \equiv b}$

集合上の二項関係は、それが反射的、対称的、推移的である 場合に限り、同値関係であると言われる。つまり、すべての集合において、${\displaystyle \,\sim \,}$${\displaystyle X}$${\displaystyle a,b,}$${\displaystyle c}$${\displaystyle X:}$

• ${\displaystyle a\sim a}$（再帰性）。
• ${\displaystyle a\sim b}$(対称性)の場合に限ります。${\displaystyle b\sim a}$
• ならば（推移性）。${\displaystyle a\sim b}$${\displaystyle b\sim c}$${\displaystyle a\sim c}$

${\displaystyle X}$関係式と合わせて集合体と呼ばれる。 の同値類は次のように定義される[ ^{1] [2]}${\displaystyle \,\sim \,}$${\displaystyle a}$${\displaystyle \,\sim ,}$${\displaystyle [a],}$${\displaystyle [a]=\{x\in X:x\sim a\}.}$

関係代数では、と が関係である場合、合成関係は、 および となるようなが存在する場合のみ、となるように定義されます。^{[注 1]この定義は、}関数合成の定義を一般化したものです。集合上の同値関係の定義特性は、次のように再定式化できます。 ${\displaystyle R\subseteq X\times Y}$${\displaystyle S\subseteq Y\times Z}$ ${\displaystyle SR\subseteq X\times Z}$${\displaystyle x\,SR\,z}$${\displaystyle y\in Y}$${\displaystyle x\,R\,y}$${\displaystyle y\,S\,z}$${\displaystyle R}$${\displaystyle X}$

• ${\displaystyle \operatorname {id} \subseteq R}$. (反射性)。(ここで、は上の恒等関数を表します。)${\displaystyle \operatorname {id} }$${\displaystyle X}$
• ${\displaystyle R=R^{-1}}$（対称性）。
• ${\displaystyle RR\subseteq R}$（推移性）^[3]

集合 上で、関係 は同値関係です。次の集合はこの関係の同値類です。 ${\displaystyle X=\{a,b,c\}}$${\displaystyle R=\{(a,a),(b,b),(c,c),(b,c),(c,b)\}}$$${\displaystyle [a]=\{a\},~~~~[b]=[c]=\{b,c\}.}$$

のすべての同値類の集合はです。この集合はに関する集合の分割です。 ${\displaystyle R}$${\displaystyle \{\{a\},\{b,c\}\}.}$${\displaystyle X}$${\displaystyle R}$

以下の関係はすべて同値関係です。

• 数値の集合において「等しい」。例えば、^[2]に等しい${\displaystyle {\tfrac {1}{2}}}$${\displaystyle {\tfrac {4}{8}}.}$
• 全ての人の集合において「誕生日が同じ」です。
• すべての三角形の集合上で「相似」です。
• すべての三角形の集合上で「合同である」 。
• 自然数 が与えられると、整数を法としては と合同である。^[2]${\displaystyle n}$ ${\displaystyle n}$
• 関数 が与えられると、の定義域の元上で「 はの下でと同じ像を持ちます」 。たとえば、とは の下で と同じ像を持ちます。${\displaystyle f:X\to Y}$${\displaystyle f}$${\displaystyle f}$ ${\displaystyle X}$${\displaystyle 0}$${\displaystyle \pi}$${\displaystyle \sin}$${\displaystyle 0}$
• 実数の集合上で「絶対値が同じ」
• すべての角度の集合上で「同じ余弦を持つ」。

• 実数間の関係「≥」は反射的かつ推移的ですが、対称的ではありません。たとえば、7 ≥ 5 ですが、5 ≥ 7 ではありません。
• 1 より大きい自然数間の「1 より大きい共通因数を持つ」という関係は、反射的かつ対称的ですが、推移的ではありません。たとえば、自然数 2 と 6 には 1 より大きい共通因数があり、6 と 3 には 1 より大きい共通因数がありますが、2 と 3 には 1 より大きい共通因数がありません。
• 集合X上の空の関係 R ( aRb が真にならないように定義される) は、空対称かつ推移的です。ただし、反射的ではありません ( X自体が空でない限り)。
• 実数間の「ほぼ等しい」という関係は、より正確に定義されたとしても、同値関係ではありません。なぜなら、反射的で対称的ではあっても、複数の小さな変化が蓄積されて大きな変化になる可能性があるため、推移的ではないからです。ただし、近似が漸近的に定義される場合、たとえば、ある点のf − gの極限がその点で 0 である場合、2 つの関数fとgはある点の近くでほぼ等しいと言うことで、同値関係を定義します。

• 半順序とは、反射的、反対称的、推移的な関係です。
• 等式は、同値関係であると同時に半順序でもあります。等式は、集合上で反射的、対称的、反対称的な関係である唯一の関係でもあります。代数式では、等しい変数は互いに置き換えることができますが、この機能は同値関係の変数では利用できません。同値関係の同値クラスは互いに置き換えることができますが、クラス内の個体を置き換えることはできません。
• 厳密な半順序は、非反射的、推移的、非対称的です。
• 部分同値関係は推移的かつ対称的である。このような関係は、それが全体的である場合、つまり、すべてに対して何らかのものが存在する場合にのみ反射的である^[証明1]。したがって、同値関係は、対称的、推移的、かつ全体の関係として定義することもできます。${\displaystyle a,}$${\displaystyle b{\text{ }}a\sim b となる。}$
• 三元同値関係は、通常の (二元) 同値関係の三元類似物です。
• 反射的かつ対称的な関係は、有限の場合は依存関係であり、無限の場合は許容関係です。
• 事前順序は反射的かつ推移的です。
• 合同関係は、その定義域が代数構造の基礎集合でもあり、追加の構造を尊重する同値関係です。一般に、合同関係は準同型の核の役割を果たし、構造を合同関係で割った商を形成できます。多くの重要なケースでは、合同関係は、それが定義されている構造のサブ構造として別の表現を持ちます (たとえば、群 上の合同関係は、正規サブグループに対応します)。${\displaystyle X}$
• 任意の同値関係は分離関係の否定ですが、その逆の命題は排中律と同値であるため、古典数学（構成的数学ではなく）でのみ成立します。
• 反射的かつ左（または右）ユークリッド関係である各関係は、同値関係でもあります。

が上の同値関係であり、がの要素の性質であって、が真であるときはいつでも、が真であるとき、その性質は明確に定義されている、または関係の下でクラス不変であるという。${\displaystyle \,\sim \,}$${\displaystyle X,}$${\displaystyle P(x)}$${\displaystyle X,}$${\displaystyle x\sim y,}$ ${\displaystyle P(x)}$${\displaystyle P(y)}$${\displaystyle P}$${\displaystyle \,\sim .}$

よくある特殊なケースとして、が から別の集合への関数である場合に、 がを意味するとき、はクラスの射であり、 に対して不変である、または単に に対して不変であると言われることがあります。 これは、例えば有限群のキャラクタ理論で発生します。 関数 を伴う後者のケースは、可換三角形で表現できます。不変も参照してください。著者によっては、「 に対して不変」という代わりに、「 と互換性がある」または単に「 を尊重」という表現を使用する人もいます。 ${\displaystyle f}$${\displaystyle X}$${\displaystyle Y;}$${\displaystyle x_{1}\sim x_{2}}$${\displaystyle f\left(x_{1}\right)=f\left(x_{2}\right)}$${\displaystyle f}$${\displaystyle \,\sim ,}$ ${\displaystyle \,\sim ,}$ ${\displaystyle \,\sim .}$${\displaystyle f}$${\displaystyle \,\sim }$${\displaystyle \,\sim }$${\displaystyle \,\sim }$

より一般的には、関数は（同値関係 の下で）同値な引数を（同値関係 の下で）同値な値に写像することができる。このような関数は、 からへの射として知られている。${\displaystyle \,\sim _{A}}$${\displaystyle \,\sim _{B}}$${\displaystyle \,\sim _{A}}$${\displaystyle \,\sim _{B}.}$

、およびを同値関係とします。いくつかの重要な定義と用語を以下に示します 。${\displaystyle a,b\in X}$${\displaystyle \sim }$

のすべてのおよびに対して成り立ち、 および の外部では決して成り立たないの部分集合をによるの同値類と呼びます。が属する同値類を で表します。の互いに同値な すべての要素は、同じ同値類の要素でもあります。${\displaystyle Y}$${\displaystyle X}$${\displaystyle a\sim b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle Y}$${\displaystyle a}$${\displaystyle Y}$${\displaystyle b}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle \sim }$${\displaystyle [a]:=\{x\in X:a\sim x\}}$${\displaystyle a}$${\displaystyle X}$

によって表されるのすべての同値類の集合は、による の商集合です。が位相空間である場合、を位相空間に変換する自然な方法があります。詳細については、 商空間を参照してください。${\displaystyle X}$${\displaystyle \sim ,}$${\displaystyle X/{\mathord {\sim }}:=\{[x]:x\in X\},}$${\displaystyle X}$${\displaystyle \sim .}$${\displaystyle X}$${\displaystyle X/\sim }$

の射影は、の要素をそれぞれの同値類に写像する関数で定義される。${\displaystyle \,\sim \,}$${\displaystyle \pi :X\to X/{\mathord {\sim }}}$${\displaystyle \pi (x)=[x]}$${\displaystyle X}$${\displaystyle \,\sim .}$

射影に関する定理: ^[4] 関数 がである場合に となるようなものとし、 となる唯一の関数 が存在する。が全射でありが全単射である場合にが全単射である。${\displaystyle f:X\to B}$${\displaystyle a\sim b}$${\displaystyle f(a)=f(b).}$${\displaystyle g:X/\sim \to B}$${\displaystyle f=g\pi .}$${\displaystyle f}$${\displaystyle a\sim b{\text{ if and only if }}f(a)=f(b),}$${\displaystyle g}$

関数の同値核は、次のように定義される同値関係 ~ です。 注入の同値核は恒等関係です。${\displaystyle f}$${\displaystyle x\sim y{\text{ if and only if }}f(x)=f(y).}$

Xの分割は、 Xの空でない部分集合の集合Pであり、Xのすべての要素はPの単一の要素の要素です。Pの各要素は分割のセルです。さらに、 Pの要素はペアごとに互いに素であり、それらの和集合はXです。

X をn個の要素を持つ有限集合とします。X上のすべての同値関係はXの分割に対応し、その逆も同様であるため、X上の同値関係の数はXの異なる分割の数に等しく、これはn番目のベル数 B _nです。

$${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}\quad }$$（ドビンスキーの公式）。

重要な結果は、同値関係とパーティションを結び付けている：^{[5] [6] [7]}

• 集合X上の同値関係 ~ はX を分割します。
• 逆に、 Xの任意の分割に対応して、 X上に同値関係 ~ が存在する。

どちらの場合も、 Xの分割のセルは、 ~ によるXの同値類です。Xの各要素はXの任意の分割の一意のセルに属し、分割の各セルは~ によるXの同値類と同一であるため、Xの各要素は ~ によるXの一意の同値類に属します。したがって、 X上のすべての同値関係の集合とXのすべての分割の集合の間には自然な一対一関係が存在します。

と が同じ集合 上の2つの同値関係であり、 がすべての に対してを意味する場合、 はよりも粗い関係であり、 はよりも細かい関係であると言われます。同様に、 ${\displaystyle \sim }$${\displaystyle \approx }$${\displaystyle S}$${\displaystyle a\sim b}$${\displaystyle a\approx b}$${\displaystyle a,b\in S,}$${\displaystyle \approx }$${\displaystyle \sim }$${\displaystyle \sim }$${\displaystyle \approx }$

• ${\displaystyle \sim }$は、 のすべての同値クラスがの同値クラスの部分集合であり、したがって のすべての同値クラスがの同値クラスの和集合である場合よりも細かくなります。${\displaystyle \approx }$${\displaystyle \sim }$${\displaystyle \approx }$${\displaystyle \approx }$${\displaystyle \sim }$
• ${\displaystyle \sim }$は、 によって作成されたパーティションが によって作成されたパーティションの改良である場合よりも細かくなります。${\displaystyle \approx }$${\displaystyle \sim }$${\displaystyle \approx }$

等式同値関係は、任意の集合上で最も細かい同値関係ですが、すべての要素のペアを関連付ける普遍関係は最も粗い同値関係です。

固定された集合上のすべての同値関係の集合に対する関係「は より細かい」は、それ自体が半順序関係であり、その集合を幾何格子にする。^[8]${\displaystyle \sim }$${\displaystyle \approx }$

• 任意の集合が与えられた場合、すべての関数の集合に対する同値関係は次のようにして得ることができる。2 つの関数は、それぞれの不動点の集合が同じ濃度 （順列 の長さ 1 のサイクルに対応）を持つときに同等であるとみなされる。${\displaystyle X,}$${\displaystyle [X\to X]}$${\displaystyle X\to X}$
• 上の同値関係は、その全射影の同値核である^[9]逆に、集合間の全射は、その定義域上の分割、すなわち余定義域内のシングルトンの原像の集合を決定する。したがって、の分割上の同値関係と が定義域である射影は、同じものを指定する 3 つの同値な方法である。${\displaystyle \,\sim \,}$${\displaystyle X}$${\displaystyle \pi :X\to X/\sim .}$${\displaystyle X,}$${\displaystyle X,}$${\displaystyle X,}$
• X上の同値関係の集合（のサブセットとして見た二項関係）の交差も同値関係である。これにより、同値関係を生成する便利な方法が得られる。X上の任意の二項関係Rが与えられた場合、 R によって生成される同値関係は、Rを含むすべての同値関係の交差（ Rを含む最小の同値関係とも呼ばれる）である。具体的には、R は同値関係を生成する。${\displaystyle X\times X}$

${\displaystyle a\sim b}$自然数 と元が存在して、、、または、${\displaystyle n}$${\displaystyle x_{0},\ldots ,x_{n}\in X}$${\displaystyle a=x_{0}}$${\displaystyle b=x_{n}}$${\displaystyle x_{i-1}\mathrel {R} x_{i}}$${\displaystyle x_{i}\mathrel {R} x_{i-1}}$${\displaystyle i=1,\ldots ,n.}$

この方法で生成される同値関係は自明なものです。たとえば、X上の任意の全順序によって生成される同値関係には、 X自体という1 つの同値クラスが正確に存在します。

• 同値関係は、「ものを接着する」ことによって新しい空間を構築できます。Xを単位直交座標 とし、~ をすべての に対して、すべての に対してによって定義されるX上の同値関係とします。すると、商空間は自然にトーラスと同一視 (同相)できます。正方形の紙を用意し、上端と下端を曲げて接着し、円筒を形成します。次に、できた円筒を曲げて 2 つの開いた端を接着すると、トーラスになります。${\displaystyle [0,1]\times [0,1],}$${\displaystyle (a,0)\sim (a,1)}$${\displaystyle a\in [0,1]}$${\displaystyle (0,b)\sim (1,b)}$${\displaystyle b\in [0,1],}$ ${\displaystyle X/\sim }$

数学の多くは、同値関係と順序関係の研究に基づいています。格子理論は、順序関係の数学的構造を捉えます。同値関係は順序関係と同様に数学において遍在しますが、同値の代数的構造は順序ほどよく知られていません。前者の構造は主に群論に基づいており、程度は低いものの、格子、カテゴリ、および類群の理論に基づいています。

順序関係が順序集合、つまり対の上限と下限に関して閉じた集合に基づいているのと同様に、同値関係は分割集合、つまり分割構造を保存する全単射に関して閉じた集合に基づいている。このような全単射は同値類をそれ自体に写像するため、このような全単射は順列とも呼ばれる。したがって、順列群（変換群とも呼ばれる）と関連する軌道の概念は、同値関係の数学的構造を明らかにする。

'~' は、ある空でない集合A （宇宙または基礎集合と呼ばれる）上の同値関係を表すものとする。Gは、 Aの分割構造を保存するA上の全単射関数の集合を表すものとし、これはすべてのおよびに対して成り立つことを意味する。すると、次の3つの関連する定理が成り立つ：^[10]${\displaystyle x\in A}$${\displaystyle g\in G,g(x)\in [x].}$

• ~ A を同値類に分割します。(これは前述の同値関係の基本定理です)。
• Aの分割が与えられたとき、Gは合成による変換群であり、その軌道は分割のセルである。 ^[14]
• A上の変換群Gが与えられたとき、 A上の同値関係 ~ が存在し、その同値類はGの軌道である。^{[15] [16]}

つまり、A上の同値関係 ~ が与えられた場合、その軌道が ~ の下でのAの同値類であるA上の変換群 G が存在する。

この変換群による同値関係の特徴付けは、格子が順序関係を特徴付ける方法とは根本的に異なります。格子理論演算のmeetとjoinの引数は、何らかの宇宙Aの要素です。一方、変換群演算のcompilationとinverse の引数は、一組の単射A → Aの要素です。

一般の群に移って、H をある群Gの部分群とします。 ~ をG上の同値関係とし、 ~ の同値類 ( HのGへの作用の軌道とも呼ばれます)は、 GにおけるHの右剰余類です。aとb を交換すると、左剰余類が生成されます。 ${\displaystyle a\sim b{\text{ if and only if }}ab^{-1}\in H.}$

関連する考え方は、Rosen (2008: chpt. 10) に記載されています。

G を集合とし、"~" をG上の同値関係を表すものとする。すると、この同値関係を表す群を次のように形成することができる。オブジェクトはGの要素であり、 Gの任意の2つの要素xとyに対して、 xからyへの唯一の射が存在するのは、次の場合のみである。 ${\displaystyle x\sim y.}$

同値関係を群の特殊なケースとみなすことの利点は次のとおりです。

• 「自由同値関係」という概念は存在しないが、有向グラフ上の自由群の概念は存在する。したがって、「同値関係の表現」、すなわち対応する群の表現について話すことは意味がある。
• 群の束、群作用、集合、同値関係は、群の概念の特殊なケースと見なすことができ、この観点は多くの類似性を示唆する。
• 多くの文脈において「商」、したがって合同と呼ばれる適切な同値関係が重要である。これは、カテゴリの内部群の概念につながる。^[17]

任意の集合X上の同値関係は、集合の包含関係によって順序付けられると、慣例によりCon Xと呼ばれる完全な束を形成します。標準写像ker  : X ^ X → Con Xは、X上のすべての関数のモノイドX ^ XとCon Xを関連付けます。kerは射影的ですが、単射ではありません。より形式的には、 X上の同値関係ker は、各関数f  : X → Xをその核ker fにとります。同様に、ker(ker) はX ^ X上の同値関係です。

同値関係は、例や反例の簡単なソースです。たとえば、ちょうど 2 つの無限同値類を持つ同値関係は、ω-カテゴリカルであるが、それより大きい基数に対してはカテゴリカルではない理論の簡単な例です。

モデル理論の含意は、関係を定義する特性が、各特性について、他のすべての特性を満たしながらも特定の特性を満たさない関係の例が見つかる場合にのみ、互いに独立して（したがって定義の必要な部分から）証明できるということです。したがって、同値関係の 3 つの定義特性は、次の 3 つの例によって相互に独立して証明できます。

• 反射的かつ推移的: N上の関係 ≤ 。または任意の前順序。
• 対称的かつ推移的: N上の関係R は、aRb ↔ ab ≠ 0 として定義されます。または任意の部分同値関係。
• 反射的かつ対称的: Z上の関係R は、aRb ↔「a − b は、2 または 3 の少なくとも 1 つで割り切れる」と定義されます。または、任意の依存関係。

同値関係が持つ可能性のある、 第一階述語論理で定義可能なプロパティには次のものがあります。

• 同値類の数は有限または無限です。
• 同値類の数は（有限の）自然数nに等しい。
• すべての同値類は無限の濃度を持ちます。
• 各同値類の要素数は自然数nです。

• ボレル同値関係
• クラスターグラフ – 完全グラフの非結合和集合から作られたグラフ
• 共役類 – 群論において、共役関係における同値類
• 等角性（幾何学）  – 長さと方向が同じ線分の性質
• 超有限同値関係
• 同値関係による商 – 同値類のスキーム理論への一般化
• 位相共役性 – 位相幾何学における概念
• まで – 同等の構造（同値関係）を除く、一意性の数学的記述

• ブラウン、ロナルド、2006年。「トポロジーと群体」 Booksurge LLC。ISBN 1-4196-2722-8。 
• Castellani, E., 2003、「対称性と等価性」、Brading, Katherine、および E. Castellani 編、『物理学における対称性: 哲学的考察』、ケンブリッジ大学出版局、422–433 ページ。
• Robert Dilworthおよび Crawley, Peter、1973 年。格子の代数理論。Prentice Hall。第 12 章では、格子理論で同値関係がどのように生じるかについて説明します。
• Higgins, PJ, 1971.カテゴリと群体。Van Nostrand。2005 年から TAC 再版としてダウンロード可能。
• ジョン・ランドルフ・ルーカス、1973年。『時間と空間に関する論文』ロンドン：メシューエン。第31章。
• Rosen, Joseph (2008)対称性のルール: 科学と自然は対称性に基づいている。Springer-Verlag。主に章。9、10。
• レイモンド・ワイルダー(1965) 『数学基礎入門』第2版、第2-8章:同値性を定義する公理、pp 48-50、John Wiley & Sons。

• 「同値関係」、数学百科事典、EMS Press、2001 [1994]
• Bogomolny, A.、「同等関係」cut-the-knot。2009年 9 月 1 日にアクセス
• PlanetMath における同値関係
• OEISシーケンス A231428 (同値関係を表すバイナリ マトリックス)