Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Do we also assume * is associative? –  coffeemath Oct 21 '12 at 10:14
    
No, it's not associative. –  Ezra Oct 21 '12 at 10:15
    
I guess it is not necessarily commutative. –  Berci Oct 21 '12 at 10:18
    
I guess not. But is there a counterexample? –  Ezra Oct 21 '12 at 10:19
    
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$. –  Berci Oct 21 '12 at 10:48

3 Answers 3

up vote 13 down vote accepted

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,

share|improve this answer
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. =D –  Patrick Da Silva Oct 21 '12 at 11:06
3  
You won. Nice one. –  Berci Oct 21 '12 at 11:06
    
with $x=y*(y*x)$ the $x*y$ should be $(y*(y*x))*y$ essentially you proved $y*x=y*x$ –  ratchet freak Oct 21 '12 at 13:38
    
@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. =) –  Patrick Da Silva Oct 21 '12 at 19:26

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$...

share|improve this answer
1  
Do you think the quotient still satisfies the latter? –  Patrick Da Silva Oct 21 '12 at 10:55
    
@PatrickDaSilva: It obviously does, since $y(yx)=(yy)x=x=x(yy)=(xy)y$ –  tomasz Oct 21 '12 at 11:00
    
You guys should check my answer. –  Patrick Da Silva Oct 21 '12 at 11:02
    
Hmm.. Something is still not OK:( it is a Group! –  Berci Oct 21 '12 at 11:02
    
@tomasz : You assumed the operation is associative. –  Patrick Da Silva Oct 21 '12 at 11:03

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 ==========================
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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