Syntactic congruence universal property
ProvedHJMEilenberg.syntactic_universalLet be a many-sorted -algebra and a sorted language in . The syntactic congruence saturates , and for every congruence on ,
Thus is exactly the greatest algebra congruence whose equivalence classes preserve membership in . This universal property connects the supremum-style Lean definition with the syntactic congruence used throughout the paper.
import Definitions.Def_HJMEilenberg_Formations
namespace HJMEilenberg
open MSKleene
/-- Proposition 5.4: the syntactic congruence is the greatest congruence
saturating a language. -/
theorem syntactic_universal {S : Type} {sig : Signature S}
(A : Algebra sig) (L : Language A) :
Saturated (syntacticCongruence A L) L ∧
∀ Phi : Congruence A,
Saturated Phi L ↔ Phi ≤ syntacticCongruence A L := by
sorry
end HJMEilenbergRead-back
What the Lean code literally says, in plain math · gpt-5
For every small type of sorts, every -sorted signature (assigning a type of operation symbols to each finite input-sort list , including , and output sort ), every -algebra (a carrier type at each sort and a total interpretation of every operation symbol), and every language with arbitrary subsets , let be the following syntactic congruence on : a congruence means a family of equivalence relations, one on each , preserved componentwise by every basic operation, and means that for every congruence on , if every congruence whose classes preserve membership in —that is, satisfying —is pointwise contained in , then ; explicitly, the containment means . The theorem asserts the conjunction that itself preserves membership in , namely , and that for every congruence on , preserves membership in if and only if , i.e. if and only if . There are no assumptions that , the signature, or any carrier is finite or nonempty, nor any decidable-equality assumption: may be empty (making all sortwise clauses vacuous), individual carrier sorts may be empty (making their elementwise clauses vacuous), the signature may have no symbols or may have nullary symbols where an algebra can interpret them, and may be empty, full, or otherwise arbitrary at each sort (for an empty or full component its membership-equivalence condition is automatically true).
Confirmed by the mission captain (proposal self-audit).