Congruence if and only if Left and Right Congruence

Question

I have the following problem that I am stuck on:

Let $M$ be a set with a binary operation $\circ$, defined for elements of $M$, and suppose that $\sim$ is an equivalence relation on $M$. Show that congruence with respect to $\sim$ and $\circ$ holds if and only if left congruence and right congruence with respect to $\sim$ and $\circ$ both hold.

Here are the definitions that my class is using:

The equivalence relation is a congruence with respect to $\sim$ and $\circ$ if for all $x,x',y,y'\in M$ with $x\sim x'$ and $y\sim y'$, $(x\circ y)\sim(x'\circ y')$.

Left congruence: If $z\in M$ and $x\sim y$, then $(z\circ x)\sim(z\circ y)$.

Right congruence: If $z\in M$ and $x\sim y$, then $(x\circ z)\sim(y\circ z)$.

I feel like this should be a really easy proof, but I can't seem to figure it out. Thanks in advance for any help or suggestions!

Answer 1

If

$$\begin{array}{rcll} x &\sim& x' \\ x \circ y &\sim& x' \circ y & \text{right congruence} \\ y &\sim& y' \\ x' \circ y &\sim& x' \circ y' & \text{left congruence} \\ x \circ y &\sim& x' \circ y' & \text{equivalence relation is transitive} \\ \end{array}$$

Only if

Let $x,y,z \in M$ such that $x \sim y$. Also, $z \sim z$ because equivalence relation is reflexive. Then, by the given assumption, we have $x \circ z \sim y \circ z$ (right congruence) and $z \circ x \sim z \circ y$ (left congruence).

Remarks

Note how the two properties of equivalence relation are used here. Also, note how symmetry is not used. We can construct a relation that is reflexive and transitive but not symmetric, on a set of two elements $S = \{a,b\}$, as follows: $R = \{(a,a), (a,b), (b,b)\}$, i.e. for all $x,y \in S$, $xRy$ if and only if $(x,y) \ne (b,a)$.

Reflexive

We have $aRa$ and $bRb$, so $R$ is reflexive.

Symmetric

We have $aRb$ but not $bRa$, so $R$ is not symmetric.

Transitive

We have $8$ statements to check:

• $(x,y,z) = (a,a,a): aRa \land aRa \implies aRa$ (true and true implies true)
• $(x,y,z) = (a,a,b): aRa \land aRb \implies aRb$ (true and true implies true)
• $(x,y,z) = (a,b,a): aRb \land bRa \implies aRa$ (true and false implies true)
• $(x,y,z) = (a,b,b): aRb \land bRb \implies aRb$ (true and true implies true)
• $(x,y,z) = (b,a,a): bRa \land aRa \implies bRa$ (false and true implies false)
• $(x,y,z) = (b,a,b): bRa \land aRb \implies bRb$ (false and true implies true)
• $(x,y,z) = (b,b,a): bRb \land bRa \implies bRa$ (true and false implies false)
• $(x,y,z) = (b,b,b): bRb \land bRb \implies bRb$ (true and true implies true)

Congruence

There are 16 binary operations that can be defined on $S$. I'll only pick one:

$$\begin{array}{c|c} \circ&a&b\\\hline a&a&a\\\hline b&b&b \end{array}$$

The verification that $\circ$ and $\sim$ satisfy all three of left congruence, right congruence, and congruence, is left to the reader as an exercise, ending this exploration.