Notes on Congruences

We say that a relation $r \subseteq D \times D$ is a congruence with respect to a set of functions and relations iff, when we consider a first-order language containing symbols for these functions and relations and interpret 'eq' as $r$ , the Axioms for Equality hold in the resulting structure $I$ .

We next fix $D$ as well as functions and relations and consider the set of all congruences on the set $D$ with respect to these functions and relations.

We assume no relation symbols other than congruence itself. (We represent a predicate $p(x_1,\ldots,x_n)$ as $f_p(x_1,\ldots,x_n)=true$ .)

Intersection of Congruences

Theorem: Let $S$ be a set of congruences. Then $\bigcap S$ is also a congruence. Note: we define $\bigcap S = \{ x \mid \forall r \in S. x \in r \}$ .

Proof:

We will consider the case of $S = \{ r_1, r_2\}$ . It case be generalized to arbitrary number of relation, because $\cap$ is associative.

Reflexive: $\forall x. (x,x) \in r_1 \wedge (x,x) \in r_2$ because $r_1,r_2$ are congruence. It implies that $(x,x) \in \bigcap S$ .

Symmetric: $\forall x,y. ((x,y) \in r_1 \rightarrow (y,x) \in r_1) \wedge ((x,y) \in r_2 \rightarrow (y,x) \in r_2)$ because $r_1,r_2$ are congruence. It implies that $(x,y) \in \bigcap S \rightarrow (y,x) \in \bigcap S$ .

Transitive:

$\begin{equation*}\begin{array}{rcl} (x,y) \in \bigcap S \wedge (y,z) \in \bigcap S &\rightarrow& (x,y) \in r_1,r_2 \wedge (y,z) \in r_1,r_2 \\ r_1,r_2 ~~ \text{transitive} & \rightarrow & (x,z) \in r_1,r_2 \\ & \rightarrow & (x,z)\in \bigcap S \end{array} \end{equation*}$

Congruence conditions: $\forall x_1,\ldots,x_n,y_1,\ldots,y_n.$

$\begin{equation*}\begin{array}{rcl} \bigwedge_{i=0}^n (x_i,y_1) \in \bigcap S & \rightarrow & \bigwedge_{i=0}^n (x_i,y_1) \in r_1,r_2 \\ r_1,r_2 ~~ \text{congruence relations} & \rightarrow & (f(x_1,\ldots, x_n), f(y_1,\ldots, y_n)) \in r_1,r_2 \\ & \rightarrow & f(x_1,\ldots, x_n) = f(y_1,\ldots, y_n) \in \bigcap S \end{array} \end{equation*}$

End of Proof.

Existence of the Least Congruence Containing Given Relation

Theorem: Let $r_0$ be a relation. Let $S$ be the set of all congruences $r$ such that $r_0 \subseteq r$ and let $r_* = \bigcap S$ . Then $r_*$ is the least congruence containing $r_0$ , that is

$r_*$ is a congruence
$r_0 \subseteq r_*$
if $r'$ is a congruence such that $r_0 \subseteq r'$ , then $r_* \subseteq r'$

Construction of the Least Congruence Containing Given Relation

Define

$\begin{equation*}\begin{array}{rcl} C(r) &=& r \cup \Delta_D \cup r^{-1} \cup r \circ r\ \cup \\ & & \{ ((f(x_1,\ldots,x_n),f(y_1,\ldots,y_n)) \mid \bigwedge_{i=1}^n (x_i,y_i) \in r \} \end{array} \end{equation*}$

Let $r_{n+1} = C(r_n)$ for $n \ge 0$ .

Theorem: $\bigcup_{n \ge 0} r_n$ is the least congruence containing $r_0$ .

Proof (sketch):

$r_* \subseteq \bigcup_{n \ge 0} r_n$ : $\bigcup_{n \ge 0} r_n$ is a congruence that contains $r_0$ , thus $r_* \subseteq \bigcup_{n \ge 0} r_n$ .
$\bigcup_{n \ge 0} r_n \subseteq r_*$ : by induction on $n$ .
- $n=0$ : $r_0 \subseteq r_*$ by definition of $r_*$
- $n \rightarrow n+1$ : all elements introduced by $C(r_n)$ are required to be in $r_*$ by definition of congruence, so if $r_n \subseteq r_*$ then also $r_{n+1} \subseteq r_*$

End of Proof.