# Congruence Relation iff Compatible with Operation/Proof 1

## Theorem

Let $\struct {S, \circ}$ be an algebraic structure.

Let $\RR$ be an equivalence relation on $S$.

Then $\RR$ is a congruence relation for $\circ$ if and only if:

 $\displaystyle \forall x, y, z \in S: \ \$ $\displaystyle x \mathrel \RR y$ $\implies$ $\displaystyle \paren {x \circ z} \mathrel \RR \paren {y \circ z}$ $\displaystyle x \mathrel \RR y$ $\implies$ $\displaystyle \paren {z \circ x} \mathrel \RR \paren {z \circ y}$

That is, if and only if $\RR$ is compatible with $\circ$.

## Proof

### Necessary Condition

Let $\RR$ ibe a congruence relation for $\circ$.

That is:

$\forall x_1, x_2, y_1, y_2 \in S: x_1 \mathrel \RR x_2 \land y_1 \mathrel \RR y_2 \implies \paren {x_1 \circ y_1} \mathrel \RR \paren {x_2 \circ y_2}$

As $\RR$ is an equivalence relation it is by definition reflexive.

That is:

$\forall z \in S: z \mathrel \RR z$

Make the substitutions:

 $\displaystyle x_1$ $\to$ $\displaystyle x$ $\displaystyle x_2$ $\to$ $\displaystyle y$ $\displaystyle y_1$ $\to$ $\displaystyle z$ $\displaystyle y_2$ $\to$ $\displaystyle z$

It follows that:

$\forall x, y, z \in S: x \mathrel \RR y \implies \paren {x \circ z} \mathrel \RR \paren {y \circ z}$

Similarly, make the substitutions:

 $\displaystyle x_1$ $\to$ $\displaystyle z$ $\displaystyle x_2$ $\to$ $\displaystyle z$ $\displaystyle y_1$ $\to$ $\displaystyle x$ $\displaystyle y_2$ $\to$ $\displaystyle y$

It follows that:

$\forall x, y, z \in S: x \mathrel \RR y \implies \paren {z \circ x} \mathrel \RR \paren {z \circ y}$

$\Box$

### Sufficient Condition

Now let $\RR$ have the nature that:

 $\displaystyle \forall x, y, z \in S: \ \$ $\displaystyle x \mathrel \RR y$ $\implies$ $\displaystyle \paren {x \circ z} \mathrel \RR \paren {y \circ z}$ $\displaystyle x \mathrel \RR y$ $\implies$ $\displaystyle \paren {z \circ x} \mathrel \RR \paren {z \circ y}$

Then we have:

 $\displaystyle \forall x_1, x_2, y_1, y_2 \in S: \ \$ $\displaystyle x_1 \mathrel \RR y_1$ $\implies$ $\displaystyle \paren {x_1 \circ x_2} \mathrel \RR \paren {y_1 \circ x_2}$ $\displaystyle x_2 \mathrel \RR y_2$ $\implies$ $\displaystyle \paren {y_1 \circ x_2} \mathrel \RR \paren {y_1 \circ y_2}$

As $\RR$ is an equivalence relation it is by definition transitive.

Thus it follows that:

$\paren {x_1 \circ x_2} \mathrel \RR \paren {y_1 \circ y_2}$

$\Box$

The result follows.

$\blacksquare$