Pure second-order syntax
Lax369799.SetLogic · concepts/Lax369799/SetLogic.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The set-only presentation of MSO uses inclusion, initial membership, universal proposition tests, and existential edge tests. Bound variables are represented by a new option value. Empty sets and singletons are definable using inclusion and quantification over sets, as in Section 6.2.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.MonadicSecondOrder |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Pure second-order syntax |
| 6 | type: theorem |
| 7 | --- |
| 8 | The set-only presentation of MSO uses inclusion, initial membership, |
| 9 | universal proposition tests, and existential edge tests. Bound variables |
| 10 | are represented by a new option value. Empty sets and singletons are |
| 11 | definable using inclusion and quantification over sets, as in Section 6.2. |
| 12 | -/ |
| 13 | namespace Lax369799.SetLogic |
| 14 | open TransitionSystems |
| 15 | |
| 16 | inductive Formula (P : Type) : Type → Type 1 |
| 17 | | subset {X} : X → X → Formula P X |
| 18 | | initial {X} : X → Formula P X |
| 19 | | proposition {X} : P → X → Formula P X |
| 20 | | edge {X} : X → X → Formula P X |
| 21 | | neg {X} : Formula P X → Formula P X |
| 22 | | disj {X} : Formula P X → Formula P X → Formula P X |
| 23 | | existsSet {X} : Formula P (Option X) → Formula P X |
| 24 | |
| 25 | def Formula.eval {P : Type} (S : TransitionSystem P) : |
| 26 | {X : Type} → Formula P X → (X → Set S.Vertex) → Prop |
| 27 | | _, .subset x y, σ => σ x ⊆ σ y |
| 28 | | _, .initial x, σ => S.initial ∈ σ x |
| 29 | | _, .proposition p x, σ => ∀ v ∈ σ x, p ∈ S.valuation v |
| 30 | | _, .edge x y, σ => ∃ v ∈ σ x, ∃ w ∈ σ y, S.edge v w |
| 31 | | _, .neg φ, σ => ¬ φ.eval S σ |
| 32 | | _, .disj φ ψ, σ => φ.eval S σ ∨ ψ.eval S σ |
| 33 | | _, .existsSet φ, σ => ∃ U, φ.eval S (Option.elim · U σ) |
| 34 | |
| 35 | def Formula.conj {P X : Type} (φ ψ : Formula P X) : Formula P X := |
| 36 | .neg (.disj (.neg φ) (.neg ψ)) |
| 37 | |
| 38 | def Formula.empty {P X : Type} (x : X) : Formula P X := |
| 39 | .neg (.existsSet (.neg (.subset (.some x) .none))) |
| 40 | |
| 41 | def Formula.singleton {P X : Type} (x : X) : Formula P X := |
| 42 | .conj (.neg (.empty x)) (.neg (.existsSet |
| 43 | (.conj (.subset .none (.some x)) |
| 44 | (.conj (.neg (.empty .none)) (.neg (.subset (.some x) .none)))))) |
| 45 | |
| 46 | axiom empty_iff {P X : Type} (S : TransitionSystem P) (σ : X → Set S.Vertex) (x : X) : |
| 47 | (Formula.empty x).eval S σ ↔ σ x = ∅ |
| 48 | |
| 49 | axiom singleton_iff {P X : Type} (S : TransitionSystem P) (σ : X → Set S.Vertex) (x : X) : |
| 50 | (Formula.singleton x).eval S σ ↔ ∃ v, σ x = {v} |
| 51 | |
| 52 | end Lax369799.SetLogic |
| 53 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments