Proof of completeness for shuffles
Proposition (Completeness for shuffles).
If [[s1]] [[s2]]
then s1 = s2.
Proof.
First show by induction on s that:
=
Then show by induction on s that:
=
Then show by induction on s that we can
find a shuffle t such that:
=
(The previous result is needed in the case of composition).
Finally, iteratively use the first and last properties to show that
if [[s1]] [[s2]]
then s1 = s2.
Back