LARA

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.