Let $x$, $u$, $v$, $w$, $y$, $x'$, $u'$, $v'$, $w'$, $y'$ be words. If

  1. $y'x' = xy$
  2. $y'u'x' = xuy$
  3. $y'v'x' = xvy$
  4. $y'w'x' = xwy$
  5. $y'v'u'x' = xuvy$
  6. $y'w'v'x' = xvwy$

all hold, then I need to prove that $y'w'v'u'x' = xuvwy$.

I'm a little confused how to prove this, How can I form $y'w'v'u'x'$ from the equations above?


closed as unclear what you're asking by Luke Mathieson, Raphael Nov 2 '14 at 9:27

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What do you not understand? Note that if there is no set of suitable words, then the implication you are supposed to prove is true. $\endgroup$ – Raphael Nov 2 '14 at 9:26
  • 1
    $\begingroup$ @Raphael why closed? The question is well-formed and clear to my eyes. $\endgroup$ – Ran G. Nov 2 '14 at 14:43
  • 2
    $\begingroup$ @RanG. It's a problem dump. ForSol does not state what they don't understand (the problem statement seems clear to me, indeed) nor what particular problem they face in finding a solution. In other words, there's not question here. $\endgroup$ – Raphael Nov 2 '14 at 17:05
  • $\begingroup$ I've edited my question. Basically I do not know how to form y'w'v'u'x' $\endgroup$ – ForSol Nov 2 '14 at 21:27
  • 1
    $\begingroup$ @Raphael ForSol did state their difficulty: starting with y'w'v'u'x', pattern matching doesn't reveal any further rule that can be applied. $\endgroup$ – Yuval Filmus Nov 2 '14 at 21:30

Suppose without loss of generality that $|y'| \geq |x|$. If we write $y' = xa$ then $ax' = y$. The equalities then become

  1. $xau'x' = xuax'$.
  2. $xav'x' = xvax'$.
  3. $xaw'x' = xwax'$.
  4. $xav'u'x' = xuvax'$.
  5. $xaw'v'x' = xvwax'$.

Cancelling $x,x'$, we get

  1. $au' = ua$.
  2. $av' = va$.
  3. $aw' = wa$.
  4. $av'u' = uva$.
  5. $aw'v' = vwa$.

Using $y' = xa$, (5), (1), and $y = ax'$, we get $$ y'w'v'u'x' = xaw'v'u'x' = xvwau'x' = xvwuax' = xvwuy. $$ This is close to what we want, only we got $vwu$ instead of $uvw$.

Plugging (2) into (4) gives $uva = av'u = vau' = vua$, and so $u$ and $v$ commute. Similarly, plugging (2) into (5) gives $vwa = aw'v' = wav'=wva$, and so $v$ and $w$ commute. The set of words commuting with $v$ forms a commutative monoid (since all are powers of some primitive word), and so $u$ and $w$ also commute. Therefore $vwu = uvw$, completing the proof.


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