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

Syntactic set-algebras and rankwise finiteness

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

    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
    8 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.SyntacticOrder
    2import Lax369799.Resolutions
    3
    4/-!
    5---
    6title: Syntactic set-algebras and rankwise finiteness
    7type: theorem
    8---
    9Recognition below is conditional on the original set-algebra interface.
    10Existence uses expanded continuity in ExpandedSyntacticAlgebra instead.
    11The accepting set is an upward-closed meet filter and recognises the language. Small-profile
    12equivalence has finite index, giving rankwise finiteness when
    13the language is recognised by a rankwise-finite regular-tree algebra.
    14These are the principal results of Sections 4.2–4.3.
    15-/
    16
    17namespace Lax369799.SyntacticAlgebraTheorems
    18open 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
    26axiom 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
    34axiom 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
    41axiom syntactic_rankwise_finite {A : RankedSet} (L : Language A)
    42 (hL : RegularTreeRecognizable L) : RankwiseFinite (SyntacticCarrier L)
    43
    44end Lax369799.SyntacticAlgebraTheorems
    45
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…