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

Computable bounds for MSO recognizing algebras

Lax369799.QuantitativeRecognition · concepts/Lax369799/QuantitativeRecognition.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 effectivity argument starts with a syntax-computed bound for every sort of an MSO recognizing algebra. Products multiply bounds, nonempty powersets exponentiate them, and atomic path summaries have explicit finite cardinalities.

    Concept map
    11 concepts; 5 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Mathlib.SetTheory.Cardinal.NatCard
    2import Lax369799.MSORecognition
    3import Lax369799.SetLogicTranslation
    4
    5/-!
    6---
    7title: Computable bounds for MSO recognizing algebras
    8type: theorem
    9---
    10The effectivity argument starts with a syntax-computed bound for every
    11sort of an MSO recognizing algebra. Products multiply bounds, nonempty
    12powersets exponentiate them, and atomic path summaries have explicit
    13finite cardinalities.
    14-/
    15
    16namespace Lax369799.QuantitativeRecognition
    17open RankedSystems Algebras SetLogic
    18
    19def Bound (f : ℕ → ℕ) {A : RankedSet} (L : Language A) : Prop :=
    20 ∃ (B : RankedSet) (E : Algebra B) (η : RankedMap A B) (F : Set (B 0)),
    21 RankwiseFinite B ∧ Recognizes E η F L ∧ ∀ k,Nat.card (B k) ≤ f k
    22
    23def logicBound {P : Type} : {X : Type} → Formula P X → ℕ → ℕ
    24 | _, .subset _ _, k => 2 ^ (4*(k+1))
    25 | _, .initial _, k => 2 ^ (4*(k+1))
    26 | _, .proposition _ _, k => 2 ^ (4*(k+1))
    27 | _, .edge _ _, k => 2 ^ (4*(k+1))
    28 | _, .neg φ, k => logicBound φ k
    29 | _, .disj φ ψ, k => logicBound φ k * logicBound ψ k
    30 | _, .existsSet φ, k => 2 ^ logicBound φ k
    31
    32def msoBound {P : Type} (φ : MonadicSecondOrder.Sentence P) : ℕ → ℕ :=
    33 logicBound (SetLogicTranslation.translate φ (X := Empty) Fin.elim0 Fin.elim0)
    34
    35axiom mso_bound {P : Type} [Finite P] (φ : MonadicSecondOrder.Sentence P) :
    36 Bound (msoBound φ) {S | MonadicSecondOrder.Models (TransitionEncoding.decode S) φ}
    37
    38end Lax369799.QuantitativeRecognition
    Show Proof

    Discussion

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

    Loading discussion…