Congruence Relation iff Compatible with Operation/Proof 2

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

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$