Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Definition of 'compatible' operation

  1. May 24, 2010 #1
    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. jcsd
  3. May 24, 2010 #2
    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']


    [a] +' = [a'] +' [b'] = [a + b] = [a' + b']
  4. May 24, 2010 #3
    Ok! Thanks a lot.
    Is that equivalent to say that R must be a congruence relation on (M,+)?
  5. May 24, 2010 #4

    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 [itex]\mathcal{A}[/itex] is a universal algebra with a system of operations [itex]\Omega[/itex], then an equivalence relation [itex]E[/itex] on [itex]\mathcal{A}[/itex] is a congruence iff
    [tex]{(\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.}}[/tex]
    For nullary operations this necessarily follows from the reflexivity of [itex]E[/itex].

    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
  6. May 24, 2010 #5
    Thanks for the explanation!
    Now everything is clear.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook