Proof of `Shuffle automata and shuffle-finite series` (1st statement)

groundedproofs/Lax619925Proofs/Shuffle.lean · lax-619925

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.

Read the Lean proof on GitHub

Description

The shuffle anti-derivative closure (paper §6): over a finite alphabet, if gg is a left anti-derivative of a tuple ff of shuffle-finite series (leftDerivag=faleftDeriv a g = f a for all aa), then gg is shuffle-finite. The witnessing tuple for gg is gg itself followed by the concatenation of the witnessing tuples of the faf a's: gg is trivially a shuffle polynomial in a tuple containing it (its own variable), and the tuple is closed under left derivatives because leftDerivag=faleftDeriv a g = f a is a shuffle polynomial in the (closed) witnessing tuple for faf a, and each faf a'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).