Movatterモバイル変換

[0]ホーム

Jump to content

Congruence relation

Edit links

From Wikipedia, the free encyclopedia

Equivalence relation in algebra

For the term as used in elementary geometry, seecongruence (geometry).

This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(February 2015) (Learn how and when to remove this message)

Inabstract algebra, acongruence relation (or simplycongruence) is anequivalence relation on analgebraic structure (such as agroup,ring, orvector space) that is compatible with the structure in the sense thatalgebraic operations done with equivalent elements will yield equivalent elements.^[1] Every congruence relation has a correspondingquotient structure, whose elements are theequivalence classes (orcongruence classes) for the relation.^[2]

Definition

[edit]

The definition of a congruence depends on the type ofalgebraic structure under consideration. Particular definitions of congruence can be made forgroups,rings,vector spaces,modules,semigroups,lattices, and so forth. The common theme is that a congruence is anequivalence relation on an algebraic object that is compatible with the algebraic structure, in the sense that the operations arewell-defined on theequivalence classes.

General

[edit]

The general notion of a congruence relation can be formally defined in the context ofuniversal algebra, a field which studies ideas common to allalgebraic structures. In this setting, arelation $R {\displaystyle R}$ on a given algebraic structure is calledcompatible if for each $n {\displaystyle n}$ and each $n {\displaystyle n}$ -ary operation $\mu$ defined on the structure: whenever $a_{1}\mathrel {R} a'_{1}$ and ... and $a_{n}\mathrel {R} a'_{n}$ , then $\mu (a_{1},\ldots ,a_{n})\mathrel {R} \mu (a'_{1},\ldots ,a'_{n})$ .

A congruence relation on the structure is then defined as an equivalence relation that is also compatible.^[3]^[4]

Examples

[edit]

Basic example

[edit]

This section is about the(mod n) notation. For the binarymod operation, seemodulo operation.

The prototypical example of a congruence relation iscongruence modulo $n {\displaystyle n}$ on the set ofintegers. For a given positive integer $n {\displaystyle n}$ , two integers $a {\displaystyle a}$ and $b {\displaystyle b}$ are calledcongruent modulo $n {\displaystyle n}$ , written

a\equiv b{\pmod {n}}

if $a-b$ isdivisible by $n {\displaystyle n}$ (or equivalently if $a {\displaystyle a}$ and $b {\displaystyle b}$ have the sameremainder when divided by $n {\displaystyle n}$ ).

For example, $37 {\displaystyle 37}$ and $57 {\displaystyle 57}$ are congruent modulo $10 {\displaystyle 10}$ ,

37\equiv 57{\pmod {10}}

since $37-57=-20$ is a multiple of 10, or equivalently since both $37 {\displaystyle 37}$ and $57 {\displaystyle 57}$ have a remainder of $7 {\displaystyle 7}$ when divided by $10 {\displaystyle 10}$ .

Congruence modulo $n {\displaystyle n}$ (for a fixed $n {\displaystyle n}$ ) is compatible with bothaddition andmultiplication on the integers. That is,

a_{1}\equiv a_{2}{\pmod {n}}

and

b_{1}\equiv b_{2}{\pmod {n}}

then

a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {n}}

and

a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}

The corresponding addition and multiplication of equivalence classes is known asmodular arithmetic. From the point of view of abstract algebra, congruence modulo $n {\displaystyle n}$ is a congruence relation on thering of integers, and arithmetic modulo $n {\displaystyle n}$ occurs on the correspondingquotient ring.

Example: Groups

[edit]

For example, a group is an algebraic object consisting of aset together with a singlebinary operation, satisfying certain axioms. If $G {\displaystyle G}$ is a group with operation $\ast$ , acongruence relation on $G {\displaystyle G}$ is an equivalence relation $\equiv$ on the elements of $G {\displaystyle G}$ satisfying

g_{1}\equiv g_{2}\ \ \,

and

\ \ \,h_{1}\equiv h_{2}\implies g_{1}\ast h_{1}\equiv g_{2}\ast h_{2}

for all $g_{1},g_{2},h_{1},h_{2}\in G$ . For a congruence on a group, the equivalence class containing theidentity element is always anormal subgroup, and the other equivalence classes are the othercosets of this subgroup. Together, these equivalence classes are the elements of aquotient group.

Example: Rings

[edit]

When an algebraic structure includes more than one operation, congruence relations are required to be compatible with each operation. For example, a ring possesses both addition and multiplication, and a congruence relation on a ring must satisfy

r_{1}+s_{1}\equiv r_{2}+s_{2}

and

r_{1}s_{1}\equiv r_{2}s_{2}

whenever $r_{1}\equiv r_{2}$ and $s_{1}\equiv s_{2}$ . For a congruence on a ring, the equivalence class containing 0 is always a two-sidedideal, and the two operations on the set of equivalence classes define the corresponding quotient ring.

Relation with homomorphisms

[edit]

If $f:A\,\rightarrow B$ is ahomomorphism between two algebraic structures (such ashomomorphism of groups, or alinear map betweenvector spaces), then the relation $R {\displaystyle R}$ defined by

a_{1}\,R\,a_{2}

if and only if

f(a_{1})=f(a_{2})

is a congruence relation on $A {\displaystyle A}$ . By thefirst isomorphism theorem, theimage ofA under $f {\displaystyle f}$ is a substructure ofBisomorphic to the quotient ofA by this congruence.

On the other hand, the congruence relation $R {\displaystyle R}$ induces a unique homomorphism $f:A\rightarrow A/R$ given by

f(x)=\{y\mid x\,R\,y\}

Thus, there is a natural correspondence between the congruences and the homomorphisms of any given algebraic structure.

Congruences of groups, and normal subgroups and ideals

[edit]

In the particular case ofgroups, congruence relations can be described in elementary terms as follows:IfG is a group (withidentity elemente and operation *) and ~ is abinary relation onG, then ~ is a congruence whenever:

Given any elementa ofG,a ~a (reflexivity);
Given any elementsa andb ofG,ifa ~b, thenb ~a (symmetry);
Given any elementsa,b, andc ofG, ifa ~bandb ~c, thena ~c (transitivity);
Given any elementsa,a′,b, andb′ ofG, ifa ~a′ andb ~b′, thena *b ~a′ *b′;
Given any elementsa anda′ ofG, ifa ~a′, thena⁻¹ ~a′⁻¹ (this is implied by the other four,^{[note 1]} so is strictly redundant).

Conditions 1, 2, and 3 say that ~ is anequivalence relation.

A congruence ~ is determined entirely by the set{a ∈G |a ~e} of those elements ofG that are congruent to the identity element, and this set is anormal subgroup.Specifically,a ~b if and only ifb⁻¹ *a ~e.So instead of talking about congruences on groups, people usually speak in terms of normal subgroups of them; in fact, every congruence corresponds uniquely to some normal subgroup ofG.

Ideals of rings and the general case

[edit]

A similar trick allows one to speak of kernels inring theory asideals instead of congruence relations, and inmodule theory assubmodules instead of congruence relations.

A more general situation where this trick is possible is withOmega-groups (in the general sense allowing operators with multiple arity). But this cannot be done with, for example,monoids, so the study of congruence relations plays a more central role in monoid theory.

Universal algebra

[edit]

The general notion of a congruence is particularly useful inuniversal algebra. An equivalent formulation in this context is the following:^[4]

A congruence relation on an algebraA is asubset of thedirect productA ×A that is both anequivalence relation onA and asubalgebra ofA ×A.

Thekernel of ahomomorphism is always a congruence. Indeed, every congruence arises as a kernel.For a given congruence ~ onA, the setA / ~ ofequivalence classes can be given the structure of an algebra in a natural fashion, thequotient algebra.The function that maps every element ofA to its equivalence class is a homomorphism, and the kernel of this homomorphism is ~.

ThelatticeCon(A) of all congruence relations on an algebraA isalgebraic.

John M. Howie described howsemigroup theory illustrates congruence relations in universal algebra:

In a group a congruence is determined if we know a single congruence class, in particular if we know the normal subgroup which is the class containing the identity. Similarly, in a ring a congruence is determined if we know the ideal which is the congruence class containing the zero. In semigroups there is no such fortunate occurrence, and we are therefore faced with the necessity of studying congruences as such. More than anything else, it is this necessity that gives semigroup theory its characteristic flavour. Semigroups are in fact the first and simplest type of algebra to which the methods of universal algebra must be applied ...^[5]

Category theory

[edit]

Incategory theory, a congruence relationR on a categoryC is given by: for each pair of objectsX,Y inC, an equivalence relationR_X,Y on Hom(X,Y), such that the equivalence relations respect composition of morphisms. SeeQuotient category § Definition for details.

Explanatory notes

[edit]

^Sincea′⁻¹ =a′⁻¹ *a *a⁻¹ ~a′⁻¹ *a′ *a⁻¹ =a⁻¹

Notes

[edit]

^Hungerford (1974), p. 27
^Hungerford (1974), p. 26
^Barendregt (1990), p. 338, Def. 3.1.1
^^a ^bBergman (2011), Sect. 1.5 and Exercise 1(a) in Exercise Set 1.26 (Bergman uses the expressionhaving the substitution property forbeing compatible)
^Howie (1975), p. v

References

[edit]

Barendregt, Henk (1990). "Functional Programming and Lambda Calculus". In Jan van Leeuwen (ed.).Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 321–364.ISBN 0-444-88074-7.
Bergman, Clifford (2011),Universal Algebra: Fundamentals and Selected Topics, Taylor & Francis
Horn; Johnson (1985),Matrix Analysis, Cambridge University Press,ISBN 0-521-38632-2 (Section 4.5 discusses congruency of matrices.)
Howie, J. M. (1975),An Introduction to Semigroup Theory,Academic Press
Hungerford, Thomas W. (1974),Algebra, Springer-Verlag
Rosen, Kenneth H (2012).Discrete Mathematics and Its Applications. McGraw-Hill Education.ISBN 978-0077418939.