Congruence Relation iff Compatible with Operation

From ProofWiki
Jump to navigation Jump to search

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 1

Necessary Condition

Let $\mathcal R$ ibe a congruence relation for $\circ$.

That is:

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


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

That is:

$\forall z \in S: z \mathop {\mathcal R} 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 {\mathcal R} y \implies \paren {x \circ z} \mathrel {\mathcal R} \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 {\mathcal R} y \implies \paren {z \circ x} \mathrel {\mathcal R} \paren {z \circ y}$

$\Box$


Sufficient Condition

Now let $\mathcal R$ have the nature that:

\(\displaystyle \forall x, y, z \in S: \ \ \) \(\displaystyle x \mathrel {\mathcal R} y\) \(\implies\) \(\displaystyle \paren {x \circ z} \mathrel {\mathcal R} \paren {y \circ z}\)
\(\displaystyle x \mathrel {\mathcal R} y\) \(\implies\) \(\displaystyle \paren {z \circ x} \mathrel {\mathcal R} \paren {z \circ y}\)


Then we have:

\(\displaystyle \forall x_1, x_2, y_1, y_2 \in S: \ \ \) \(\displaystyle x_1 \mathrel {\mathcal R} y_1\) \(\implies\) \(\displaystyle \paren {x_1 \circ x_2} \mathrel {\mathcal R} \paren {y_1 \circ x_2}\)
\(\displaystyle x_2 \mathrel {\mathcal R} y_2\) \(\implies\) \(\displaystyle \paren {y_1 \circ x_2} \mathrel {\mathcal R} \paren {y_1 \circ y_2}\)


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

Thus it follows that:

$\paren {x_1 \circ x_2} \mathrel {\mathcal R} \paren {y_1 \circ y_2}$

$\Box$


The result follows.

$\blacksquare$


Proof 2

We have that an equivalence relation is a (symmetric) preordering.

Thus the result Preordering of Products under Operation Compatible with Preordering can be applied directly.

$\blacksquare$


Sources