Operation on Set for which Every Equivalence Relation is Congruence

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set with at least $3$ elements.

Let $\circ$ be an operation on $S$ such that every equivalence relation on $S$ is a congruence relation for $\circ$.


Then $\circ$ is one of the following:

the right operation $\to$
the left operation $\gets$
the constant operation $\sqbrk c$ for some $c \in S$.


Proof

First we note that from:

Equivalence Relation is Congruence for Constant Operation
Equivalence Relation is Congruence for Left Operation
Equivalence Relation is Congruence for Right Operation

every equivalence relation on $S$ is a congruence relation for the right operation, the left operation and the constant operation.

Let $\circ$ be an operation on $S$ which is not one of those three.



Then there exists $x_1, x_2, y_1, y_2 \in S$ such that:

$x_1 \circ y_1 = z_1$
$x_2 \circ y_2 = z_2$

where:

$z_1 \ne z_2$
$\map \lnot {z_1 = x_1 \land z_2 = x_2}$
$\map \lnot {z_1 = y_1 \land z_2 = y_2}$

The above are possible only if there are more than $3$ elements in $S$.


Let $\RR$ be an equivalence relation on $S$ such that:

$x_1 \mathrel \RR x_2$
$y_1 \mathrel \RR y_2$

but that:

$\map \lnot {z_1 \mathrel \RR z_2}$

Then $\RR$ is not a congruence relation.

The result follows from the Rule of Transposition.

$\blacksquare$


Sources