合同関係

抽象代数学において、合同関係 (congruence relation)（あるいは単に合同 (congruence)）は（群、環、あるいはベクトル空間のような）代数的構造上の、その構造と協調的な同値関係である。すべての合同関係は対応する商（英語版）構造を持ち、その元はその関係の同値類（あるいは合同類 (congruence class)）である。 合同関係のプロトタイプの例は整数全体の集合上の n {\displaystyle n} を法とした合同である。与えられた正の整数 n {\displaystyle n} に対して、2 つの整数 a {\displaystyle a} と b {\displaystyle b} は次のようなとき n {\displaystyle n} を法として合同 (congruent modulo n {\displaystyle n} ) と呼ばれ、 a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} と書かれる。 a − b {\displaystyle a-b} が n {\displaystyle n} によって割り切れる（あるいは同じことだが a {\displaystyle a} と b {\displaystyle b} は n {\displaystyle n} で割られたときに同じ余りを持つ）。 例えば、 37 {\displaystyle 37} と 57 {\displaystyle 57} は 10 {\displaystyle 10} を法として合同である 37 ≡ 57 ( mod 10 ) {\displaystyle 37\equiv 57{\pmod {10}}} なぜならば 37 − 57 = − 20 {\displaystyle 37-57=-20} は 10 の倍数であるからだ、あるいは同じことだが、 37 {\displaystyle 37} と 57 {\displaystyle 57} はどちらも 10 {\displaystyle 10} で割ったときに 7 {\displaystyle 7} 余るからである。 （固定された n {\displaystyle n} に対して） n {\displaystyle n} を法とした合同は整数の加法と乗法両方と両立する。つまり、 a 1 ≡ a 2 ( mod n ) {\displaystyle a_{1}\equiv a_{2}{\pmod {n}}} 　　かつ　　 b 1 ≡ b 2 ( mod n ) {\displaystyle b_{1}\equiv b_{2}{\pmod {n}}} であれば a 1 + b 1 ≡ a 2 + b 2 ( mod n ) {\displaystyle a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {n}}} 　かつ　 a 1 b 1 ≡ a 2 b 2 ( mod n ) {\displaystyle a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}} である。合同類の対応する加法と乗法は合同算術として知られている。抽象代数学の観点からは、 n {\displaystyle n} を法とした合同は整数環上の合同関係であり、 n {\displaystyle n} を法とした算術は対応する商環で起こる。 合同の定義は考えている代数的構造のタイプに依存する。合同の定義は群、環、ベクトル空間、加群、半群、束などに対してできる。共通のテーマは合同は、演算が同値類に関して well-defined であるという意味で代数的構造と両立する代数的対象上の同値関係であるということである。 例えば、群はある公理を満たすただ1つの二項演算を伴った1つの集合からなる代数的対象である。 G {\displaystyle G} が演算 ∗ を持った群であれば、G 上の合同関係 (congruence relation) は G の元についての同値関係 ≡ であって g1 ≡ g2  かつ  h1 ≡ h2    ならば    g1 ∗ h1 ≡ g2 ∗ h2 をすべての g1, g2, h1, h2 ∈ G に対して満たすものである。群上の合同に対して、単位元を含む同値類はいつも正規部分群であり、他の同値類はこの部分群の剰余類である。また、これらの同値類は商群の元である。 代数的構造が 1 つよりも多くの演算を持つとき、合同関係は各演算と両立することを要求される。例えば、環は加法と乗法を両方持ち、環上の合同関係は、r1 ≡ r2 かつ s1 ≡ s2 であるときにはいつでも、 r1 + s1 ≡ r2 + s2    および    r1s1 ≡ r2s2 を満たさなければならない。環上の合同に対して、0 を含む同値類はいつも両側イデアルであり、同値類の集合上の 2 つの演算は対応する商環を定義する。 合同関係の一般の概念は普遍代数学、すべての代数的構造に共通するアイデアを研究する分野、の文脈において正式な定義を与えることができる。この設定において、合同関係は次を満たす代数的構造上の同値関係 ≡ である。すべての n-項演算 μ と、各 i に対して ai ≡ ai′ を満たすすべての元 a1,...,an,a1′,...,an′ に対して、 μ(a1, a2, ..., an) ≡ μ(a1′, a2′, ..., an′) ƒ: A → B が2つの代数的構造の間の準同型（例えば群の準同型やベクトル空間の間の線型写像）であれば、 a1 ≡ a2    if and only if    ƒ(a1) = ƒ(a2) によって定義される関係 ≡ は合同関係である。第一同型定理によって、ƒ による A の像は A のこの合同による商に同型な B の部分構造である。 特に群の場合には、合同関係は以下のように初等的な言葉で記述することができる： G が（単位元 e と演算 * をもった）群で ~ が G 上の二項関係であれば、~ は次が成り立つときにはいつでも合同である： G の任意の元 a が与えられると（英語版）、a ~ a （反射性 (reflexivity)）； G の任意の元 a と b が与えられると、a ~ b であれば b ~ a である（対称性 (symmetry)）； G の任意の元 a, b, c が与えられると、a ~ b かつ b ~ c であれば a ~ c である（推移性 (transitivity)）； G の任意の元 a, a' , b, b' が与えられると、a ~ a' かつ b ~ b' であれば、a * b ~ a' * b' である； G の任意の元 a と a' が与えられると、a ~ a' であれば、a−1 ~ a' −1 である（これは実は他の 4 つから証明できるので、真に冗長である）。 条件 1, 2, 3 は ~ が同値関係であると言っている。 合同 ~ は単位元に合同な G の元の集合 {a ∈ G : a ~ e} によって完全に決定される。そしてこの集合は正規部分群である。 具体的には、a ~ b であるのは b−1 * a ~ e であるとき、かつそのときに限る。 なので群の合同について話す代わりに、群の正規部分群の言葉で普通話す。実は、すべての合同は G のある正規部分群に一意的に対応する。 同様の手法は、合同関係の代わりに核の言葉で（環論であればイデアル、加群論であれば部分加群によって）述べることもできる。この手法が可能な最も一般の状況は（複数の項数 (arity) をもつ作用を許す一般的な意味で）オメガ-群である（核となるのはΩ-安定な正規部分群）。 しかしこれは例えばモノイドではできないので、合同関係の研究はモノイド論においてより中心的な役割を果たす。 アイデアは普遍代数において一般化される： 代数 A 上の合同関係は A 上の同値関係でもあり直積 A × A の部分代数でもあるような A × A の部分集合である。 準同型の核（英語版）はいつも合同である。実際、すべての合同は核として生じる。 A 上の与えられた合同 ~ に対して、同値類全体の集合 A/~ は自然な方法、商代数（英語版）で代数の構造が与えられる。 A のすべての元をその同値類に写す関数は準同型であり、この準同型の核は ~ である。 代数 A 上のすべての合同関係の束 Con(A) は代数的（英語版）である。  en:Table of congruences en:Linear congruence theorem en:Congruence lattice problem Horn and Johnson, Matrix Analysis, Cambridge University Press, 1985. ISBN 0-521-38632-2. (Section 4.5 discusses congruency of matrices.)