Congruence relation

In mathematics , more precisely in algebra , an equivalence relation on an algebraic structure is called a congruence relation if the fundamental operations of the algebraic structure are compatible with this equivalence relation .

Definitions

Congruence relation and quotient algebra

An equivalence relation on a set does not necessarily have anything to do with the structure that is defined on it. Particularly in algebra, however, such equivalence relations are of particular interest, their ( surjective ) quotient mapping ${\displaystyle A}$ ${\displaystyle \equiv }$

${\displaystyle \mathrm {q} _{\equiv }\colon \,A\twoheadrightarrow A/{\equiv },\,a\mapsto [a]_{\equiv },}$

is compatible with the algebraic structure or a homomorphism . Because then the structure induced by on the quotient set , the so-called factor or quotient algebra from to with operations , ${\displaystyle \mathbf {A} =(A,(f_{i})_{i\in I})}$ ${\displaystyle \mathrm {q} _{\equiv }}$ ${\displaystyle A/{\equiv }}$ ${\displaystyle \mathbf {A} /{\equiv }:=(A/{\equiv },(f_{i,\equiv })_{i\in I})}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \equiv }$ ${\displaystyle f_{i,\equiv }}$

${\displaystyle f_{i,\equiv }([a_{1}]_{\equiv },\dotsc ,[a_{n_{i}}]_{\equiv }):=[f_{i}(a_{1},\dotsc ,a_{n_{i}})]_{\equiv }}$for everyone and everyone , ${\displaystyle a_{1\!\;\!},\dotsc ,a_{n_{i}\!}\in A}$ ${\displaystyle i\in I}$

of the same kind as that of . ${\displaystyle A}$

Such an equivalence relation is called a congruence relation on and two elements congruent after if they are equivalent with respect to : ${\displaystyle \equiv }$ ${\displaystyle \mathbf {A} }$ ${\displaystyle a,b\in A}$ ${\displaystyle \equiv }$ ${\displaystyle \equiv }$

${\displaystyle a\equiv b\iff [a]_{\equiv }=[b]_{\equiv }}$.

The equivalence class of each is then called the congruence class . ${\displaystyle [a]_{\equiv }}$ ${\displaystyle a\in A}$

An equivalence relation on is precisely then a congruence on an algebraic structure , when all the fundamental operations , are compatible with , i. H. for all , with the following applies: ${\displaystyle \equiv }$ ${\displaystyle A}$ ${\displaystyle \mathbf {A} =(A,(f_{i})_{i\in I})}$ ${\displaystyle f_{i}}$ ${\displaystyle i\in I}$ ${\displaystyle \equiv }$ ${\displaystyle a_{1\!\;\!},\dotsc ,a_{n_{i}\!\;\!},b_{1},\dotsc ,b_{n_{i}\!}\in A}$ ${\displaystyle n_{i}\in \mathbb {N} }$ ${\displaystyle a_{1\!}\equiv b_{1},\dotsc ,a_{n_{i}\!}\equiv b_{n_{i}\!}}$

${\displaystyle f_{i}(a_{1},\dotsc ,a_{n_{i}\!\;\!})\equiv f_{i}(b_{1},\dotsc ,b_{n_{i}\!\;\!})}$.

Core of a homomorphism

If and are two algebraic structures of the same kind and is a homomorphism of this kind, then the kernel of ${\displaystyle \mathbf {A} =(A,(f_{i})_{i\in I})}$ ${\displaystyle \mathbf {B} =(B,(g_{i})_{i\in I})}$ ${\displaystyle \varphi \colon \,\mathbf {A} \to \mathbf {B} }$ ${\displaystyle \varphi }$

${\displaystyle \ker \varphi :=\varphi ^{-1}\circ \varphi =\{(a,b)\in A\times A\mid \varphi (a)=\varphi (b)\}=\colon \equiv }$

a congruence relation on and for all applies: ${\displaystyle \equiv }$ ${\displaystyle \mathbf {A} }$ ${\displaystyle a\in A}$

${\displaystyle [a]_{\equiv }=\varphi ^{-1}(\{\varphi (a)\})=\varphi ^{-1}(\varphi (\{a\}))=\ker \varphi (\{a\})}$.

${\displaystyle \varphi }$can be in a surjective, as follows a bijective and an injective homomorphism disassemble ( homomorphism ):

${\displaystyle \varphi =\mathrm {i} _{\varphi }\circ \varphi ^{\equiv \!}\circ \mathrm {q} _{\equiv }}$

with and the inclusion image . ${\displaystyle \varphi ^{\equiv }\colon \,A/{\equiv }\;{\!\;\twoheadrightarrow \;\!\!\!\!\!\!\!\!\!\!\;\rightarrowtail }\;\varphi (A),\,[a]_{\equiv }\mapsto \varphi (a),}$ ${\displaystyle \mathrm {i} _{\varphi }\colon \,\varphi (A)\rightarrowtail B,\,\varphi (a)\mapsto \varphi (a)}$

generalization

Quotient structure

In general, those equivalence relations on a set play an important role, their quotient mapping ${\displaystyle \equiv }$ ${\displaystyle A}$

${\displaystyle \mathrm {q} _{\equiv }\colon \,A\twoheadrightarrow A/{\equiv },\,a\mapsto [a]_{\equiv },}$

with the structure in compatible or a homomorphism is. ${\displaystyle \mathbf {A} =(A,(R_{i})_{i\in I})}$ ${\displaystyle A}$

The given structure on the quotient set , the so-called factor or quotient structure with relations , ${\displaystyle \mathrm {q} _{\equiv }}$ ${\displaystyle A/{\equiv }}$ ${\displaystyle \mathbf {A} /{\equiv }:=(A/{\equiv },(R_{i,\equiv })_{i\in I})}$ ${\displaystyle R_{i,\equiv }}$

${\displaystyle ([a_{1}]_{\equiv },\dotsc ,[a_{n_{i}}]_{\equiv })\in R_{i,\equiv }\;:\!\iff (a_{1},\dotsc ,a_{n_{i}})\in R_{i}\;\;}$for each , ${\displaystyle i\in I}$

is then again of the same kind as that of . ${\displaystyle A}$

In particular, then all the associated functions with compatible. ${\displaystyle \mathbf {A} }$ ${\displaystyle \equiv }$

Special congruences

Normal divisor of a group

Now denote a group , its neutral element and any normal subgroup of . ${\displaystyle \mathbf {G} =(G,*)}$ ${\displaystyle e}$ ${\displaystyle \mathbf {N} =(N,*)}$ ${\displaystyle \mathbf {G} }$

For each one ${\displaystyle a\in G}$

${\displaystyle aN:=\{a*n\mid n\in N\}}$

the associated secondary class of the normal divisor s . With ${\displaystyle N}$

${\displaystyle G/N:=\{aN\mid a\in G\}}$

and the complex product then forms a group with the neutral element : the factor group of after . ${\displaystyle \cdot }$ ${\displaystyle \mathbf {G} /N:=(G/N,\cdot )}$ ${\displaystyle N=eN}$ ${\displaystyle \mathbf {G} }$ ${\displaystyle N}$

But because

${\displaystyle \varphi _{N}\colon \,\mathbf {G} \to \mathbf {G} /N,\,a\mapsto aN,}$

is a group homomorphism is

${\displaystyle \equiv _{N\,}:=\ker \varphi _{N}}$

a congruence relation on and for all applies: ${\displaystyle \mathbf {G} }$ ${\displaystyle a,b\in G}$

${\displaystyle a\equiv _{N\!}b\iff \varphi _{N}(a)=\varphi _{N}(b)\iff aN=bN}$.

Conversely, any congruence delivers on exactly one normal subgroup in . ${\displaystyle \equiv }$ ${\displaystyle \mathbf {G} }$ ${\displaystyle [e]_{\equiv }}$ ${\displaystyle \mathbf {G} }$

In a group, the normal factors correspond exactly to the congruence relations. Therefore, for any group homomorphism , the normal divisor also becomes ${\displaystyle \varphi \colon \,\mathbf {G} \to \mathbf {H} }$

${\displaystyle [e]_{\equiv }=\ker \varphi (\{e\})}$

referred to as the core of ${\displaystyle \varphi }$ .

Congruence after a module

An additive Abelian group is called a module (from Latin modulus measure). Since each subgroup of a module is normal, the carrier quantities of the subgroups correspond exactly to the congruence relations on a module. ${\displaystyle \mathbf {G} =(G,+)}$ ${\displaystyle \mathbf {M} =(M,+)}$ ${\displaystyle \mathbf {G} }$

This also applies to the carrier quantities of the sub-modules of a module over a ring and in particular also to the sub-vector spaces of a vector space .

The secondary class is designated for everyone ${\displaystyle a\in G}$

${\displaystyle a+M:=\{a+m\mid m\in M\}}$

as a residual after ${\displaystyle M}$ or residue class modulo ${\displaystyle M}$ (from Latin. MODULO , ablative to modulus ), and the factor group 's residual module of after . ${\displaystyle \mathbf {G} /M:=(G/M,+)}$ ${\displaystyle \mathbf {G} }$ ${\displaystyle M}$

If two elements are congruent after , then they are also called congruent after the module or congruent modulo and this is written ${\displaystyle a,b\in G}$ ${\displaystyle \equiv _{M}}$ ${\displaystyle M}$ ${\displaystyle M}$

${\displaystyle a\equiv b{\pmod {M}}\quad }$ or or short . ${\displaystyle \quad a\equiv b\mod M\quad }$ ${\displaystyle \quad a\equiv b\;\;(M)}$

The following applies:

${\displaystyle a\equiv b\mod M\;\;\iff \;\;-b+a\in M}$.

Is simply generated in , i.e. for a , then one also says that they are congruent modulo and notated ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle M=\langle m\rangle :=\{\zeta m\mid \zeta \in \mathbb {Z} \}}$ ${\displaystyle m\in G}$ ${\displaystyle a,b}$ ${\displaystyle m}$

${\displaystyle a\equiv b\mod m}$.

Examples

Identity relation

For every algebraic structure , the equivalence relation given by the graph of the identical mapping to is the equality or identity relation ${\displaystyle \mathbf {A} =(A,(f_{i})_{i\in I})}$ ${\displaystyle \operatorname {id} _{A}}$ ${\displaystyle A}$

${\displaystyle \mathrm {I} _{A}:=\{(a,b)\in A\times A\mid a=b\}=\{(a,a)\mid a\in A\}}$,

a congruence relation . ${\displaystyle \mathbf {A} }$

All relation

To be they are equivalent any two elements. This gives an equivalence relation , the so-called universal or universal relation ${\displaystyle \mathbf {A} =(A,(f_{i})_{i\in I})}$

${\displaystyle \mathrm {U} _{A}:=A\times A=\{(a,b)\mid a,b\in A\}}$,

it is also based on a congruence relation . ${\displaystyle \mathbf {A} }$

Ring ideals

Each ring is a module about itself and the carrier quantities of the associated sub- modules are exactly the ideals of the ring , therefore the ring ideals correspond exactly to the congruence relations . ${\displaystyle \mathbf {R} =(R,+,\cdot )}$ ${\displaystyle (R,+)}$ ${\displaystyle \mathbf {R} }$

L ^p space

In the vector space of the fold integrable functions , is ${\displaystyle ({\mathcal {L}}^{p},+)}$ ${\displaystyle p}$ ${\displaystyle 0<p\leq \infty }$

${\displaystyle {\mathcal {U}}_{0}:=\{f\in {\mathcal {L}}^{p}\mid f(x)=0}$ almost everywhere ${\displaystyle \}}$

Carrier set of a subspace of . ${\displaystyle ({\mathcal {L}}^{p},+)}$

The quotient vector space

${\displaystyle (L^{p},+):=({\mathcal {L}}^{p\!}/{\mathcal {U}}_{0},+)}$

is called space . ${\displaystyle L^{p\!}}$

Congruence of whole numbers

"Congruence" was originally called any congruence of two whole numbers modulo another whole number defined on the main ideal ring of whole numbers : ${\displaystyle (\mathbb {Z} ,+,\cdot )}$ ${\displaystyle \alpha ,\beta }$ ${\displaystyle \mu }$

${\displaystyle \alpha \equiv \beta \mod \mu \;\;\iff \;\;\alpha -\beta \in (\mu ):=\mathbb {Z} \mu =\{\zeta \mu \mid \zeta \in \mathbb {Z} \}}$.

${\displaystyle \alpha }$and are congruent modulo if and only if they have the same remainder when dividing by . ${\displaystyle \beta }$ ${\displaystyle \mu }$ ${\displaystyle \mu }$

More congruence terms

• Congruent number
• Congruence (geometry)

literature

• Stanley Burris, H. P. Sankappanavar: A Course in Universal Algebra . Millennium Edition. 2012 update, ISBN 978-0-9880552-0-9 ( math.uwaterloo.ca [PDF; 4.4 MB ]).
• Udo Hebisch , Hanns Joachim Weinert: Half rings. Algebraic Theory and Applications in Computer Science . Teubner, Stuttgart 1993, ISBN 3-519-02091-2 .
• Thomas Ihringer : General Algebra. With an appendix on Universal Coalgebra by H. P. Gumm (=  Berlin study series on mathematics . Volume 10 ). Heldermann, Lemgo 2003, ISBN 3-88538-110-9 .
• Fritz Reinhardt, Heinrich Soeder: dtv atlas for mathematics. Boards and texts . Volumes 1 and 2. 9th and 8th editions. Deutscher Taschenbuch Verlag, Munich 1991 and 1992, ISBN 3-423-03007-0 and ISBN 3-423-03008-9 .
• B. L. van der Waerden : Algebra . Using lectures by E. Artin and E. Noether. Volume I (=  Heidelberg Pocket Books . Volume 12 ). 9th edition. Springer, Berlin / Heidelberg 1993, ISBN 978-3-642-85528-3 , doi : 10.1007 / 978-3-642-85527-6 .

References and comments

1. ↑ ^{a b c In} the literature, there is usually no clear distinction between a group and its number of carriers . ${\displaystyle \mathbf {G} =(G,*)}$ ${\displaystyle G}$