Congruence relation

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. Every congruence relation has a corresponding quotient structure, whose elements are the equivalence classes (or congruence classes) for the relation.

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

{\displaystyle R}

on a given algebraic structure is called compatible if for each

n

{\displaystyle n}

and each

n

{\displaystyle n}

-ary operation

μ

{\displaystyle \mu }

defined on the structure: whenever

a

1

R

a

1

′

{\displaystyle a_{1}\mathrel {R} a'_{1}}

and ... and

a

n

R

a

n

′

{\displaystyle a_{n}\mathrel {R} a'_{n}}

, then

μ

(

a

1

,

…

,

a

n

)

R

μ

(

a

1

′

,

…

,

a

n

′

)

{\displaystyle \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.

Examples

Basic example

The prototypical example of a congruence relation is congruence modulo

n

{\displaystyle n}

on the set of integers.