Lemma concerning compatibility of words (formed by a term algebra)

Question

I need to prove the next lemma regarding compatibility of words in term algebras, that includes 3 parts:

1. $u,v$ are compatible iff $u^ \smallfrown w_1= v^ \smallfrown w_2$.

2. If $u_1u_2$ and $v_1v_2$ are compatible, then $u_1$ and $v_1$ are compatible.

3. If $uv$ and $uw$ are compatible, then $v$ and $w$ are compatible.

Definition 1. $x$ is a prefix of $w$ iff $w=x^ \smallfrown v$. Also, $x^ \smallfrown v=xv$ (both notations are interchangeable)

Definition 2. Two words $u$, $v$ are compatible if one of them is a prefix of the other. An equivalent definition is: $uu' = vv'$ for some $u'$, $v'$.

I would very much appreciate your help checking the proof I worked out, whether the math makes sense, and paying special attention to writing, I will thank you very much if you can point out details that are missing or a different wording that would make things clearer etc.

Proof:

1 $\Rightarrow$Let $u$ and $v$ be two compatible words. Assume $v$ is a prefix of $u$, hence $u=v^ \smallfrown v'$. Let $w_1$ be a word and take $u^ \smallfrown w_1$, by the previous assumption, $u^ \smallfrown w_1 = v^ \smallfrown v'^ \smallfrown w_1$. Let $w_2= v'^ \smallfrown w_1$. Therefore, $u^ \smallfrown w_1 =v^ \smallfrown w_2 $. $\Leftarrow$. Is trivial. Assume $u^ \smallfrown w_1 = v^ \smallfrown w_2 $, this is exactly the alternative part of definition 2 for compatible words.

2 Let $u_1u_2$ and $v_1v_2$ be compatible words. Assume $v_1v_2$ is a prefix of $u_1u_2$, therefore, $u_1u_2=v_1v_2v'$. Define $w_1= u_1$ and $w_2=v_2v'$, then $u_1w_1=v_1w_2$. By the equivalent definition of compatible words in definition 2, $u_1$ and $v_1$ are compatible.

3 Let $uv$ and $uw$ be compatible words. Assume that $uv$ is a prefix of $uw$, then $uw=uvv'$. In this one I have a bit more trouble with expressing it, the idea is the next: $uw$ and $uv$ are compatible, it means that one forms the first part of the other, so, as and example, if you have $1112^ \smallfrown 344 ^ \smallfrown5$ and $1112^ \smallfrown 344$ its clear that if you delete the first part that is equal, the remaining one will still be compatible, but I can't find the way to express it formally.

I would very much appreciate your input about this proof

Answer 1

HINT

We can try by contradiction ...

The "compatibility" relation is a congruence relation on the algebraic structure of terms with the operation of concatenation.

We want to prove that :

If $uw_1$ and $uw_2$ are congruent (i.e. compatible), then $w_1$ and $w_2$ are congruent.

Assume that they are not; i.e. that :

for no $h,k ,\, $ : $ \, w_1h=w_2k$.

But then, "prefixing" $u$ to both words does not chenge the situation; i.e. we cannot get, by prefixing only, that the couple of "un-compatible" words give rise to new couple taht is compatible. Thus :

for no $h,k ,\, $ : $ \, u(w_1h)=u(w_2k)$.

But $uw_1$ and $uw_2$ are congruent, i.e. $(uw_1)z_1=(uw_2)z_2$, for some $z_1,z_2$.

Thus, we can conclude with the desired property if we can state the associativity of the operation of concatenation.

Do you have proved it already ?