同値関係

数学において、同値関係（どうちかんけい、英: equivalence relation）とは二項関係であって反射的、対称的、推移的の3つの性質を満たすものをいう。そのことから、与えられた集合上の1つの同値関係はその集合を同値類に分割（類別）することが導かれる。

同値関係にあることを表すのに用いられる記法は文献によってさまざまであるが、与えられた集合上の同値関係 $R$ に関して2つの元 $a, b$ が同値であることを " $a ~ b$ " や " $a \equiv b$ " で表すことが最もよく用いられる。 $R$ に関して同値であることを明示する場合には、" $a ~ R b$ " や " $a \equiv R b$ " あるいは " $a R b$ " などと書かれる。

定義

ある集合 $S$ において、以下の3つの性質をすべて満たす二項関係 $\sim$ は $S$ 上の同値関係であるという。それらの性質とは $S$ の任意の元 $a, b, c$ に対して、

反射律： $a\sim a$ .
対称律： $a\sim b$ ならば $b\sim a$ .
推移律： $a\sim b$ かつ $b\sim c$ ならば $a\sim c$ .

上の3つをまとめて同値律ということがよくある^[1]。 $\sim$ が同値関係であるときに、 $a\sim b$ であることを、 $a$ と $b$ は同値であるという^[1]。

同値関係の例

相等関係 ( $=$ )：集合としてあるいは集合の元として同じである。表現形式や構成要素が同一である。
図形の合同関係：位置や裏表や向きの違いを無視して、図形として同じである。
図形の相似関係：裏表・向き・大きさの比率の違いを無視して、図形の "形" としては同じである。
直線の平行関係：アフィン平面内の直線が交わらないか、一致する（傾きが同じである）。
量の比例関係：増え方・減り方の割合としては同じである。
整数の合同関係：ある数で割った余りが同じである。

以下のものは一般には、類における "関係" となる。

集合の濃度の対等 "関係"：集合の中身は別として、集合の大きさとしては同じである。
命題が同値であるという "関係"：2つの命題において、真偽（真理値）が同じである、または互いに片方から他方を証明できる。

諸概念

同値類

→詳細は「同値類」を参照

集合 $S$ の上に同値関係 $\sim$ が定義されているときには、 $S$ の各元 $a$ に対して $a$ に同値である元を全て集めた集合を考えることができる。この $S$ の部分集合を、 $a$ を代表^[2]あるいは代表元 (representative) とする同値類 (equivalence class) または単に $a$ の（属する）類^[2]と呼び、普通 $[a], a, C (a)$ ^[3] などと書く：

[a]:=\{x\in S\mid a\sim x\}.

また、1つの同値類 $X$ に対して、 $[x] = X$ となる $S$ の元 $x$ を1つ定めることを、 $X$ の代表元として $x$ をとるという。1つの同値類は、それに含まれている元を任意に選んでそれを代表元とする同値類を作ってもそれはもとと同じ同値類になる（同値類は代表元の取替えによって不変である）：

X=[x],\ y\in X\iff y\in [x]\iff x\sim y\iff x\in [y]\iff [y]=X,\,x\in X.

ゆえに同値類に関する性質を代表元の性質のみによって記述することは、一般には適当ではない。 $X$ 上の同値関係 $~$ が与えられたとき、 $X$ の元に関する性質 $P$ が $x ~ y$ なるとき常に $P (x)$ ならば $P (y)$ を満たすならば、性質 $P$ は同値関係 $~$ の下で well-defined であるとか、各同値類上で不変 (class invariant; 類不変) であるなどという。

そのようなものとしてよくあるのが、写像 $f : X \to Y$ で、 $x 1 ~ x 2$ ならば $f (x 1) = f (x 2)$ なるときである。この場合、 $f$ は各同値類上で定数 (class invariant under $~$ )、あるいは $~$ の下で不変 (invariant under $~$ ), より短く $~$ -不変などという。このようなものは例えば有限群の指標論などで見かけることができる。また、このような写像の性質を可換三角図式として書き表すことができる（不変量なども参照）。文献によっては、不変という代わりに、 $~$ に関する準同型 (morphism; 射) であるとか $~$ と両立する (compatible with $~$ ) とか適合する ("respects $~$ ") などのように言うこともある。

より一般に、（ある関係 $~ A$ に関して）同値なものを（別の関係 $~ B$ に関して）同値なものへ写す写像を考えることができて、そのような写像を $~ A$ から $~ B$ への準同型（あるいは射）などと呼ぶ。

商集合

集合 $S$ の同値関係 $\sim$ から定まる同値類すべてを集めた集合のことを、集合 $S$ を同値関係 $\sim$ で割った集合、あるいは $S$ の $\sim$ による商集合であるといい、

S/{\sim }:=\{[x]\mid x\in S\}

と表す。集合 $S$ の元に対してそれが属する同値類を対応させることにより、 $S$ から商集合への自然な全射

\pi \colon S\twoheadrightarrow S/{\sim };\ x\mapsto [x]

が与えられる。これを同値関係 $\sim$ に付随する商写像や標準射影という。

定理 (標準射影の普遍性)^[4]: 写像 $f : X \to B$ が $a ~ b$ ならば $f (a) = f (b)$ を満たすならば、商集合からの写像 $g : X /~ \to B$ で $f=g\circ \pi$ （ $π$ は標準射影）を満たすものが一意に存在する。さらに、 $f$ が全射かつ $a ~ b \Leftrightarrow f (a) = f (b)$ を満たすとき、 $g$ は全単射となる。

また、 $S$ の相異なるすべての同値類から代表元を1つずつ集めて作った $S$ の部分集合のことを、集合 $S$ における同値関係 $\sim$ の（あるいは商集合 $S/\sim$ の）完全代表系 (complete system of representatives) と呼ぶ。つまり、集合 $S$ の部分集合 $A$ が同値関係 $\sim$ についての完全代表系であるとは、包含写像と標準射影の合成 $A\hookrightarrow S\twoheadrightarrow S/\sim ;a\mapsto [a]$ が全単射となることである。

類別

→詳細は「集合の分割」を参照

集合 $S$ に対して、 $S$ の空集合を含まない部分集合族 $M$ であって、 $M$ に属するどの2つの相異なる集合は交わりを持たず、 $M$ の和集合が $S$ 全体に一致するときに、集合族 $M$ のことを集合 $S$ の類別または分類 (classification)^[2] あるいは分割 (partition) であるという。

定理 (同値関係と類別の関係)

集合 $X$ 上の同値関係 $~$ は $X$ を類別する。
$X$ の任意の類別に対して $X$ 上の同値関係 $~$ が一意的に対応する。

これが同値関係と類別の間の基本的な結果である^[5]^[6]^[7]。いずれの主張も、 $X$ の分割のセル全体のなす集合が $X$ の $~$ に関する同値類全体のなす集合に一致する。 $X$ の各元 $x$ は $X$ の分割のセルのうちただ1つのみに属するのであるから（かつ、各セルは同値類と同一視できるのだから）、各元 $x$ は $X$ の同値類のうちただ1つのみに属する。従って、 $X$ 上で可能な同値関係全体のなす集合と $X$ の分割全体のなす集合との間には自然な全単射が存在することがわかる。

同値核

→「核 (代数学)」および「核 (集合論)（英語版）」も参照

写像 $f$ の同値核 (equivalence kernel) あるいは $f$ に付随する同値関係^[8]とは、

x\sim y\iff f(x)=f(y)

で定義される関係 $~$ を言う。

同値関係の比較

→「集合の分割 § 分割の細分」も参照

集合 $S$ 上の2つの同値関係 $~, \approx$ が $a ~ b$ ならば $a \approx b$ を任意の $a, b \in S$ に対して満たすとき、同値関係 $\approx$ は $~$ より粗い (coarser) または弱いといい、 $~$ は $\approx$ より細かい (finer) または強いという。

同値類の言葉で言えば

$~$ が $\approx$ より細かい（強い）とは、 $~$ に関する任意の同値類が $\approx$ に関する適当な同値類の部分集合となるときにいう。

それゆえ、 $\approx$ に関する任意の同値類は $~$ に関する同値類の合併になる。すなわち

$~$ が $\approx$ より細かい（強い）とは、 $~$ の定める分割が $\approx$ の定める分割の細分となるときに言う。

とも言い換えられる。

相等関係は任意の集合上で最も強い同値関係であり、自明な関係^[9]は最も弱い同値関係であり、任意の2つの元は互いに同値になる。

集合 $S$ を固定して考えるとき、その上の同値関係全体の成す集合上で、" $~$ は $\approx$ より細かい" という関係はそれ自身半順序を成し、それにより $S$ 上の同値関係の全体は幾何束（英語版）をなす^[10]。

商集合の例

→「合同関係」も参照

整数全体のなす集合 $Z$ に、 $a$ と $b$ の差 $a - b$ が $3$ の倍数であるときまたそのときに限って $a \equiv b$ という関係 $\equiv$ を決めると、これは同値関係になる。

この関係によって集合 $Z$ が3つの同値類（この場合、剰余類 とも呼ばれる）に分割される。それぞれの同値類は $3$ で割り切れるもの全体 $[0]$ 、 $1$ 余るもの全体 $[1]$ 、 $2$ 余るもの全体 $[2]$ に対応している。

この商集合は普通 $Z /3 Z$ と書かれて、自然に演算が定義できて、加法に関するアーベル群、さらに乗法をいれて可換環になる（剰余類環）。また $p$ が素数のとき $Z / p Z$ は体（有限体）になる。

同様の例として、商線型空間（商ベクトル空間）、剰余群（剰余類群、商群）、剰余環（商環）、商位相空間などはそれぞれ適当な同値関係による商集合（に適切な構造を付与したもの）として定義される。

他の2項関係との関係

半順序は反射的・反対称的かつ推移的な二項関係をいう。
相等関係は半順序かつ同値関係となるような関係である。また、相等関係は反射的・対称的かつ反対称的な唯一の関係である。
狭義半順序は、非反射的・推移的かつ非対称的をいう。
半同値関係（英語版）は推移的かつ対称的である。推移性と対称性から反射性が出るための必要十分条件は、各元 $a \in X$ に対して適当な $b \in X$ をとれば $a ~ b$ とできることである。
反射的かつ対称的な関係は、それが有限なとき従属関係（英語版）といい、無限なとき容認関係（英語版）という。
前順序は反射的かつ推移的な関係をいう。
合同関係は適当な代数系の台集合上で定義される同値関係で、付随する代数構造と両立するようなものをいう。一般に、合同関係は準同型の核と同じ役割を果たすもので、それによる商集合に商代数系の構造を入れることができる。多くの重要な場合において合同関係は考えている構造の部分構造として実現することができる（例えば、群の合同関係は正規部分群に対応する）。

ユークリッド関係

ユークリッドの著『原論』には

公理 1: 同じものに等しいもの同士は互いに等しい

という公理がある。今日において、上の公理の「等しい」という部分をすべて「関係する」と書き換えた性質を満足する関係はユークリッド的（英語版）であると言われる。二項関係 $R$ に関して一般には $a R b$ は $b R a$ と相異なるから、ユークリッド関係も

左ユークリッド関係：( $a R c$ かつ $b R c$ ) ならば $a R b$
右ユークリッド関係：( $c R a$ かつ $c R b$ ) ならば $a R b$

の二種類が考えられる。ユークリッド関係と同値関係との関係は以下のように述べることができる:

定理: 与えられた左（または右）ユークリッド関係が反射的ならば、その関係は対称的かつ推移的となる。

証明は以下のようにすればよい。

左ユークリッド関係の性質 [( $a R c$ かつ $b R c$ ) ならば $a R b$ ] において $a = c$ ととれば、[( $a R a$ かつ $b R a$ ) ならば $a R b$ ] を得る。いま仮定により $R$ は反射的だから恒真となる $a R a$ を除去すれば対称性 [ $b R a$ ならば $a R b$ ] を得る。
対称性が示されたから、左ユークリッド関係の性質 [( $a R c$ かつ $b R c$ ) ならば $a R b$ ] において $b R c$ を $c R b$ で置き換えて推移性 [( $a R c$ かつ $c R b$ ) ならば $a R b$ ] を得る。

右ユークリッド関係についても同様。ゆえに、同値関係は反射的かつユークリッド的な二項関係として特徴づけられる。

一般化

→詳細は「余等化子」を参照

同値関係を圏論的に一般化した概念に余等化子がある。圏 $C$ の射 $f, g : X \to Y$ の余等化子とは対象 $Q$ と射 $q : Y \to Q$ の組であって、 $qf = qg$ を満たし、以下の普遍性を持つものである：対象 $Q'$ と射 $q' : Y \to Q'$ の組があって、 $q' f = q' g$ を満たすならば、次の図式を可換にする射 $u : Q \to Q'$ がただ1つ存在する^[11]。

集合 $S$ 上に同値関係 $\sim$ が与えられたとする。 $R = {(x, y) \in S \times S | x \sim y}$ とおき、写像 $r 1, r 2 : R \to S$ を $r 1 (x, y) = x$ , $r 2 (x, y) = y$ で定義すると、商集合 $S /\sim$ と標準射影 $π : S \to S /\sim$ の組は集合の圏における $r 1$ と $r 2$ の余等化子である。

出典

[脚注の使い方]

^ ^a ^b 松坂 1968, p. 54.
^ ^a ^b ^c 松坂 1968, p. 57.
^ 松坂 1968, p. 56.
^ Garrett Birkhoff and Saunders Mac Lane, 1999 (1967). Algebra, 3rd ed. p.35, Th.19. Chelsea.
^ Wallace, D. A. R., 1998. Groups, Rings and Fields. p. 31, Th. 8. Springer-Verlag.
^ Dummit, D. S., and Foote, R. M., 2004. Abstract Algebra, 3rd ed. p. 3, Prop. 2. John Wiley & Sons.
^ Karel Hrbacek & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, pages 29–32, Marcel Dekker
^ 松坂 1968, p. 55.
^ ProofWiki: Trivial_Relation, Trivial_Relation_is_Equivalence
^ Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, 25 (3rd ed.), American Mathematical Society, ISBN 9780821810255 . Sect. IV.9, Theorem 12, page 95
^ Awodey, Steve (2006). Category theory. Oxford University Press. ISBN 0-19-856861-4. Zbl 1100.18001. "Definition 3.18"

参考文献

松坂和夫『集合・位相入門』岩波書店、1968年。

外部リンク

『同値関係といろいろな例』 - 高校数学の美しい物語
Hazewinkel, Michiel, ed. (2001), “Equivalence relation”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Weisstein, Eric W. "Equivalence Relation". mathworld.wolfram.com (英語).
equivalence relation - PlanetMath.（英語）

[FOOTNOTE松坂196854-1] 松坂 1968, p. 54.

[FOOTNOTE松坂196857-2] 松坂 1968, p. 57.

[FOOTNOTE松坂196856-3] 松坂 1968, p. 56.

[4] Garrett Birkhoff and Saunders Mac Lane, 1999 (1967). Algebra, 3rd ed. p.35, Th.19. Chelsea.

[5] Wallace, D. A. R., 1998. Groups, Rings and Fields. p. 31, Th. 8. Springer-Verlag.

[6] Dummit, D. S., and Foote, R. M., 2004. Abstract Algebra, 3rd ed. p. 3, Prop. 2. John Wiley & Sons.

[7] Karel Hrbacek & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, pages 29–32, Marcel Dekker

[FOOTNOTE松坂196855-8] 松坂 1968, p. 55.

[9] ProofWiki: Trivial_Relation, Trivial_Relation_is_Equivalence

[10] Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, 25 (3rd ed.), American Mathematical Society, ISBN 9780821810255 . Sect. IV.9, Theorem 12, page 95

[11] Awodey, Steve (2006). Category theory. Oxford University Press. ISBN 0-19-856861-4. Zbl 1100.18001. "Definition 3.18"

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

定義