---
tag: 7DFJTZR3XJ
kind: definition
name: Congruence generated by a relation
msc: [08A30]
defines: QP06QH2Q7C
uses: [QJGPT2W0FT, DCSXXT4SER, XP67WCPQ59]
sources:
  - url: https://en.wikipedia.org/wiki/Congruence_relation
---

## Definition

Let $\mathbf{A}$ be an [[algebra|QJGPT2W0FT]] with universe $A$ and let $R \subseteq A \times A$.
The *congruence generated by* $R$ is
$$\operatorname{Cg}(R) = \bigcap \set{\theta : \theta \text{ is a congruence on } \mathbf{A} \text{ and } R \subseteq \theta}.$$
For $a, b \in A$ one writes $\operatorname{Cg}(a, b)$ for $\operatorname{Cg}(\set{(a, b)})$, the principal congruence of $a$ and $b$.

## Remarks

The family in the intersection contains $A \times A$, so it is nonempty.
An intersection of [[congruences|DCSXXT4SER]] is a congruence, so $\operatorname{Cg}(R)$ is the least congruence containing $R$.

A description from below: $(a, b) \in \operatorname{Cg}(R)$ if and only if there are elements $a = z_0, z_1, \dots, z_n = b$ with the following property.
For each $i < n$ there are $(c_i, d_i) \in R$ and a unary [[polynomial operation|XP67WCPQ59]] $p_i$ with $\set{z_i, z_{i+1}} = \set{p_i(c_i), p_i(d_i)}$.

Example: in the group $(\Z, +, -, 0)$, $\operatorname{Cg}(0, 6)$ is congruence modulo $6$.
Congruence modulo $6$ contains $(0, 6)$, and every congruence $\theta$ containing $(0, 6)$ contains $(a, a + 6k)$ for all $a, k \in \Z$ by compatibility with $+$ and $-$.

Non-example: the equivalence relation with classes $\set{0, 6}$ and singletons elsewhere contains $(0, 6)$ but is not $\operatorname{Cg}(0, 6)$.
It is not a congruence, since $0 + 1 = 1$ and $6 + 1 = 7$ are not related.