Monadic second-order logic on transition systems
Lax369799.MonadicSecondOrder · concepts/Lax369799/MonadicSecondOrder.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
MSO has vertex variables, set variables, equality, the initial-vertex predicate, proposition predicates, the edge relation, membership, Boolean connectives, and quantification over vertices and arbitrary vertex sets. The two natural-number indices count the free variables of each kind; a sentence has no free variables. Semantics is given by the usual Tarski clauses (Section 6.2).
Concept map
Lean source view on GitHub
| 1 | import Lax369799.TransitionSystems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Monadic second-order logic on transition systems |
| 6 | type: definition |
| 7 | --- |
| 8 | MSO has vertex variables, set variables, equality, the initial-vertex |
| 9 | predicate, proposition predicates, the edge relation, membership, Boolean |
| 10 | connectives, and quantification over vertices and arbitrary vertex sets. |
| 11 | The two natural-number indices count the free variables of each kind; |
| 12 | a sentence has no free variables. Semantics is given by the usual Tarski |
| 13 | clauses (Section 6.2). |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.MonadicSecondOrder |
| 17 | open TransitionSystems |
| 18 | |
| 19 | inductive Formula (P : Type) : ℕ → ℕ → Type |
| 20 | | equal {m n} : Fin m → Fin m → Formula P m n |
| 21 | | initial {m n} : Fin m → Formula P m n |
| 22 | | proposition {m n} : P → Fin m → Formula P m n |
| 23 | | edge {m n} : Fin m → Fin m → Formula P m n |
| 24 | | member {m n} : Fin m → Fin n → Formula P m n |
| 25 | | neg {m n} : Formula P m n → Formula P m n |
| 26 | | disj {m n} : Formula P m n → Formula P m n → Formula P m n |
| 27 | | existsVertex {m n} : Formula P (m + 1) n → Formula P m n |
| 28 | | existsSet {m n} : Formula P m (n + 1) → Formula P m n |
| 29 | |
| 30 | def Formula.eval {P : Type} (S : TransitionSystem P) : |
| 31 | {m n : ℕ} → Formula P m n → (Fin m → S.Vertex) → |
| 32 | (Fin n → Set S.Vertex) → Prop |
| 33 | | _, _, .equal x y, ρ, _ => ρ x = ρ y |
| 34 | | _, _, .initial x, ρ, _ => ρ x = S.initial |
| 35 | | _, _, .proposition p x, ρ, _ => p ∈ S.valuation (ρ x) |
| 36 | | _, _, .edge x y, ρ, _ => S.edge (ρ x) (ρ y) |
| 37 | | _, _, .member x X, ρ, σ => ρ x ∈ σ X |
| 38 | | _, _, .neg φ, ρ, σ => ¬ φ.eval S ρ σ |
| 39 | | _, _, .disj φ ψ, ρ, σ => φ.eval S ρ σ ∨ ψ.eval S ρ σ |
| 40 | | _, _, .existsVertex φ, ρ, σ => ∃ v, φ.eval S (Fin.cases v ρ) σ |
| 41 | | _, _, .existsSet φ, ρ, σ => ∃ X, φ.eval S ρ (Fin.cases X σ) |
| 42 | |
| 43 | abbrev Sentence (P : Type) := Formula P 0 0 |
| 44 | |
| 45 | def Models {P : Type} (S : TransitionSystem P) (φ : Sentence P) : Prop := |
| 46 | φ.eval S Fin.elim0 Fin.elim0 |
| 47 | |
| 48 | def Definable {P : Type} (L : Set (TransitionSystem P)) : Prop := |
| 49 | ∃ φ : Sentence P, ∀ S, S ∈ L ↔ Models S φ |
| 50 | |
| 51 | end Lax369799.MonadicSecondOrder |
| 52 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments