Proof of `Shuffle automata and shuffle-finite series` (1st statement)
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The shuffle anti-derivative closure (paper §6): over a finite alphabet, if is a left anti-derivative of a tuple of shuffle-finite series ( for all ), then is shuffle-finite. The witnessing tuple for is itself followed by the concatenation of the witnessing tuples of the 's: is trivially a shuffle polynomial in a tuple containing it (its own variable), and the tuple is closed under left derivatives because is a shuffle polynomial in the (closed) witnessing tuple for , and each 's witnessing tuple is itself closed. The finiteness of the alphabet is what makes the combined tuple finite. The proof proceeds entirely at the semantic level (shuffle polynomials in a tuple closed under left derivatives).