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

Pure second-order syntax

Lax369799.SetLogic · concepts/Lax369799/SetLogic.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

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

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

    1 empty_iff proven

    2 singleton_iff proven

    Lean source view on GitHub

    1import Lax369799.MonadicSecondOrder
    2
    3/-!
    4---
    5title: Pure second-order syntax
    6type: theorem
    7---
    8The set-only presentation of MSO uses inclusion, initial membership,
    9universal proposition tests, and existential edge tests. Bound variables
    10are represented by a new option value. Empty sets and singletons are
    11definable using inclusion and quantification over sets, as in Section 6.2.
    12-/
    13namespace Lax369799.SetLogic
    14open TransitionSystems
    15
    16inductive 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
    25def 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
    35def Formula.conj {P X : Type} (φ ψ : Formula P X) : Formula P X :=
    36 .neg (.disj (.neg φ) (.neg ψ))
    37
    38def Formula.empty {P X : Type} (x : X) : Formula P X :=
    39 .neg (.existsSet (.neg (.subset (.some x) .none)))
    40
    41def 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
    46axiom empty_iff {P X : Type} (S : TransitionSystem P) (σ : X → Set S.Vertex) (x : X) :
    47 (Formula.empty x).eval S σ ↔ σ x = ∅
    48
    49axiom singleton_iff {P X : Type} (S : TransitionSystem P) (σ : X → Set S.Vertex) (x : X) :
    50 (Formula.singleton x).eval S σ ↔ ∃ v, σ x = {v}
    51
    52end Lax369799.SetLogic
    53
    Show ProofShow Proof

    Discussion

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

    Loading discussion…