Proof of `Linearly-finite and recognisable series` (1st statement)

groundedproofs/Lax619925Proofs/Recognisable.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

If gg is a left anti-derivative of the tuple ff (leftDerivag=faleftDeriv a g = f a for every letter aa) and each faf a is linearly finite, then gg is linearly finite. The witness is g∪⋃aGa{g} ∪ ⋃ₐ Gₐ, where GaGₐ is a finite generator set for faf a; the union is finite because αα is a FintypeFintype. Every generator of the witness maps under a left derivative either to faf a (if it is gg) or into the span of its own GaGₐ (if it comes from some GbG_b), and both of those lie in the span of the whole witness.