# Definition of 'compatible' operation

1. May 24, 2010

### mnb96

Hello,
given a monoid (M,+)
I define an equivalence relation R on (M,+)

My question is: what does it mean formally that "the operation + is compatible with the equivalence relation R" ?

2. May 24, 2010

### JSuarez

It means that you can define an operation " +' " on M/R, using the "+" already defined on M by:

[a] +' := [a + b]

Where [x] is the x's equivalence class. Note that you may always "sum" two equivalence classes as above, but when "+" is compatible with R, then the result is independent of the representatives, that is, if:

[a] = [a'], = [b']

Then:

[a] +' = [a'] +' [b'] = [a + b] = [a' + b']

3. May 24, 2010

### mnb96

Ok! Thanks a lot.
Is that equivalent to say that R must be a congruence relation on (M,+)?

4. May 24, 2010

### Martin Rattigan

Yes.

A congruence relation on a universal algebra is defined to be an equivalence relation that is compatible in a similar sense to the above with each of its operations.

Specifically if $\mathcal{A}$ is a universal algebra with a system of operations $\Omega$, then an equivalence relation $E$ on $\mathcal{A}$ is a congruence iff
$${(\forall\omega\in\Omega)(\forall a_i,a_i'\in\mathcal{A})a_iEa_i'\Rightarrow a_{i_1}a_{i_2}...a_{i_n}\omega E a_{i_1}'a_{i_2}'...a_{i_n}'\omega\text{ where }\omega\text{ is an }n\text{-ary operation.}}$$
For nullary operations this necessarily follows from the reflexivity of $E$.

A monoid has a binary operation (+) and a nullary operation (1). From the final remark in the preceding paragraph an equivalence relation that is compatible with + is a congruence.

Last edited: May 24, 2010
5. May 24, 2010

### mnb96

Thanks for the explanation!
Now everything is clear.