Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
βŒ•
Log in
← Formalpedia

Β§7, p. 218 β€” C_𝒒(L), F_𝒒(L) (and C_𝒒(L) ∩ F_𝒒(L)) contain their supremal elements

Proved
RamadgeWonham.Synthesis.supremal_elements

by mikedeng1 Β· Sep 27, 2026 Β· Mathlib 0df444a (Lean v4.33.1)

discrete-event-systemsformal-languagesp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1supervisory-control

Let G\mathcal GG be a generator over a finite alphabet with controllable events Ξ£c\Sigma_cΞ£c​ and L(G)=LΛ‰m(G)L(\mathcal G) = \bar L_m(\mathcal G)L(G)=LΛ‰m​(G), and let LβŠ†L(G)L \subseteq L(\mathcal G)LβŠ†L(G). Each of the classes

CG(L),FG(L),CG(L)∩FG(L)\mathbf C_{\mathcal G}(L), \qquad \mathbf F_{\mathcal G}(L), \qquad \mathbf C_{\mathcal G}(L) \cap \mathbf F_{\mathcal G}(L)CG​(L),FG​(L),CG​(L)∩FG​(L)

contains a (necessarily unique) greatest element with respect to inclusion, namely the union of all its members; these are denoted sup⁑CG(L)\sup \mathbf C_{\mathcal G}(L)supCG​(L), sup⁑FG(L)\sup \mathbf F_{\mathcal G}(L)supFG​(L) and sup⁑{CG(L)∩FG(L)}\sup\{\mathbf C_{\mathcal G}(L) \cap \mathbf F_{\mathcal G}(L)\}sup{CG​(L)∩FG​(L)}.

The supremal controllable sublanguage is the central object of the theory: Theorem 7.1 identifies it as the behaviour of the minimally restrictive supervisor.

Formalization Note. sup⁑\supsup is sSup in the complete lattice Set (List Ξ±) (the union of the class), and "contains its supremal element" is IsGreatest. The third class is the one Theorem 7.1 (ii) uses; the paper covers it by "In fact, CG(L)\mathbf C_{\mathcal G}(L)CG​(L) and FG(L)\mathbf F_{\mathcal G}(L)FG​(L) are complete subsemilattices".

Preamble
import Mathlib
import Definitions.Def_RamadgeWonham_Synthesis_Controllable
Formal statement
namespace RamadgeWonham.Synthesis

/-- Ramadge–Wonham 1987, Β§7, p. 218, display after the proof of Proposition 7.1. Standing
assumptions: `Ξ£` finite (p. 207), `L(𝒒) = LΜ„_m(𝒒)` (Β§5, p. 213). For `L βŠ† L(𝒒)`, each of
`C_𝒒(L)`, `F_𝒒(L)` (and `C_𝒒(L) ∩ F_𝒒(L)`, used in Theorem 7.1 (ii)) contains a supremal element
with respect to inclusion, namely its union `sup = sSup`. -/
theorem supremal_elements {Ξ± : Type} [Fintype Ξ±] (G : Shared.Generator Ξ±) (Ec : Set Ξ±)
    (hG : G.L = Shared.pre G.Lm) (L : Set (List Ξ±)) (hL : L βŠ† G.L) :
    IsGreatest (Cset G Ec L) (sSup (Cset G Ec L)) ∧
      IsGreatest (Fset G L) (sSup (Fset G L)) ∧
      IsGreatest (Cset G Ec L ∩ Fset G L) (sSup (Cset G Ec L ∩ Fset G L)) := by sorry

end RamadgeWonham.Synthesis
Source
Ramadge and Wonham, Supervisory Control of a Class of Discrete Event Processes, SIAM J. Control Optim. 25(1), 1987, p. 218, Β§7, display after the proof of Proposition 7.1
Human review
  • Endorsed by Shuze Chen Β· Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 Β· Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
Β© 2026 Prove2Me