Syntactic set-algebras and rankwise finiteness
Lax369799.SyntacticAlgebraTheorems · concepts/Lax369799/SyntacticAlgebraTheorems.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Recognition below is conditional on the original set-algebra interface. Existence uses expanded continuity in ExpandedSyntacticAlgebra instead. The accepting set is an upward-closed meet filter and recognises the language. Small-profile equivalence has finite index, giving rankwise finiteness when the language is recognised by a rankwise-finite regular-tree algebra. These are the principal results of Sections 4.2–4.3.
Concept map
Evidence
This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.
1 small_profile_finite proven
2 syntactic_rankwise_finite proven
3 syntactic_recognition proven
Lean source view on GitHub
| 1 | import Lax369799.SyntacticOrder |
| 2 | import Lax369799.Resolutions |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Syntactic set-algebras and rankwise finiteness |
| 7 | type: theorem |
| 8 | --- |
| 9 | Recognition below is conditional on the original set-algebra interface. |
| 10 | Existence uses expanded continuity in ExpandedSyntacticAlgebra instead. |
| 11 | The accepting set is an upward-closed meet filter and recognises the language. Small-profile |
| 12 | equivalence has finite index, giving rankwise finiteness when |
| 13 | the language is recognised by a rankwise-finite regular-tree algebra. |
| 14 | These are the principal results of Sections 4.2–4.3. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax369799.SyntacticAlgebraTheorems |
| 18 | open RankedSystems Morphisms Flattening Algebras SetAlgebras SyntacticOrder Resolutions |
| 19 | |
| 20 | -- The revised contextual congruence is stated and proved for all finite |
| 21 | -- presentations in FiniteContextualOrder.contextual_congruence. |
| 22 | |
| 23 | -- Existence with expanded continuity is stated in ExpandedSyntacticAlgebra. |
| 24 | -- The original atomic-yield continuity is incompatible with this quotient. |
| 25 | |
| 26 | axiom syntactic_recognition {A : RankedSet} (L : Language A) |
| 27 | (hL : UnfoldInvariantLanguage L) (E : SyntacticAlgebra L) : |
| 28 | ∃ F : Set (SyntacticCarrier L 0), |
| 29 | (∀ S, syntacticMap L 0 S ∈ F ↔ Accepting L S) ∧ |
| 30 | (∀ T : System A 0, syntacticMap L 0 T.val ∈ F ↔ T ∈ L) ∧ |
| 31 | (∀ a b, a ∈ F → Below E.algebra a b → b ∈ F) ∧ |
| 32 | (∀ a b, a ∈ F → b ∈ F → meet E.algebra a b ∈ F) |
| 33 | |
| 34 | axiom small_profile_finite {A B : RankedSet} (hB : RankwiseFinite B) |
| 35 | (ρ : ∀ n, System A n → B n) (n : ℕ) : |
| 36 | Finite (Quot (@SmallProfileEquivalent A B ρ n)) |
| 37 | |
| 38 | -- SmallProfileRefinement.refines uses the revised small-map bound and |
| 39 | -- the unpruned syntactic order of Definition 68. |
| 40 | |
| 41 | axiom syntactic_rankwise_finite {A : RankedSet} (L : Language A) |
| 42 | (hL : RegularTreeRecognizable L) : RankwiseFinite (SyntacticCarrier L) |
| 43 | |
| 44 | end Lax369799.SyntacticAlgebraTheorems |
| 45 |
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments