同値関係のソースを表示

{{about|二項関係|命題|同値}}
{{出典の明記|date=2016-12}}
[[数学]]において、'''同値関係'''（どうちかんけい、{{lang-en-short|''equivalence relation''}}）とは[[二項関係]]であって[[反射関係|反射的]]、[[対称関係|対称的]]、[[推移的関係|推移的]]の3つの性質を満たすものをいう。そのことから、与えられた集合上の1つの同値関係はその集合を[[同値類]]に[[集合の分割|分割]]（類別）することが導かれる。

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

== 定義 ==
ある[[集合]] {{mvar|S}} において、以下の3つの性質をすべて満たす[[二項関係]] <math>\sim</math> は {{mvar|S}} 上の'''同値関係'''であるという。それらの性質とは {{mvar|S}} の任意の元 {{math2|''a'', ''b'', ''c''}} に対して、
* [[反射関係|反射律]]：<math>a \sim a</math>.
* [[対称関係|対称律]]：<math>a \sim b</math> ならば <math>b \sim a</math>.
* [[推移関係|推移律]]：<math>a \sim b</math> かつ <math>b \sim c</math> ならば <math>a \sim c</math>.
上の3つをまとめて'''同値律'''ということがよくある{{sfn|松坂|1968|p=54}}。<math>\sim</math> が同値関係であるときに、<math>a \sim b</math> であることを、{{mvar|a}} と {{mvar|b}} は'''同値'''であるという{{sfn|松坂|1968|p=54}}。

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

以下のものは一般には、[[クラス (集合論)|類]]における "関係" となる。
* 集合の[[濃度 (数学)|濃度]]の対等 "関係"：集合の中身は別として、集合の大きさとしては同じである。
* [[命題]]が[[同値]]であるという "関係"：2つの命題において、真偽（[[真理値]]）が同じである、または互いに片方から他方を証明できる。

== 諸概念 ==
=== 同値類 ===
{{main|同値類}}
集合 {{mvar|S}} の上に同値関係 {{math|&sim;}} が定義されているときには、{{mvar|S}} の各元 {{mvar|a}} に対して {{mvar|a}} に同値である元を全て集めた集合を考えることができる。この {{mvar|S}} の部分集合を、{{mvar|a}} を'''代表'''{{sfn|松坂|1968|p=57}}あるいは'''代表元''' ({{en|representative}}) とする'''[[同値類]]''' ({{en|equivalence class}}) または単に {{mvar|a}} の（属する）類{{sfn|松坂|1968|p=57}}と呼び、普通 {{math2|[''a''], {{overline|''a''}}, ''C''(''a'')}}{{sfn|松坂|1968|p=56}} などと書く：
:<math>[a] := \{ x \in S \mid a \sim x\}.</math>
また、1つの同値類 {{mvar|X}} に対して、{{math2|1=[''x''] = ''X''}} となる {{mvar|S}} の元 {{mvar|x}} を1つ定めることを、{{mvar|X}} の代表元として {{mvar|x}} をとるという。1つの同値類は、それに含まれている元を任意に選んでそれを代表元とする同値類を作ってもそれはもとと同じ同値類になる（同値類は代表元の取替えによって不変である）：
:<math>X = [x],\ y \in X \iff y \in [x] \iff x \sim y \iff x \in [y] \iff [y] = X,\, x \in X.</math>
ゆえに同値類に関する性質を代表元の性質のみによって記述することは、一般には適当ではない。{{mvar|X}} 上の同値関係 {{math|~}} が与えられたとき、{{mvar|X}} の元に関する性質 {{mvar|P}} が {{math2|''x'' ~ ''y''}} なるとき常に {{math|''P''(''x'')}} ならば {{math|''P''(''y'')}} を満たすならば、性質 {{mvar|P}} は同値関係 {{math|~}} の下で [[well-defined]] であるとか、各同値類上で不変 (''class invariant''; 類不変) であるなどという。

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

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

=== 商集合 ===
集合 {{mvar|S}} の同値関係 <math>\sim</math> から定まる同値類すべてを集めた集合のことを、集合 {{mvar|S}} を'''同値関係''' <math>\sim</math> '''で割った集合'''、あるいは {{mvar|S}} の <math>\sim</math> による'''[[商集合]]'''であるといい、
:<math>S/{\sim} := \{[x] \mid x \in S\}</math>
と表す。集合 {{mvar|S}} の元に対してそれが属する同値類を対応させることにより、{{mvar|S}}から商集合への自然な[[全射]]
:<math>\pi\colon S \twoheadrightarrow S/{\sim};\ x \mapsto [x]</math>
が与えられる。これを同値関係 <math>\sim</math> に付随する'''[[商写像]]'''や'''標準射影'''という。
; 定理 (標準射影の普遍性)<ref>[[Garrett Birkhoff]] and [[Saunders Mac Lane]], 1999 (1967). ''Algebra'', 3rd ed. p.35, Th.19. Chelsea.</ref>
: 写像 {{math2|''f'': ''X'' → ''B''}} が {{math2|''a'' ~ ''b''}} ならば {{math2|1=''f''(''a'') = ''f''(''b'')}} を満たすならば、商集合からの写像 {{math2|''g'': ''X''/~ → ''B''}} で <math>f=g\circ\pi</math>（{{mvar|π}} は標準射影）を満たすものが一意に存在する。さらに、{{mvar|f}} が[[全射]]かつ {{math2|1=''a'' ~ ''b'' ⇔ ''f''(''a'') = ''f''(''b'')}} を満たすとき、{{mvar|g}} は[[全単射]]となる。

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

=== 類別 ===
{{main|集合の分割}}
集合 {{mvar|S}} に対して、{{mvar|S}} の空集合を含まない[[部分集合]][[族 (数学)|族]] {{mathbf|M}} であって、{{mathbf|M}} に属するどの2つの相異なる集合は[[共通部分|交わり]]を[[素集合|持たず]]、{{mathbf|M}} の[[合併 (集合論)|和集合]]が {{mvar|S}} 全体に一致するときに、集合族 {{mathbf|M}} のことを集合 {{mvar|S}} の'''類別'''または'''分類''' ({{en|classification}}){{sfn|松坂|1968|p=57}} あるいは'''[[集合の分割|分割]]''' (partition) であるという。
; 定理 (同値関係と類別の関係)
:* 集合 {{mvar|X}} 上の同値関係 {{math|~}} は {{mvar|X}} を類別する。
:* {{mvar|X}} の任意の類別に対して {{mvar|X}} 上の同値関係 {{math|~}} が一意的に対応する。
これが同値関係と類別の間の基本的な結果である<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. p. 31, Th. 8. Springer-Verlag.</ref><ref>Dummit, D. S., and Foote, R. M., 2004. ''Abstract Algebra'', 3rd ed. p. 3, Prop. 2. John Wiley & Sons.</ref><ref>[[Karel Hrbacek]] & [[Thomas Jech]] (1999) ''Introduction to Set Theory'', 3rd edition, pages 29–32, [[Marcel Dekker]]</ref>。
いずれの主張も、{{mvar|X}} の分割のセル全体のなす集合が {{mvar|X}} の {{math|~}} に関する同値類全体のなす集合に一致する。{{mvar|X}} の各元 {{mvar|x}} は {{mvar|X}} の分割のセルのうちただ1つのみに属するのであるから（かつ、各セルは同値類と同一視できるのだから）、各元 {{mvar|x}} は {{mvar|X}} の同値類のうちただ1つのみに属する。従って、{{mvar|X}} 上で可能な同値関係全体のなす集合と {{mvar|X}} の分割全体のなす集合との間には自然な[[全単射]]が存在することがわかる。

=== 同値核 ===
{{See also|核 (代数学)|{{仮リンク|核 (集合論)|en|Kernel (set theory)}}}}
写像 {{mvar|f}} の'''同値核''' (''equivalence kernel'') あるいは {{mvar|f}} に'''付随する同値関係'''{{sfn|松坂|1968|p=55}}とは、
: <math>x\sim y \iff f(x) = f(y)</math>
で定義される関係 {{math|~}} を言う。

=== 同値関係の比較 ===
{{seealso|集合の分割#分割の細分}}
集合 {{mvar|S}} 上の2つの同値関係 {{math|~, ≈}} が {{math2|''a'' ~ ''b''}} ならば {{math2|''a'' ≈ ''b''}} を任意の {{math2|''a'', ''b'' ∈ ''S''}} に対して満たすとき、同値関係 {{math|≈}} は {{math|~}} より'''粗い''' (''coarser'') または弱いといい、{{math|~}} は {{math|≈}} より'''細かい''' (''finer'') または強いという。

[[同値類]]の言葉で言えば
* {{math|~}} が {{math|≈}} より細かい（強い）とは、{{math|~}} に関する任意の同値類が {{math|≈}} に関する適当な同値類の部分集合となるときにいう。
それゆえ、{{math|≈}} に関する任意の同値類は {{math|~}} に関する同値類の合併になる。すなわち
* {{math|~}} が {{math|≈}} より細かい（強い）とは、{{math|~}} の定める[[集合の分割|分割]]が {{math|≈}} の定める分割の[[集合の分割#分割の細分|細分]]となるときに言う。
とも言い換えられる。

[[等式|相等関係]]は任意の集合上で最も強い同値関係であり、[[自明な関係]]<ref>ProofWiki: [https://proofwiki.org/wiki/Definition:Trivial_Relation Trivial_Relation], [https://proofwiki.org/wiki/Trivial_Relation_is_Equivalence Trivial_Relation_is_Equivalence]</ref>は最も弱い同値関係であり、任意の2つの元は互いに同値になる。

集合 {{mvar|S}} を固定して考えるとき、その上の同値関係全体の成す集合上で、"{{math|~}} は {{math|≈}} より細かい" という関係はそれ自身[[半順序関係|半順序]]を成し、それにより {{mvar|S}} 上の同値関係の全体は{{仮リンク|幾何束|en|geometric lattice}}をなす<ref>{{Citation |title=Lattice Theory |volume=25 |series=Colloquium Publications |publisher=American Mathematical Society |first=Garrett |last=Birkhoff |authorlink=Garrett Birkhoff |edition=3rd |year=1995 |isbn=9780821810255}}. Sect. IV.9, Theorem 12, page 95</ref>。

== 商集合の例 ==
{{See also|合同関係}}
整数全体のなす集合 {{mathbf|Z}} に、{{mvar|a}} と {{mvar|b}} の差 {{math2|''a'' &minus; ''b''}} が {{math|3}} の[[倍数]]であるときまたそのときに限って {{math2|''a'' ≡ ''b''}} という[[整数の合同|関係 {{math|≡}}]] を決めると、これは同値関係になる。

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

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

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

== 他の2項関係との関係 ==
* [[半順序]]は[[反射関係|反射的]]・{{underline|[[反対称関係|'''反'''対称的]]}}かつ[[推移的関係|推移的]]な二項関係をいう。
* [[相等関係]]は半順序かつ同値関係となるような関係である。また、相等関係は反射的・対称的かつ反対称的な唯一の関係である。
* 狭義半順序は、非反射的・推移的かつ[[非対称関係|非対称的]]をいう。
* {{仮リンク|半同値関係|en|partial equivalence relation}}は推移的かつ対称的である。推移性と対称性から反射性が出るための[[必要十分条件]]は、各元 {{math2|''a ''∈ ''X''}} に対して適当な {{math2|''b ''∈ ''X''}} をとれば {{math2|''a ''~ ''b''}} とできることである。
* 反射的かつ対称的な関係は、それが有限なとき{{仮リンク|従属関係|en|dependency relation}}といい、無限なとき{{仮リンク|容認関係|en|tolerance relation}}という。
* {{仮リンク|前順序|en|preorder}} は反射的かつ推移的な関係をいう。
* [[合同関係]]は適当な[[代数系]]の台集合上で定義される同値関係で、付随する代数構造と両立するようなものをいう。一般に、合同関係は準同型の[[核 (代数学)|核]]と同じ役割を果たすもので、それによる商集合に商代数系の構造を入れることができる。多くの重要な場合において合同関係は考えている構造の部分構造として実現することができる（例えば、群の合同関係は[[正規部分群]]に対応する）。

=== ユークリッド関係 ===
[[ユークリッド]]の著『[[ユークリッド原論|原論]]』には
; 公理 1
: 同じものに等しいもの同士は互いに等しい
という公理がある。今日において、上の公理の「等しい」という部分をすべて「関係する」と書き換えた性質を満足する関係は{{仮リンク|ユークリッド関係|en|Euclidean relation|label=ユークリッド的}}であると言われる。[[二項関係]] {{mvar|R}} に関して一般には {{mvar|{{gaps|a|R|b}}}} は {{mvar|{{gaps|b|R|a}}}} と相異なるから、ユークリッド関係も
* 左ユークリッド関係：({{mvar|{{gaps|a|R|c}}}} かつ {{mvar|{{gaps|b|R|c}}}}) ならば {{mvar|{{gaps|a|R|b}}}}
* 右ユークリッド関係：({{mvar|{{gaps|c|R|a}}}} かつ {{mvar|{{gaps|c|R|b}}}}) ならば {{mvar|{{gaps|a|R|b}}}}
の二種類が考えられる。ユークリッド関係と同値関係との関係は以下のように述べることができる:
; 定理
: 与えられた左（または右）ユークリッド関係が反射的ならば、その関係は対称的かつ推移的となる。
証明は以下のようにすればよい。
* 左ユークリッド関係の性質 [({{mvar|{{gaps|a|R|c}}}} かつ {{mvar|{{gaps|b|R|c}}}}) ならば {{mvar|{{gaps|a|R|b}}}}] において {{math2|1=''a'' = ''c''}} ととれば、[({{mvar|{{gaps|a|R|a}}}} かつ {{mvar|{{gaps|b|R|a}}}}) ならば {{mvar|{{gaps|a|R|b}}}}] を得る。いま仮定により {{mvar|R}} は反射的だから恒真となる {{mvar|{{gaps|a|R|a}}}} を除去すれば対称性 [{{mvar|{{gaps|b|R|a}}}} ならば {{mvar|{{gaps|a|R|b}}}}] を得る。
* 対称性が示されたから、左ユークリッド関係の性質 [({{mvar|{{gaps|a|R|c}}}} かつ {{mvar|{{gaps|b|R|c}}}}) ならば {{mvar|{{gaps|a|R|b}}}}] において {{mvar|{{gaps|b|R|c}}}} を {{mvar|{{gaps|c|R|b}}}} で置き換えて推移性 [({{mvar|{{gaps|a|R|c}}}} かつ {{mvar|{{gaps|c|R|b}}}}) ならば {{mvar|{{gaps|a|R|b}}}}] を得る。
右ユークリッド関係についても同様。ゆえに、同値関係は反射的かつユークリッド的な二項関係として特徴づけられる。

== 一般化 ==
{{main|余等化子}}
同値関係を[[圏論]]的に一般化した概念に[[余等化子]]がある。[[圏 (数学)|圏]] {{mathbf|C}} の[[射]] {{math2|''f'', ''g'': ''X'' → ''Y''}} の'''余等化子'''とは[[対象 (圏論)|対象]] {{mvar|Q}} と射 {{math2|''q'': ''Y'' → ''Q''}} の組であって、{{math2|1=''qf'' = ''qg''}} を満たし、以下の[[普遍性]]を持つものである：対象 {{mvar|Q{{'}}}} と射 {{math2|''q{{'}}'': ''Y'' → ''Q{{'}}''}} の組があって、{{math2|1=''q{{'}}f'' = ''q{{'}}g''}} を満たすならば、次の図式を[[可換図式|可換]]にする射 {{math2|''u'': ''Q'' → ''Q{{'}}''}} がただ1つ存在する<ref>{{Cite book |last=Awodey |first=Steve |year=2006 |title=Category theory |url={{google books|IK_sIDI2TCwC|Category theory|plainurl=yes}} |publisher=Oxford University Press |isbn=0-19-856861-4 |ref=harv |zbl=1100.18001 |quote={{google books quote|id=zLs8BAAAQBAJ|page=66|Definition 3.18}}}}</ref>。
[[画像:Свойство коуравнителя.png|center|]]
集合 {{mvar|S}} 上に同値関係 {{math|&sim;}} が与えられたとする。{{math2|1=''R'' = {{mset|(''x'', ''y'') &isin; ''S'' × ''S'' | ''x'' &sim; ''y''}}}} とおき、写像 {{math2|''r''{{sub|1}}, ''r''{{sub|2}}: ''R'' → ''S''}} を {{math2|1=''r''{{sub|1}}(''x'', ''y'') = ''x''}}, {{math2|1=''r''{{sub|2}}(''x'', ''y'') = ''y''}} で定義すると、商集合 {{math|''S''/&sim;}} と標準射影 {{math2|''π'': ''S'' → ''S''/&sim;}} の組は[[集合の圏]]における {{math|''r''{{sub|1}}}} と {{math|''r''{{sub|2}}}} の余等化子である。

== 出典 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{Citation|和書 |author=松坂和夫 |title=集合・位相入門 |publisher=岩波書店 |year=1968}}

== 関連項目 ==
* [[違いを除いて]]

== 外部リンク ==
* {{高校数学の美しい物語|1314|同値関係といろいろな例}}
* {{SpringerEOM |title=Equivalence relation |urlname=Equivalence_relation}}
* {{MathWorld |title=Equivalence Relation |urlname=EquivalenceRelation}}
* {{PlanetMath |title=equivalence relation |urlname=equivalencerelation}}

{{Normdaten}}

{{DEFAULTSORT:とうちかんけい}}
[[Category:同値 (数学)]]
[[Category:反射関係]]
[[Category:対称関係]]
[[Category:推移関係]]
[[Category:数学的関係]]
[[Category:数学に関する記事]]