Logic on arbitrary transition systems
Lax369799.UnrestrictedLogic · concepts/Lax369799/UnrestrictedLogic.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Transition systems may have arbitrary state spaces. The usual MSO and modal fixed-point semantics agree with the finite-system semantics on finite presentations. The modal mu-calculus translates to MSO and is bisimulation invariant on arbitrary state spaces.
Concept map
Evidence
This concept declares 10 statements. Each proof establishes one of them relative to its assumptions.
1 eval_monotone proven
2 finite_bisimulation proven
3 finite_mso proven
4 finite_mso_models proven
5 finite_mu proven
6 finite_mu_models proven
7 mu_bisimulation_invariant proven
8 mu_definable_implies_mso_invariant proven
9 mu_to_mso proven
10 translate_correct proven
Lean source view on GitHub
| 1 | import Lax369799.UnrestrictedTransitionSystems |
| 2 | import Lax369799.MonadicSecondOrder |
| 3 | import Lax369799.ModalMuCalculus |
| 4 | import Mathlib.Order.FixedPoints |
| 5 | import Mathlib.Data.Set.Lattice |
| 6 | |
| 7 | /-! |
| 8 | --- |
| 9 | title: Logic on arbitrary transition systems |
| 10 | type: theorem |
| 11 | --- |
| 12 | Transition systems may have arbitrary state spaces. The usual MSO and |
| 13 | modal fixed-point semantics agree with the finite-system semantics on |
| 14 | finite presentations. The modal mu-calculus translates to MSO and is |
| 15 | bisimulation invariant on arbitrary state spaces. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax369799.UnrestrictedLogic |
| 19 | open UnrestrictedTransitionSystems |
| 20 | |
| 21 | def muEval {P : Type} (S : TransitionSystem P) : |
| 22 | {n : ℕ} → ModalMuCalculus.Formula P n → (Fin n → Set S.Vertex) → Set S.Vertex |
| 23 | | _, .top, _ => Set.univ |
| 24 | | _, .bot, _ => ∅ |
| 25 | | _, .proposition p, _ => {v | p ∈ S.valuation v} |
| 26 | | _, .negProposition p, _ => {v | p ∉ S.valuation v} |
| 27 | | _, .variable i, ρ => ρ i |
| 28 | | _, .conj φ ψ, ρ => muEval S φ ρ ∩ muEval S ψ ρ |
| 29 | | _, .disj φ ψ, ρ => muEval S φ ρ ∪ muEval S ψ ρ |
| 30 | | _, .diamond φ, ρ => {v | ∃ w, S.edge v w ∧ w ∈ muEval S φ ρ} |
| 31 | | _, .box φ, ρ => {v | ∀ w, S.edge v w → w ∈ muEval S φ ρ} |
| 32 | | _, .mu φ, ρ => sInf {X | muEval S φ (Fin.cases X ρ) ⊆ X} |
| 33 | | _, .nu φ, ρ => sSup {X | X ⊆ muEval S φ (Fin.cases X ρ)} |
| 34 | |
| 35 | def msoEval {P : Type} (S : TransitionSystem P) : |
| 36 | {m n : ℕ} → MonadicSecondOrder.Formula P m n → (Fin m → S.Vertex) → |
| 37 | (Fin n → Set S.Vertex) → Prop |
| 38 | | _, _, .equal x y, ρ, _ => ρ x = ρ y |
| 39 | | _, _, .initial x, ρ, _ => ρ x = S.initial |
| 40 | | _, _, .proposition p x, ρ, _ => p ∈ S.valuation (ρ x) |
| 41 | | _, _, .edge x y, ρ, _ => S.edge (ρ x) (ρ y) |
| 42 | | _, _, .member x X, ρ, σ => ρ x ∈ σ X |
| 43 | | _, _, .neg φ, ρ, σ => ¬ msoEval S φ ρ σ |
| 44 | | _, _, .disj φ ψ, ρ, σ => msoEval S φ ρ σ ∨ msoEval S ψ ρ σ |
| 45 | | _, _, .existsVertex φ, ρ, σ => ∃ v, msoEval S φ (Fin.cases v ρ) σ |
| 46 | | _, _, .existsSet φ, ρ, σ => ∃ X, msoEval S φ ρ (Fin.cases X σ) |
| 47 | |
| 48 | def MuModels {P : Type} (S : TransitionSystem P) (φ : ModalMuCalculus.Sentence P) : Prop := |
| 49 | S.initial ∈ muEval S φ Fin.elim0 |
| 50 | |
| 51 | def MSOModels {P : Type} (S : TransitionSystem P) (φ : MonadicSecondOrder.Sentence P) : Prop := |
| 52 | msoEval S φ Fin.elim0 Fin.elim0 |
| 53 | |
| 54 | def MuDefinable {P : Type} (L : Set (TransitionSystem P)) : Prop := |
| 55 | ∃ φ : ModalMuCalculus.Sentence P, ∀ S, S ∈ L ↔ MuModels S φ |
| 56 | |
| 57 | def MSODefinable {P : Type} (L : Set (TransitionSystem P)) : Prop := |
| 58 | ∃ φ : MonadicSecondOrder.Sentence P, ∀ S, S ∈ L ↔ MSOModels S φ |
| 59 | |
| 60 | def conjunction {P : Type} {m n : ℕ} |
| 61 | (φ ψ : MonadicSecondOrder.Formula P m n) : MonadicSecondOrder.Formula P m n := |
| 62 | .neg (.disj (.neg φ) (.neg ψ)) |
| 63 | |
| 64 | def implication {P : Type} {m n : ℕ} |
| 65 | (φ ψ : MonadicSecondOrder.Formula P m n) : MonadicSecondOrder.Formula P m n := |
| 66 | .disj (.neg φ) ψ |
| 67 | |
| 68 | def allVertex {P : Type} {m n : ℕ} |
| 69 | (φ : MonadicSecondOrder.Formula P (m + 1) n) : MonadicSecondOrder.Formula P m n := |
| 70 | .neg (.existsVertex (.neg φ)) |
| 71 | |
| 72 | def allSet {P : Type} {m n : ℕ} |
| 73 | (φ : MonadicSecondOrder.Formula P m (n + 1)) : MonadicSecondOrder.Formula P m n := |
| 74 | .neg (.existsSet (.neg φ)) |
| 75 | |
| 76 | /-- Translate satisfaction at a designated first-order variable. -/ |
| 77 | def translate {P : Type} : {n : ℕ} → ModalMuCalculus.Formula P n → |
| 78 | {m : ℕ} → Fin m → MonadicSecondOrder.Formula P m n |
| 79 | | _, .top, _, x => .equal x x |
| 80 | | _, .bot, _, x => .neg (.equal x x) |
| 81 | | _, .proposition p, _, x => .proposition p x |
| 82 | | _, .negProposition p, _, x => .neg (.proposition p x) |
| 83 | | _, .variable i, _, x => .member x i |
| 84 | | _, .conj φ ψ, _, x => conjunction (translate φ x) (translate ψ x) |
| 85 | | _, .disj φ ψ, _, x => .disj (translate φ x) (translate ψ x) |
| 86 | | _, .diamond φ, _, x => .existsVertex (conjunction (.edge x.succ 0) (translate φ 0)) |
| 87 | | _, .box φ, _, x => allVertex (implication (.edge x.succ 0) (translate φ 0)) |
| 88 | | _, .mu φ, _, x => allSet (implication |
| 89 | (allVertex (implication (translate φ 0) (.member 0 0))) (.member x 0)) |
| 90 | | _, .nu φ, _, x => .existsSet (conjunction (.member x 0) |
| 91 | (allVertex (implication (.member 0 0) (translate φ 0)))) |
| 92 | |
| 93 | def sentence {P : Type} (φ : ModalMuCalculus.Sentence P) : MonadicSecondOrder.Sentence P := |
| 94 | .existsVertex (conjunction (.initial 0) (translate φ 0)) |
| 95 | |
| 96 | axiom finite_mu {P : Type} (S : TransitionSystems.TransitionSystem P) {n : ℕ} |
| 97 | (φ : ModalMuCalculus.Formula P n) (ρ : Fin n → Set S.Vertex) : |
| 98 | muEval (ofFinite S) φ ρ = φ.eval S ρ |
| 99 | |
| 100 | axiom finite_mso {P : Type} (S : TransitionSystems.TransitionSystem P) {m n : ℕ} |
| 101 | (φ : MonadicSecondOrder.Formula P m n) (ρ : Fin m → S.Vertex) (σ : Fin n → Set S.Vertex) : |
| 102 | msoEval (ofFinite S) φ ρ σ ↔ φ.eval S ρ σ |
| 103 | |
| 104 | axiom eval_monotone {P : Type} (S : TransitionSystem P) {n : ℕ} |
| 105 | (φ : ModalMuCalculus.Formula P n) (ρ σ : Fin n → Set S.Vertex) |
| 106 | (h : ∀ i, ρ i ⊆ σ i) : muEval S φ ρ ⊆ muEval S φ σ |
| 107 | |
| 108 | axiom translate_correct {P : Type} (S : TransitionSystem P) {n : ℕ} |
| 109 | (φ : ModalMuCalculus.Formula P n) {m : ℕ} (x : Fin m) |
| 110 | (ρ : Fin m → S.Vertex) (σ : Fin n → Set S.Vertex) : |
| 111 | msoEval S (translate φ x) ρ σ ↔ ρ x ∈ muEval S φ σ |
| 112 | |
| 113 | axiom mu_to_mso {P : Type} (φ : ModalMuCalculus.Sentence P) : |
| 114 | ∃ ψ : MonadicSecondOrder.Sentence P, ∀ S : TransitionSystem P, |
| 115 | MuModels S φ ↔ MSOModels S ψ |
| 116 | |
| 117 | axiom mu_bisimulation_invariant {P : Type} (φ : ModalMuCalculus.Sentence P) : |
| 118 | BisimulationInvariant {S | MuModels S φ} |
| 119 | |
| 120 | axiom mu_definable_implies_mso_invariant {P : Type} (L : Set (TransitionSystem P)) |
| 121 | (hL : MuDefinable L) : MSODefinable L ∧ BisimulationInvariant L |
| 122 | |
| 123 | axiom finite_bisimulation {P : Type} (S T : TransitionSystems.TransitionSystem P) |
| 124 | (R : S.Vertex → T.Vertex → Prop) : |
| 125 | Bisimulation (ofFinite S) (ofFinite T) R ↔ TransitionSystems.Bisimulation S T R |
| 126 | |
| 127 | axiom finite_mu_models {P : Type} (S : TransitionSystems.TransitionSystem P) |
| 128 | (φ : ModalMuCalculus.Sentence P) : MuModels (ofFinite S) φ ↔ ModalMuCalculus.Models S φ |
| 129 | |
| 130 | axiom finite_mso_models {P : Type} (S : TransitionSystems.TransitionSystem P) |
| 131 | (φ : MonadicSecondOrder.Sentence P) : MSOModels (ofFinite S) φ ↔ MonadicSecondOrder.Models S φ |
| 132 | |
| 133 | end Lax369799.UnrestrictedLogic |
| 134 | |
| 135 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments