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![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
![{\ displaystyle \ mathrm {q} _ {\ equiv} \ colon \, A \ twoheadrightarrow A / {\ equiv}, \, a \ mapsto [a] _ {\ equiv},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6baacc296904b19f7720826a230001eaa08212ee)
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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b51012bf7b1b336f68d08efb5853877eefdf0a1)
![{\ displaystyle \ mathbf {A} / {\ equiv}: = (A / {\ equiv}, (f_ {i, \ equiv}) _ {i \ in I})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bd8127fd4d7a3e03e41793f7df4343d63ced3c1)
![\ mathbf {A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0795cc96c75d81520a120482662b90f024c9a1a1)
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
![{\ displaystyle f_ {i, \ equiv}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/014bfe8a18940aa01ee4ba256ccd56c4b618971a)
-
for everyone and everyone ,![{\ displaystyle a_ {1 \! \; \!}, \ dotsc, a_ {n_ {i} \!} \ in A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/062ab65aae4f42a9fe97fd140c8692bcc98d48c7)
![i \ in I.](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d740fe587228ce31b71c9628e089d1a9b37c6be)
of the same kind as that of .
![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Such an equivalence relation is called a congruence relation on and two elements congruent after if they are equivalent with respect to :
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
![\ mathbf {A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0795cc96c75d81520a120482662b90f024c9a1a1)
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
-
.
The equivalence class of each is then called the congruence class .
![{\ displaystyle [a] _ {\ equiv}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba4e6fae6207a74d8f4bc9731c233ef1d89bd6e)
![a \ in A](https://wikimedia.org/api/rest_v1/media/math/render/svg/a97387981adb5d65f74518e20b6785a284d7abd5)
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:
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
![{\ displaystyle \ mathbf {A} = (A, (f_ {i}) _ {i \ in I})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b51012bf7b1b336f68d08efb5853877eefdf0a1)
![f_ {i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65da883ca3d16b461e46c94777b0d9c4aa010e79)
![i \ in I.](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d740fe587228ce31b71c9628e089d1a9b37c6be)
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
![{\ displaystyle a_ {1 \! \; \!}, \ dotsc, a_ {n_ {i} \! \; \!}, b_ {1}, \ dotsc, b_ {n_ {i} \!} \ in A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00d476c78da7e77c06936ef2a78b0511ab4d667a)
![n_ {i} \ in \ mathbb {N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17cc13c5962f46501fd1d792ac09ab2fd6f2527d)
![{\ displaystyle a_ {1 \!} \ equiv b_ {1}, \ dotsc, a_ {n_ {i} \!} \ equiv b_ {n_ {i} \!}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbeaab4b7f6a9df990cf8c557f07a01d437ebe65)
-
.
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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b51012bf7b1b336f68d08efb5853877eefdf0a1)
![{\ displaystyle \ mathbf {B} = (B, (g_ {i}) _ {i \ in I})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72aff7f8a97bbc79e5577ddd544a9b1cea84d5bf)
![{\ displaystyle \ varphi \ colon \, \ mathbf {A} \ to \ mathbf {B}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ec435fd799fd7290d634aaa18dae4d2998fa2e7)
![{\ displaystyle \ ker \ varphi: = \ varphi ^ {- 1} \ circ \ varphi = \ {(a, b) \ in A \ times A \ mid \ varphi (a) = \ varphi (b) \} = \ colon \ equiv}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05dcfb0be2dead7e396a0fff165b2d1b6dc9dc14)
a congruence relation on and for all applies:
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
![\ mathbf {A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0795cc96c75d81520a120482662b90f024c9a1a1)
![a \ in A](https://wikimedia.org/api/rest_v1/media/math/render/svg/a97387981adb5d65f74518e20b6785a284d7abd5)
-
.
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3069c48e918be2da55ae42340bfc2953242a9145)
with and the inclusion image .
![{\ displaystyle \ mathrm {i} _ {\ varphi} \ colon \, \ varphi (A) \ rightarrowtail B, \, \ varphi (a) \ mapsto \ varphi (a)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6299db53e9aab57c2981a09fb22b3ad602eb97c7)
generalization
Quotient structure
In general, those equivalence relations on a set play an important role, their quotient mapping
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
![{\ displaystyle \ mathrm {q} _ {\ equiv} \ colon \, A \ twoheadrightarrow A / {\ equiv}, \, a \ mapsto [a] _ {\ equiv},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6baacc296904b19f7720826a230001eaa08212ee)
with the structure in compatible or a homomorphism is.
![{\ displaystyle \ mathbf {A} = (A, (R_ {i}) _ {i \ in I})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b691c693cfe0294031f57860d1e23aa36340f09a)
![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
The given structure on the quotient set , the so-called factor or quotient structure with relations ,
![{\ displaystyle \ mathrm {q} _ {\ equiv}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57d1caec568ea86707df19d1aaf7b0e4cdbdcf61)
![{\ displaystyle R_ {i, \ equiv}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dfcc58d52034e2cfb968ccd5aad6be9b9355fcb)
-
for each ,![i \ in I.](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d740fe587228ce31b71c9628e089d1a9b37c6be)
is then again of the same kind as that of .
![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
In particular, then all the associated functions with compatible.
![\ mathbf {A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0795cc96c75d81520a120482662b90f024c9a1a1)
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
Special congruences
Normal divisor of a group
Now denote a group , its neutral element and any normal subgroup of .
![{\ displaystyle \ mathbf {G} = (G, *)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/662dd896d65a400aebb8b995e2d65cfbd41789a8)
![e](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd253103f0876afc68ebead27a5aa9867d927467)
![{\ displaystyle \ mathbf {N} = (N, *)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed3fc8d8eb6fc4a08e4e629e3e0a03b3eebee93a)
![{\ displaystyle \ mathbf {G}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6d9c60d3cf462a9812e9a9d021d17c7bc272a5a)
For each one
![a \ in G](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe9f5ea7aea0b7a62b07eae139e7a5038ea5a120)
![{\ displaystyle aN: = \ {a * n \ mid n \ in N \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b50795cd4a042bc98442f0d06cddedddc23e33a)
the associated secondary class of the normal divisor s . With
![N](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
![{\ displaystyle G / N: = \ {aN \ mid a \ in G \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53beed00deb2fa0d1f66762197555bb84234be39)
and the complex product then forms a group with the neutral element : the factor group of after .
![\ cdot](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba2c023bad1bd39ed49080f729cbf26bc448c9ba)
![{\ displaystyle \ mathbf {G} / N: = (G / N, \ cdot)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20c55b2f6cc3a61827b60dc206eeafc5ac415113)
![{\ displaystyle N = eN}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24160b22272c1841dc2210182bdf68b831b62ad5)
![{\ displaystyle \ mathbf {G}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6d9c60d3cf462a9812e9a9d021d17c7bc272a5a)
![N](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
But because
![{\ displaystyle \ varphi _ {N} \ colon \, \ mathbf {G} \ to \ mathbf {G} / N, \, a \ mapsto aN,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7e0706d4dfd6c29ba328a3ffaa3ae047bcc6bf7)
is a group homomorphism is
![{\ displaystyle \ equiv _ {N \,}: = \ ker \ varphi _ {N}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eba670573dc3e6b8eb6f16bd3cf2b8bcb0a763a5)
a congruence relation on and for all applies:
![{\ displaystyle \ mathbf {G}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6d9c60d3cf462a9812e9a9d021d17c7bc272a5a)
![a, b \ in G](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4b3751cbf424027e1e00e22d191a2d465403c79)
-
.
Conversely, any congruence delivers on exactly one normal subgroup in .
![\ equiv](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5c34250859b6f6d2a77b4e8a2ceaa90638076d)
![{\ displaystyle \ mathbf {G}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6d9c60d3cf462a9812e9a9d021d17c7bc272a5a)
![{\ displaystyle [e] _ {\ equiv}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58eee5d988b10565256686ff0b2979781d924025)
![{\ displaystyle \ mathbf {G}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6d9c60d3cf462a9812e9a9d021d17c7bc272a5a)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/222488da3eebcb47a142c852745595c52510d3c0)
![{\ displaystyle [e] _ {\ equiv} = \ ker \ varphi (\ {e \})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21cf5114b7212b3fcf8807d9e026c5d1a5bc5279)
referred to as the core of
.
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 {M} = (M, +)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7de866051be75df24e50220e1640aca48ce9e6f8)
![{\ displaystyle \ mathbf {G}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6d9c60d3cf462a9812e9a9d021d17c7bc272a5a)
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![a \ in G](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe9f5ea7aea0b7a62b07eae139e7a5038ea5a120)
![{\ displaystyle a + M: = \ {a + m \ mid m \ in M \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c5f0451e2d027ca05b5cc56503da9322b9ac161)
as a residual after
or residue class modulo
(from Latin. MODULO , ablative to modulus ), and the factor group 's residual module of after .
![{\ displaystyle \ mathbf {G} / M: = (G / M, +)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4e5d675a8a9afac4cafa55cd23500ce768e9ffc)
![{\ displaystyle \ mathbf {G}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6d9c60d3cf462a9812e9a9d021d17c7bc272a5a)
![M.](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
If two elements are congruent after , then they are also called congruent after the module or congruent modulo and this is written
![a, b \ in G](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4b3751cbf424027e1e00e22d191a2d465403c79)
![{\ displaystyle \ equiv _ {M}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d1ed6b4b30cb682a77091290946779cf218666c)
![M.](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
![M.](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
-
or or short .![{\ displaystyle \ quad a \ equiv b \ mod M \ quad}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20acfac16d9aa287f27cdf7951bd640b0e0da5c1)
![{\ displaystyle \ quad a \ equiv b \; \; (M)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35f82ef981d6df8eff40137417b5f348d87539eb)
The following applies:
-
.
Is simply generated in , i.e. for a , then one also says that they are congruent modulo and notated
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![{\ displaystyle M = \ langle m \ rangle: = \ {\ zeta m \ mid \ zeta \ in \ mathbb {Z} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29d2f1cfbc3af2a37a6776f5f6e5cba91f5c81a9)
![m \ in G](https://wikimedia.org/api/rest_v1/media/math/render/svg/977f3b62e05c59d1cf1ca26fd5980426bdb48c2b)
![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
-
.
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
![\ operatorname {id} _ {A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f8e9928a7f50859422671451607b974756960fa)
-
,
a congruence relation .
![\ mathbf {A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0795cc96c75d81520a120482662b90f024c9a1a1)
All relation
To be they are equivalent any two elements. This gives an equivalence relation , the so-called universal or universal relation
-
,
it is also based on a congruence relation .
![\ mathbf {A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0795cc96c75d81520a120482662b90f024c9a1a1)
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8030c6877bea46ae104cd757872ee5e678f06b5b)
![(R, +)](https://wikimedia.org/api/rest_v1/media/math/render/svg/466356a631ac93bc70fbe2d276117d22f980e285)
![\ mathbf R](https://wikimedia.org/api/rest_v1/media/math/render/svg/5de85fcc2a00d8ba14aae84aeef812d7fef4b3d5)
L p space
In the vector space of the fold integrable functions , is
![{\ displaystyle ({\ mathcal {L}} ^ {p}, +)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/876de46b6486665b7a447138bac1ba964ce0ade2)
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![0 <p \ leq \ infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/915ecfea83a5b7e3432407d4eebea5a38f9948ee)
-
almost everywhere
Carrier set of a subspace of .
![{\ displaystyle ({\ mathcal {L}} ^ {p}, +)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/876de46b6486665b7a447138bac1ba964ce0ade2)
The quotient vector space
![{\ displaystyle (L ^ {p}, +): = ({\ mathcal {L}} ^ {p \!} / {\ mathcal {U}} _ {0}, +)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe89c313418c020b770617626589080da3ea8234)
is called space .
![{\ displaystyle L ^ {p \!}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37902800faa60a07cd4e57478d9c859445c3163b)
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 :
![(\ Z, +, \ cdot)](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a626bb1acb2b3beebb7ed25b98f0cc7fdb7df60)
![\ alpha, \ beta](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4b46b57cfa0011b643037751809904d915c1b48)
![\ mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
-
.
and are congruent modulo if and only if they have the same remainder when dividing by .
![\beta](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ed48a5e36207156fb792fa79d29925d2f7901e8)
![\ mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
![\ mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
More congruence terms
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
-
↑ a b c In the literature, there is usually no clear distinction between a group and its number of carriers .
![{\ displaystyle \ mathbf {G} = (G, *)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/662dd896d65a400aebb8b995e2d65cfbd41789a8)