Congruence generated by a relation

Remarks

The family in the intersection contains $A \times A$, so it is nonempty. An intersection of congruences 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 $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.