2
$\begingroup$

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?

$\endgroup$
6
  • 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
    Commented Nov 2, 2014 at 9:26
  • 1
    $\begingroup$ @Raphael why closed? The question is well-formed and clear to my eyes. $\endgroup$
    – Ran G.
    Commented Nov 2, 2014 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
    Commented Nov 2, 2014 at 17:05
  • $\begingroup$ I've edited my question. Basically I do not know how to form y'w'v'u'x' $\endgroup$
    – ForSol
    Commented Nov 2, 2014 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$ Commented Nov 2, 2014 at 21:30

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

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