Substitution in modal fixed-point formulas
Lax369799.MuSubstitution · concepts/Lax369799/MuSubstitution.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Renaming and simultaneous substitution preserve variable binding. Their semantic laws allow finite systems of modal fixed-point equations to be eliminated into the scalar syntax of the modal mu-calculus.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ModalMuCalculus |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Substitution in modal fixed-point formulas |
| 6 | type: theorem |
| 7 | --- |
| 8 | Renaming and simultaneous substitution preserve variable binding. Their |
| 9 | semantic laws allow finite systems of modal fixed-point equations to be |
| 10 | eliminated into the scalar syntax of the modal mu-calculus. |
| 11 | -/ |
| 12 | namespace Lax369799.MuSubstitution |
| 13 | open ModalMuCalculus TransitionSystems |
| 14 | |
| 15 | def lift {n m : ℕ} (f : Fin n → Fin m) : Fin (n + 1) → Fin (m + 1) := |
| 16 | Fin.cases 0 (fun i => (f i).succ) |
| 17 | |
| 18 | def rename {P : Type} {n m : ℕ} (f : Fin n → Fin m) : Formula P n → Formula P m |
| 19 | | .top => .top |
| 20 | | .bot => .bot |
| 21 | | .proposition p => .proposition p |
| 22 | | .negProposition p => .negProposition p |
| 23 | | .variable i => .variable (f i) |
| 24 | | .conj φ ψ => .conj (rename f φ) (rename f ψ) |
| 25 | | .disj φ ψ => .disj (rename f φ) (rename f ψ) |
| 26 | | .diamond φ => .diamond (rename f φ) |
| 27 | | .box φ => .box (rename f φ) |
| 28 | | .mu φ => .mu (rename (lift f) φ) |
| 29 | | .nu φ => .nu (rename (lift f) φ) |
| 30 | |
| 31 | def liftSubstitution {P : Type} {n m : ℕ} (θ : Fin n → Formula P m) : |
| 32 | Fin (n + 1) → Formula P (m + 1) := |
| 33 | Fin.cases (.variable 0) (fun i => rename Fin.succ (θ i)) |
| 34 | |
| 35 | def substitute {P : Type} {n m : ℕ} (θ : Fin n → Formula P m) : Formula P n → Formula P m |
| 36 | | .top => .top |
| 37 | | .bot => .bot |
| 38 | | .proposition p => .proposition p |
| 39 | | .negProposition p => .negProposition p |
| 40 | | .variable i => θ i |
| 41 | | .conj φ ψ => .conj (substitute θ φ) (substitute θ ψ) |
| 42 | | .disj φ ψ => .disj (substitute θ φ) (substitute θ ψ) |
| 43 | | .diamond φ => .diamond (substitute θ φ) |
| 44 | | .box φ => .box (substitute θ φ) |
| 45 | | .mu φ => .mu (substitute (liftSubstitution θ) φ) |
| 46 | | .nu φ => .nu (substitute (liftSubstitution θ) φ) |
| 47 | |
| 48 | axiom eval_rename {P : Type} (S : TransitionSystem P) {n m : ℕ} |
| 49 | (φ : Formula P n) (f : Fin n → Fin m) (ρ : Fin m → Set S.Vertex) : |
| 50 | (rename f φ).eval S ρ = φ.eval S (ρ ∘ f) |
| 51 | |
| 52 | axiom eval_substitute {P : Type} (S : TransitionSystem P) {n m : ℕ} |
| 53 | (φ : Formula P n) (θ : Fin n → Formula P m) (ρ : Fin m → Set S.Vertex) : |
| 54 | (substitute θ φ).eval S ρ = φ.eval S (fun i => (θ i).eval S ρ) |
| 55 | |
| 56 | end Lax369799.MuSubstitution |
| 57 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments