12
$\begingroup$

In a set $X$ we define a binary operation $*$ such that

$$\forall x, y \in X,\ (x*y)*y=y*(y*x)=x.$$

Is $*$ commutative and why?

  • 1
    Do we also assume * is associative?2012-10-21
  • 0
    No, it's not associative.2012-10-21
  • 0
    I guess it is not necessarily commutative.2012-10-21
  • 0
    I guess not. But is there a counterexample?2012-10-21
  • 0
    Such a $(X,*)$ cannot be a subsemigroup of a group $G$, because then all $x\in X$ satisfies $x^2=1$, so $1=(xy)^2=x^2y^2 \implies yx=xy$.2012-10-21
  • 0
    Tried it, doesn't work. What would be $aa$? Probably with $ab=c$ and $ba=d$ for 2 new elements...2012-10-21

3 Answers 3

14

Yes, it is commutative. Here is why : $$ x * y = y*(y*(x*y)) = y * ((x * (x*y))*(x*y)) = y *x. $$ I first use the identity to multiply by $y$ on the left twice, and then I replace the second $y$ by $x*(x*y)$. Then we use the fact that $$ (x * (x * y))*(x*y) = x $$ to remove the bigger chunk.

Hope that helps,

  • 3
    Simple idea : if you want to begin with $x*y$ and end up with $y*x$, you have to 'kill' an $x*y$, but the only way that can happen is if you can make it appear twice. So I wanted to put an extra $x*y$ in there, made it happen, and there you go. =D2012-10-21
  • 3
    You won. Nice one.2012-10-21
  • 0
    with $x=y*(y*x)$ the $x*y$ should be $(y*(y*x))*y$ essentially you proved $y*x=y*x$2012-10-21
  • 0
    @ratchet freak : Read it again. Are you absolutely sure that I am wrong? Note that I used that for $X = x * y$ the fact that $y * (y * X) = X$, i.e. that $y * (y * (x*y)) = x*y$. The extreme left of my equality is $x*y$, the extreme right is $y*x$ and in the middle I just keep using the identity with appropriate choices of $X$ and $Y$ to plug in. Just read it carefully, there's only three steps to find. =)2012-10-21
2

Ah, I think I got a counterexample:

Consider the free monoid $F_2$ on 2 letters $a,b$ (with empty word '$1$'), and consider its quotient $$X:=F_2/(w^2\sim 1) $$ for all words $w\in F_2$. Then, basically $X$ contains those words which doesn't have any substring of the form $ww$, and if such appears at a concatenation, they get just cancelled. For example $aba\cdot ab= a$.

Update: not good, as it is going to be a group, $xy=yx$ will follow from all $x^2=1$...

  • 1
    Do you think the quotient still satisfies the latter?2012-10-21
  • 0
    @PatrickDaSilva: It obviously does, since $y(yx)=(yy)x=x=x(yy)=(xy)y$2012-10-21
  • 0
    You guys should check my answer.2012-10-21
  • 0
    Hmm.. Something is still not OK:( it is a Group!2012-10-21
  • 0
    @tomasz : You assumed the operation is associative.2012-10-21
  • 0
    @Berci : Isn't a monoid having an associative operation? We are working with a binary operation on which nothing is assumed here.2012-10-21
  • 0
    Yes, yes, but I thought also an associative counterexample could be found..2012-10-21
  • 0
    @PatrickDaSilva: but it is associative in this case. It is not a counterexample (because it's an abelian group), but it certainly does satisfy the property.2012-10-21
  • 0
    @tomasz : Perhaps it does, but I am a little tired and I got an answer, so I won't bother going through the details of the non-counter-example =) it's cool we discussed though, I had doubts for a second.2012-10-21
1

Here's a proof that uses the automated theorem prover Prover9.

As a human, I find the output of these things difficult to read, but I find they can help by (a) suggesting an important in-between step, and (b) give a proof (even if it is unreadable), which means the result we're trying to prove is actually true, and it is possible there is a proof with a number of steps that could be understood by humans. (Also, there is a "coolness factor" to automated proofs.)

Here's the input:

formulas(assumptions).  (x * y) * y = x. y * (y * x) = x.  end_of_list.  formulas(goals).  x * y = y * x.  end_of_list. 

and a trimmed version of the output:

============================== PROOF =================================  % Proof 1 at 0.01 (+ 0.00) seconds. % Length of proof is 7. % Level of proof is 3. % Maximum clause weight is 7. % Given clauses 4.  1 x * y = y * x # label(non_clause) # label(goal).  [goal]. 2 (x * y) * y = x.  [assumption]. 3 x * (x * y) = y.  [assumption]. 4 c2 * c1 != c1 * c2.  [deny(1)]. 5 x * (y * x) = y.  [para(3(a,1),2(a,1,1))]. 7 x * y = y * x.  [para(2(a,1),5(a,1,2))]. 8 $F.  [resolve(7,a,4,a)].  ============================== end of proof ==========================