Given the following problem:

Consider the monoid $(\mathbb{Z}, T)$ with the operation $aTb=a+b-a*b$ and the equivalence relation $x \equiv y (\mod{n})$ if and only if $x-y=kn$. Prove that this relation is also compatible with the operation $T$.

If I remember correctly, the the equivalent relation between two elements means that they have the same value when operated on by the function.

But this one seems to be causing me some confusion and I am not sure where to begin. How do I go about proving this?

  • 1
    $\begingroup$ Take $x,y,x',y,'$ with $x\equiv x'$ and $y\equiv y'$ and show that $xTy \equiv x'Ty'$. $\endgroup$ – Christoph Mar 13 '18 at 12:11
  • $\begingroup$ @christoph Thay would be proving that it is equal to its simetric value? Could you explain a bit? $\endgroup$ – Omari Celestine Mar 13 '18 at 12:19

You have to show that

  1. $\equiv\pmod{n}$ is reflexive, that is, for every $z \in \mathbb Z$, we have $z\equiv z\pmod{n}$, which is true since $z-z=0=0\cdot n$.
  2. $\equiv\pmod{n}$ is symmetric, that is, for every $x,y\in \mathbb Z$, if $x\equiv y\pmod{n}$, then $y\equiv x\pmod{n}$, which is also true, since, if $x-y=kn$, then $y-x=-kn$.
  3. $\equiv\pmod{n}$ is transitive, that is, if $x\equiv y\pmod{n}$ and $y\equiv z\pmod{n}$, then $x\equiv z\pmod{n}$. This is also true, because if $x-y=k_1n$ and $y-z=k_2n$, then $x-z=(x-y)+(y-z)=(k_1+k_2)n$.

Edit I completely overlooked part of the question. So the main problem is to show the relation is compatible.

Take $x\equiv x'\pmod{n}$ and $y\equiv y' \pmod{n}$.
Now we show that $xTy \equiv x'Ty' \pmod{n}$.
If $x\equiv x'\pmod{n}$, then there exist $k_x \in \mathbb Z$ such that $x-x'=k_xn$;
similarly, there exists $k_y$ such that $y-y'=k_yn$.
Now, $xTy=x+y-xy$ and $x'Ty'=x'+y'-x'y'$ and we want to show that $$xTy-x'Ty'=kn,$$ for some $k \in\mathbb Z$. But \begin{align} xTy-x'Ty' &= (x+y-xy)-(x'+y'-x'y')\\ &= (x-x')+(y-y')-(xy-x'y')\\ &= k_xn+k_yn-(xy-xy'+xy'-x'y')\\ &= (k_x+k_y)n-x(y-y')-(x-x')y'\\ &= (k_x(1-y')+k_y(1-x))n. \end{align}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.