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

Monadic second-order logic on transition systems

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

definition

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

    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
    3 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Lax369799.TransitionSystems
    2
    3/-!
    4---
    5title: Monadic second-order logic on transition systems
    6type: definition
    7---
    8MSO has vertex variables, set variables, equality, the initial-vertex
    9predicate, proposition predicates, the edge relation, membership, Boolean
    10connectives, and quantification over vertices and arbitrary vertex sets.
    11The two natural-number indices count the free variables of each kind;
    12a sentence has no free variables. Semantics is given by the usual Tarski
    13clauses (Section 6.2).
    14-/
    15
    16namespace Lax369799.MonadicSecondOrder
    17open TransitionSystems
    18
    19inductive 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
    30def 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
    43abbrev Sentence (P : Type) := Formula P 0 0
    44
    45def Models {P : Type} (S : TransitionSystem P) (φ : Sentence P) : Prop :=
    46 φ.eval S Fin.elim0 Fin.elim0
    47
    48def Definable {P : Type} (L : Set (TransitionSystem P)) : Prop :=
    49 ∃ φ : Sentence P, ∀ S, S ∈ L ↔ Models S φ
    50
    51end Lax369799.MonadicSecondOrder
    52

    Discussion

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

    Loading discussion…