Congruence relation

Last updated May 04, 2024

In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done with equivalent elements will yield equivalent elements.^[1] Every congruence relation has a corresponding quotient structure, whose elements are the equivalence classes (or congruence classes) for the relation.^[2]

Definition

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

General

The general notion of a congruence relation can be formally defined in the context of universal algebra, a field which studies ideas common to all algebraic structures. In this setting, a relation $R$ on a given algebraic structure is called compatible if

for each

n

and each

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

Basic example

The prototypical example of a congruence relation is congruence modulo $n$ on the set of integers. For a given positive integer $n$ , two integers $a$ and $b$ are called congruent modulo $n$ , written

a\equiv b{\pmod {n}}

if $a-b$ is divisible by $n$ (or equivalently if $a$ and $b$ have the same remainder when divided by $n$ ).

For example, $37$ and $57$ are congruent modulo $10$ ,

37\equiv 57{\pmod {10}}

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

Congruence modulo $n$ (for a fixed $n$ ) is compatible with both addition and multiplication on the integers. That is,

if

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 as modular arithmetic. From the point of view of abstract algebra, congruence modulo $n$ is a congruence relation on the ring of integers, and arithmetic modulo $n$ occurs on the corresponding quotient ring.

Example: Groups

For example, a group is an algebraic object consisting of a set together with a single binary operation, satisfying certain axioms. If $G$ is a group with operation $\ast$ , a congruence relation on $G$ is an equivalence relation $\equiv$ on the elements of $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 the identity element is always a normal subgroup, and the other equivalence classes are the other cosets of this subgroup. Together, these equivalence classes are the elements of a quotient group.

Example: Rings

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-sided ideal, and the two operations on the set of equivalence classes define the corresponding quotient ring.

Relation with homomorphisms

If $f:A\,\rightarrow B$ is a homomorphism between two algebraic structures (such as homomorphism of groups, or a linear map between vector spaces), then the relation $R$ defined by

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

if and only if

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

is a congruence relation on $A$ . By the first isomorphism theorem, the image of A under $f$ is a substructure of B isomorphic to the quotient of A by this congruence.

On the other hand, the congruence relation $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

In the particular case of groups, congruence relations can be described in elementary terms as follows: If G is a group (with identity element e and operation *) and ~ is a binary relation on G, then ~ is a congruence whenever:

Given any element a of G, a ~ a ( reflexivity );
Given any elements a and b of G, if a ~ b, then b ~ a ( symmetry );
Given any elements a, b, and c of G, if a ~ b and b ~ c, then a ~ c ( transitivity );
Given any elements a, a′, b, and b′ of G, if a ~ a′ and b ~ b′, then a * b ~ a′ * b′;
Given any elements a and a′ of G, if a ~ a′, then a⁻¹ ~ a′⁻¹ (this is implied by the other four,^{[note 1]}^{[ citation needed ]} so is strictly redundant).

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

A congruence ~ is determined entirely by the set {a ∈ G | a ~ e} of those elements of G that are congruent to the identity element, and this set is a normal subgroup. Specifically, a ~ b if and only if b⁻¹ * 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 of G.

Ideals of rings and the general case

A similar trick allows one to speak of kernels in ring theory as ideals instead of congruence relations, and in module theory as submodules instead of congruence relations.

A more general situation where this trick is possible is with Omega-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

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

A congruence relation on an algebra A is a subset of the direct product A × A that is both an equivalence relation on A and a subalgebra of A × A.

The kernel of a homomorphism is always a congruence. Indeed, every congruence arises as a kernel. For a given congruence ~ on A, the set A / ~ of equivalence classes can be given the structure of an algebra in a natural fashion, the quotient algebra. The function that maps every element of A to its equivalence class is a homomorphism, and the kernel of this homomorphism is ~.

The lattice Con(A) of all congruence relations on an algebra A is algebraic.

John M. Howie described how semigroup 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]

Explanatory notes

↑ Since a′⁻¹ = a′⁻¹ * a * a⁻¹ ~ a′⁻¹ * a′ * a⁻¹ = a⁻¹

Notes

↑ Hungerford (1974), p. 27
↑ Hungerford (1974), p. 26
↑ Barendregt (1990), p. 338, Def. 3.1.1
1 2 Bergman (2011), Sect. 1.5 and Exercise 1(a) in Exercise Set 1.26 (Bergman uses the expression having the substitution property for being compatible)
↑ Howie (1975), p. v

Related Research Articles

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equality. Any number $is equal to itself (reflexive). If, then (symmetric). If and, then (transitive).$

In mathematics, when the elements of some set $have a notion of equivalence, then one may naturally split the set into equivalence classes . These equivalence classes are constructed so that elements and belong to the same equivalence class if, and only if, they are equivalent.$

A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure. For example, the cyclic group of addition modulo n can be obtained from the group of integers under addition by identifying elements that differ by a multiple of $and defining a group structure that operates on each such class as a single entity. It is part of the mathematical field known as group theory.$

In mathematics, given two groups, (G,∗) and (H, ·), a group homomorphism from (G,∗) to (H, ·) is a function h : G → H such that for all u and v in G it holds that

In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type. The word homomorphism comes from the Ancient Greek language: ὁμός meaning "same" and μορφή meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German ähnlich meaning "similar" to ὁμός meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925).

In mathematics, a group is a set with an operation that satisfies the following constraints: the operation is associative and has an identity element, and every element of the set has an inverse element.

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being $0$ .

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

In abstract algebra, a normal subgroup is a subgroup that is invariant under conjugation by members of the group of which it is a part. In other words, a subgroup $of the group is normal in if and only if for all and The usual notation for this relation is$

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

In algebra, the kernel of a homomorphism is generally the inverse image of 0. An important special case is the kernel of a linear map. The kernel of a matrix, also called the null space, is the kernel of the linear map defined by the matrix.

In mathematics, specifically abstract algebra, the isomorphism theorems are theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules, Lie algebras, and various other algebraic structures. In universal algebra, the isomorphism theorems can be generalized to the context of algebras and congruences.

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as $or$

In ring theory, a branch of abstract algebra, a quotient ring, also known as factor ring, difference ring or residue class ring, is a construction quite similar to the quotient group in group theory and to the quotient space in linear algebra. It is a specific example of a quotient, as viewed from the general setting of universal algebra. Starting with a ring R and a two-sided ideal I in R, a new ring, the quotient ring R / I, is constructed, whose elements are the cosets of I in R subject to special + and ⋅ operations.

In mathematics, a quotient algebra is the result of partitioning the elements of an algebraic structure using a congruence relation. Quotient algebras are also called factor algebras. Here, the congruence relation must be an equivalence relation that is additionally compatible with all the operations of the algebra, in the formal sense described below. Its equivalence classes partition the elements of the given algebraic structure. The quotient algebra has these classes as its elements, and the compatibility conditions are used to give the classes an algebraic structure.

In mathematics, a congruence subgroup of a matrix group with integer entries is a subgroup defined by congruence conditions on the entries. A very simple example is the subgroup of invertible 2 × 2 integer matrices of determinant 1 in which the off-diagonal entries are even. More generally, the notion of congruence subgroup can be defined for arithmetic subgroups of algebraic groups; that is, those for which we have a notion of 'integral structure' and can define reduction maps modulo an integer.

In mathematics and computer science, the syntactic monoid $of a formal language is the smallest monoid that recognizes the language .$

In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951. John Mackintosh Howie, a prominent semigroup theorist, described this work as "so all-pervading that, on encountering a new semigroup, almost the first question one asks is 'What are the Green relations like?'". The relations are useful for understanding the nature of divisibility in a semigroup; they are also valid for groups, but in this case tell us nothing useful, because groups always have divisibility.

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$ . In the standard notation of modular arithmetic this congruence is written as

References

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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[5] Since a′⁻¹ = a′⁻¹ * a * a⁻¹ ~ a′⁻¹ * a′ * a⁻¹ = a⁻¹

[FOOTNOTEHungerford197427-1] Hungerford (1974), p. 27

[FOOTNOTEHungerford197426-2] Hungerford (1974), p. 26

[FOOTNOTEBarendregt1990338Def._3.1.1-3] Barendregt (1990), p. 338, Def. 3.1.1

[FOOTNOTEBergman2011Sect._1.5_and_Exercise_1(a)_in_Exercise_Set_1.26_(Bergman_uses_the_expression_''having_the_substitution_property''_for_''being_compatible'')-4] 1 2 Bergman (2011), Sect. 1.5 and Exercise 1(a) in Exercise Set 1.26 (Bergman uses the expression having the substitution property for being compatible)

[FOOTNOTEHowie1975v-6] Howie (1975), p. v

[1]

[2]

[3]

[4]

[note 1]

[5]