Proof of `Linearly-finite and recognisable series` (5th 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

The equality (zeroness) problem is decidable for recognisable series over a finite alphabet (paper §4). The decider decZerodecZero reads, as a BoolBool, the linear-algebra condition that the initial vector annihilates the subspace reachable from the final vector: r.sem=0r.sem = 0 iff that annihilation holds (semZeroiffannihilatesReachablesemZero_iff_annihilatesReachable), and the annihilation condition is decidable (it lives in the finite-dimensional space Finr.dim→QFin r.dim → ℚ), so r.sem=0r.sem = 0 is.