Computable bounds for MSO recognizing algebras
Lax369799.QuantitativeRecognition · concepts/Lax369799/QuantitativeRecognition.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Lean source view on GitHub
| 1 | import Mathlib.SetTheory.Cardinal.NatCard |
| 2 | import Lax369799.MSORecognition |
| 3 | import Lax369799.SetLogicTranslation |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Computable bounds for MSO recognizing algebras |
| 8 | type: theorem |
| 9 | --- |
| 10 | The effectivity argument starts with a syntax-computed bound for every |
| 11 | sort of an MSO recognizing algebra. Products multiply bounds, nonempty |
| 12 | powersets exponentiate them, and atomic path summaries have explicit |
| 13 | finite cardinalities. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.QuantitativeRecognition |
| 17 | open RankedSystems Algebras SetLogic |
| 18 | |
| 19 | def 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 | |
| 23 | def 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 | |
| 32 | def msoBound {P : Type} (φ : MonadicSecondOrder.Sentence P) : ℕ → ℕ := |
| 33 | logicBound (SetLogicTranslation.translate φ (X := Empty) Fin.elim0 Fin.elim0) |
| 34 | |
| 35 | axiom mso_bound {P : Type} [Finite P] (φ : MonadicSecondOrder.Sentence P) : |
| 36 | Bound (msoBound φ) {S | MonadicSecondOrder.Models (TransitionEncoding.decode S) φ} |
| 37 | |
| 38 | end Lax369799.QuantitativeRecognition |
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments