Regular-language-formation recovery identity
ProvedHJMEilenberg.recover_languagesLet be finite, let be a regular-language formation, and let be a finite-index congruence formation that agrees at every variable family with the construction . Then applying the congruence-to-language construction recovers the original formation pointwise:
This is the second inverse identity in the final formation isomorphism.
import Definitions.Def_HJMEilenberg_Formations
namespace HJMEilenberg
open MSKleene
/-- Second recovery identity in Proposition 6.23. -/
theorem recover_languages {S : Type} [Finite S] {sig : Signature S}
(L : RegularLanguageFormation sig)
(F : FiniteIndexCongruenceFormation sig)
(hF : ∀ X : SSet S, F.congruences X = congruencesOf L X) :
∀ X : SSet S, languagesOf F X = L.languages X := by
sorry
end HJMEilenbergRead-back
What the Lean code literally says, in plain math · gpt-5
For every finite type , every -sorted signature assigning a type of operation symbols to each finite input-sort list and output sort , every regular-language formation over , and every finite-index congruence formation over , assume that for every arbitrary -sorted family of variable types , is exactly the set of congruences on the free algebra such that (i) the disjoint union of their quotient classes is finite and (ii) every sorted language saturated by —meaning implies —belongs to . Here consists sortwise of the terms generated from variables in by the operations of ; a congruence is a sortwise equivalence relation compatible with every operation; and means at every sort. The packaged assumptions on further say that is nonempty for every , is closed under componentwise intersection, is upward closed under , contains only finite-index congruences, and is closed under pullback as follows: if and is a homomorphism for which is surjective at every sort, then the congruence belongs to . The packaged assumptions on say that every member of is regular, meaning that its syntactic congruence has finite index; that every language saturated by the universal congruence belongs to ; that whenever , every language saturated by the intersection of their syntactic congruences also belongs to ; and that if , is sortwise surjective after quotienting by the syntactic congruence of , and is saturated by that congruence’s pullback along , then . Literally, the syntactic congruence used here relates of sort exactly when, for every congruence , if every congruence saturating the language is contained in , then . Under the displayed equality for all , the conclusion is that for every , is exactly , with no uniqueness required of the witnessing . All quantifiers include , empty variable components , empty term carriers, and signatures with empty operation-symbol types; no is assumed finite or inhabited. Consequently, sortwise compatibility and saturation clauses are vacuous on empty term carriers, all sort-indexed clauses are vacuous when is empty, and a required quotient-surjectivity premise may be impossible when its source carrier is empty but its target quotient is inhabited.
Confirmed by the mission captain (proposal self-audit).