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

Continuity through expanded representatives

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

    Expand every algebra-valued vertex into a representative before resolving nondeterminism. All substitutions retain unreachable vertices until the final yield observation. Acceptance of these expanded resolutions, also in every surrounding context, is independent of the representatives. This is a contextual continuity law; it does not identify the yields of an atomic algebra-valued pattern with those of its expansion.

    Concept map
    46 concepts
    100%
    Algebraic decomposition with boundary dataAlgebras and recognitionDeterministic elements and the earlierreplacement propertyBounded profiles refine finite contextualequivalenceContext decomposition with hole boundarydataRelabelling and deterministic contextsubstitutionFinite resolution approximation in a contextSmallification preserving identitycontinuationsDeterministic normal forms with identitycontinuationsUnary continuations of deterministiccontextsContinuity through expanded representativesPlanted normal contexts and deterministicwitnessesYield acceptance of finite presentationsContexts over finite presentationsContextual preorders on finite presentationsFinite yield approximation of contextualacceptance and orderMorphisms of unpruned finite presentationsFinite presentations without reachabilitypruningSmall profiles of finite presentationsFinite approximation of a flatteningresolutionNormal forms retaining split-variableresolutionsContextual quotient algebras of finitepresentationsYield continuity for finite-presentationcontextsFinite sums are contextual meetsFlattening and contextsFlattening, resolutions, and yield congruenceFinite support for initial observationsMorphisms, unfoldings, and yieldsBounded profiles in root-free substitutionpatternsBounded optimal flatten-resolutionsLocally surjective maps of finitepresentationsResolution values of finite presentationsTransfer of resolutions through boundedprofilesRanked sets, set-systems, and systemsRenaming variables in systems andresolutionsCompression of the variables offlatten-resolutionsFinite families of split-variable resolutionsResolutions and bounded profilesRoot entries in substituted presentationsFinite support for root observationsThe earlier continuity-bearing set-algebrainterfaceSyntactic set-algebras and rankwise finitenessYield-syntactic order and quotientEvaluation and variable renaming inregular-tree algebrasCompression of variable maps by finiteobservationsContinuity of yields in a context
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.FiniteAcceptance
    2import Lax369799.FiniteContinuityOrder
    3import Lax369799.FiniteYieldMeets
    4
    5/-!
    6---
    7title: Continuity through expanded representatives
    8type: theorem
    9---
    10Expand every algebra-valued vertex into a representative before resolving
    11nondeterminism. All substitutions retain unreachable vertices until the
    12final yield observation. Acceptance of these expanded resolutions, also
    13in every surrounding context, is independent of the representatives.
    14This is a contextual continuity law; it does not identify the yields of
    15an atomic algebra-valued pattern with those of its expansion.
    16-/
    17namespace Lax369799.ExpandedContinuity
    18open RankedSystems (RankedSet SetSystem System)
    19open FinitePresentations FiniteContexts FiniteContextualOrder FiniteSyntacticAlgebra
    20open FiniteAcceptance
    21
    22abbrev Representatives {A : RankedSet} (L : Algebras.Language A) {n : ℕ}
    23 (P : FiniteSystem (Carrier (Accepting L)) n) :=
    24 ∀ v : P.Vertex, FiniteSystem A (P.graph.label v).1
    25
    26def Represents {A : RankedSet} (L : Algebras.Language A) {n : ℕ}
    27 (P : FiniteSystem (Carrier (Accepting L)) n) (q : Representatives L P) : Prop :=
    28 ∀ v, quotientMap (Accepting L) _ (q v) = (P.graph.label v).2
    29
    30noncomputable def expansion {A : RankedSet} (L : Algebras.Language A) {n : ℕ}
    31 (P : FiniteSystem (Carrier (Accepting L)) n) (q : Representatives L P) : FiniteSystem A n :=
    32 flatten (withLabels P q)
    33
    34def Admissible {A : RankedSet} (L : Algebras.Language A) (T : SetSystem A 0) : Prop :=
    35 ∃ U : System A 0, U ∈ L ∧ (T = U.val ∨ T = RankedSystems.plant U.val)
    36
    37def ResolvesIn {A : RankedSet} (L : Algebras.Language A) {n : ℕ}
    38 (P : FiniteSystem (Carrier (Accepting L)) n) (q : Representatives L P)
    39 (C : Context A n 0) (T : SetSystem A 0) : Prop :=
    40 Morphisms.Yield (RankedSystems.trim (plug C (expansion L P q)).graph) T
    41
    42axiom evaluation {A : RankedSet} (L : Algebras.Language A)
    43 (E : Algebra (Carrier (Accepting L)))
    44 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    45 E.eval n (relabel (quotientMap (Accepting L)) S) = quotientMap (Accepting L) n (flatten S))
    46 {n : ℕ} (P : FiniteSystem (Carrier (Accepting L)) n)
    47 (q : Representatives L P) (hq : Represents L P q) :
    48 E.eval n P = quotientMap (Accepting L) n (expansion L P q)
    49
    50axiom closed_continuity {A : RankedSet} (L : Algebras.Language A)
    51 (E : Algebra (Carrier (Accepting L)))
    52 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    53 E.eval n (relabel (quotientMap (Accepting L)) S) = quotientMap (Accepting L) n (flatten S))
    54 (P : FiniteSystem (Carrier (Accepting L)) 0)
    55 (q : Representatives L P) (hq : Represents L P q) :
    56 AcceptingClass (Accepting L) (E.eval 0 P) ↔
    57 ∀ T, Morphisms.Yield (RankedSystems.trim (expansion L P q).graph) T → Admissible L T
    58
    59axiom contextual_continuity {A : RankedSet} (L : Algebras.Language A)
    60 (E : Algebra (Carrier (Accepting L)))
    61 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    62 E.eval n (relabel (quotientMap (Accepting L)) S) = quotientMap (Accepting L) n (flatten S))
    63 {n : ℕ} (P : FiniteSystem (Carrier (Accepting L)) n)
    64 (q : Representatives L P) (hq : Represents L P q) (R : FiniteSystem A n) :
    65 ClassBelow (Accepting L) (quotientMap (Accepting L) n R) (E.eval n P) ↔
    66 ∀ C : Context A n 0, Accepting L (plug C R) →
    67 ∀ T, ResolvesIn L P q C T → Admissible L T
    68
    69axiom representative_independence {A : RankedSet} (L : Algebras.Language A)
    70 (E : Algebra (Carrier (Accepting L)))
    71 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    72 E.eval n (relabel (quotientMap (Accepting L)) S) = quotientMap (Accepting L) n (flatten S))
    73 {n : ℕ} (P : FiniteSystem (Carrier (Accepting L)) n)
    74 (q r : Representatives L P) (hq : Represents L P q) (hr : Represents L P r)
    75 (C : Context A n 0) :
    76 (∀ T, ResolvesIn L P q C T → Admissible L T) ↔
    77 (∀ T, ResolvesIn L P r C T → Admissible L T)
    78
    79axiom finite_approximation {A : RankedSet} (L : Algebras.Language A)
    80 (E : Algebra (Carrier (Accepting L)))
    81 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    82 E.eval n (relabel (quotientMap (Accepting L)) S) = quotientMap (Accepting L) n (flatten S))
    83 {n : ℕ} (P : FiniteSystem (Carrier (Accepting L)) n)
    84 (q : Representatives L P) (hq : Represents L P q) (R : FiniteSystem A n) :
    85 ClassBelow (Accepting L) (quotientMap (Accepting L) n R) (E.eval n P) ↔
    86 ∀ (m : ℕ) (F : Fin m → SetSystem A n),
    87 (∀ i, Morphisms.Yield (RankedSystems.trim (expansion L P q).graph) (F i)) →
    88 ClassBelow (Accepting L) (quotientMap (Accepting L) n R)
    89 (quotientMap (Accepting L) n (ofSetSystem (YieldContinuity.finiteSum F)))
    90
    91axiom yield_lower_bound {A : RankedSet} (L : Algebras.Language A)
    92 (E : Algebra (Carrier (Accepting L)))
    93 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    94 E.eval n (relabel (quotientMap (Accepting L)) S) = quotientMap (Accepting L) n (flatten S))
    95 {n : ℕ} (P : FiniteSystem (Carrier (Accepting L)) n)
    96 (q : Representatives L P) (hq : Represents L P q) (R : FiniteSystem A n) :
    97 ClassBelow (Accepting L) (quotientMap (Accepting L) n R) (E.eval n P) ↔
    98 ∀ T : SetSystem A n,
    99 Morphisms.Yield (RankedSystems.trim (expansion L P q).graph) T →
    100 ClassBelow (Accepting L) (quotientMap (Accepting L) n R)
    101 (quotientMap (Accepting L) n (ofSetSystem T))
    102
    103end Lax369799.ExpandedContinuity
    104
    Show ProofShow ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…