Computable bounds on the syntactic nullary and unary sorts
Lax369799.QuantitativeProfiles · concepts/Lax369799/QuantitativeProfiles.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The number of possible small profile entries is bounded by a finite sum. Initial and root profile codes give a bound on each contextual quotient without computing equivalence of contexts. This is the quantitative step used in the effectivity argument after Theorem 2.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.QuantitativeRecognition |
| 2 | import Lax369799.FiniteContextualOrder |
| 3 | import Lax369799.FiniteAcceptance |
| 4 | import Mathlib.Algebra.BigOperators.Group.Finset.Basic |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Computable bounds on the syntactic nullary and unary sorts |
| 9 | type: theorem |
| 10 | --- |
| 11 | The number of possible small profile entries is bounded by a finite sum. |
| 12 | Initial and root profile codes give a bound on each contextual quotient |
| 13 | without computing equivalence of contexts. This is the quantitative |
| 14 | step used in the effectivity argument after Theorem 2. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax369799.QuantitativeProfiles |
| 18 | |
| 19 | def entryBound (f : ℕ → ℕ) (bound n : ℕ) : ℕ := |
| 20 | ∑ k ∈ Finset.range (n*bound+1),f k*n^k |
| 21 | |
| 22 | def quotientBound (f : ℕ → ℕ) (n : ℕ) : ℕ := |
| 23 | 2 ^ (2*entryBound f (f 1+1) n) |
| 24 | |
| 25 | open RankedSystems Algebras QuantitativeRecognition |
| 26 | |
| 27 | axiom syntactic_bound {A : RankedSet} (L : Language A) (hL : UnfoldInvariantLanguage L) |
| 28 | (f : ℕ → ℕ) (hrec : Bound f L) (n : ℕ) : |
| 29 | Nat.card (FiniteContextualOrder.Carrier (FiniteAcceptance.Accepting L) n) ≤ quotientBound f n |
| 30 | |
| 31 | end Lax369799.QuantitativeProfiles |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments