While this submission is a draft, it cannot be used by other submissions.

Logic on arbitrary transition systems

Lax369799.UnrestrictedLogic · concepts/Lax369799/UnrestrictedLogic.lean · lax-369799

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    6 concepts; 4 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 10 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.UnrestrictedTransitionSystems
    2import Lax369799.MonadicSecondOrder
    3import Lax369799.ModalMuCalculus
    4import Mathlib.Order.FixedPoints
    5import Mathlib.Data.Set.Lattice
    6
    7/-!
    8---
    9title: Logic on arbitrary transition systems
    10type: theorem
    11---
    12Transition systems may have arbitrary state spaces. The usual MSO and
    13modal fixed-point semantics agree with the finite-system semantics on
    14finite presentations. The modal mu-calculus translates to MSO and is
    15bisimulation invariant on arbitrary state spaces.
    16-/
    17
    18namespace Lax369799.UnrestrictedLogic
    19open UnrestrictedTransitionSystems
    20
    21def 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
    35def 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
    48def MuModels {P : Type} (S : TransitionSystem P) (φ : ModalMuCalculus.Sentence P) : Prop :=
    49 S.initial ∈ muEval S φ Fin.elim0
    50
    51def MSOModels {P : Type} (S : TransitionSystem P) (φ : MonadicSecondOrder.Sentence P) : Prop :=
    52 msoEval S φ Fin.elim0 Fin.elim0
    53
    54def MuDefinable {P : Type} (L : Set (TransitionSystem P)) : Prop :=
    55 ∃ φ : ModalMuCalculus.Sentence P, ∀ S, S ∈ L ↔ MuModels S φ
    56
    57def MSODefinable {P : Type} (L : Set (TransitionSystem P)) : Prop :=
    58 ∃ φ : MonadicSecondOrder.Sentence P, ∀ S, S ∈ L ↔ MSOModels S φ
    59
    60def conjunction {P : Type} {m n : ℕ}
    61 (φ ψ : MonadicSecondOrder.Formula P m n) : MonadicSecondOrder.Formula P m n :=
    62 .neg (.disj (.neg φ) (.neg ψ))
    63
    64def implication {P : Type} {m n : ℕ}
    65 (φ ψ : MonadicSecondOrder.Formula P m n) : MonadicSecondOrder.Formula P m n :=
    66 .disj (.neg φ) ψ
    67
    68def allVertex {P : Type} {m n : ℕ}
    69 (φ : MonadicSecondOrder.Formula P (m + 1) n) : MonadicSecondOrder.Formula P m n :=
    70 .neg (.existsVertex (.neg φ))
    71
    72def 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. -/
    77def 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
    93def sentence {P : Type} (φ : ModalMuCalculus.Sentence P) : MonadicSecondOrder.Sentence P :=
    94 .existsVertex (conjunction (.initial 0) (translate φ 0))
    95
    96axiom 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
    100axiom 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
    104axiom 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
    108axiom 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
    113axiom mu_to_mso {P : Type} (φ : ModalMuCalculus.Sentence P) :
    114 ∃ ψ : MonadicSecondOrder.Sentence P, ∀ S : TransitionSystem P,
    115 MuModels S φ ↔ MSOModels S ψ
    116
    117axiom mu_bisimulation_invariant {P : Type} (φ : ModalMuCalculus.Sentence P) :
    118 BisimulationInvariant {S | MuModels S φ}
    119
    120axiom mu_definable_implies_mso_invariant {P : Type} (L : Set (TransitionSystem P))
    121 (hL : MuDefinable L) : MSODefinable L ∧ BisimulationInvariant L
    122
    123axiom 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
    127axiom finite_mu_models {P : Type} (S : TransitionSystems.TransitionSystem P)
    128 (φ : ModalMuCalculus.Sentence P) : MuModels (ofFinite S) φ ↔ ModalMuCalculus.Models S φ
    129
    130axiom finite_mso_models {P : Type} (S : TransitionSystems.TransitionSystem P)
    131 (φ : MonadicSecondOrder.Sentence P) : MSOModels (ofFinite S) φ ↔ MonadicSecondOrder.Models S φ
    132
    133end Lax369799.UnrestrictedLogic
    134
    135
    Show ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…