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

Extremal accepted situations in the syntactic algebra

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

    Sections 5.1–5.2 minimize the element in the hole as well as its context pieces. In the syntactic algebra, planting allows context pieces to be recorded by their unary values, a root flag, and self-loop directions. An extremal situation is a componentwise minimal accepted pair of these data and an element. This is the planted form of Definition 85. Unlike extremality of context data for a fixed element, it also forces every accepted decrease of that element to be equal to it.

    Concept map
    59 concepts; 6 descendants hidden
    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 identitycontinuationsUnary normal form of deterministic elementsDeterministic normal forms with identitycontinuationsUnary continuations of deterministiccontextsContinuity through expanded representativesSyntactic algebras with expanded continuityPlanted normal contexts and deterministicwitnessesExtremal accepted situations in the syntacticalgebraUnary types selected by extremal refinementYield acceptance of finite presentationsAutomaton property of the unprunedsyntactic algebraContexts over finite presentationsContextual preorders on finite presentationsFinite yield approximation of contextualacceptance and orderContext decomposition without pruningExtremal unary data for finite presentationsFinite iteration of context-preserving localchoicesMorphisms of unpruned finite presentationsUnary normal forms without pruningOrdered syntactic algebras of finitepresentationsFinite presentations without reachabilitypruningSmall profiles of finite presentationsFinite approximation of a flatteningresolutionNormal forms retaining split-variableresolutionsContextual quotient algebras of finitepresentationsSimultaneous deterministic replacements infinite presentationsYield 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-algebrainterfaceExtremal witnesses with separate rootedcomponentsSyntactic set-algebras and rankwise finitenessYield-syntactic order and quotientEvaluation and variable renaming inregular-tree algebrasVariable exits of unary systemsCompression of variable maps by finiteobservationsContinuity of yields in a context
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.ExpandedSyntacticAlgebra
    2import Lax369799.ExtremalUnaryTypes
    3import Lax369799.FiniteLocalReplacement
    4
    5/-!
    6---
    7title: Extremal accepted situations in the syntactic algebra
    8type: theorem
    9---
    10Sections 5.1–5.2 minimize the element in the hole as well as its context
    11pieces. In the syntactic algebra, planting allows context pieces to be
    12recorded by their unary values, a root flag, and self-loop directions.
    13An extremal situation is a componentwise minimal accepted pair of these
    14data and an element. This is the planted form of Definition 85.
    15Unlike extremality of context data for a fixed element, it also forces
    16every accepted decrease of that element to be equal to it.
    17-/
    18
    19namespace Lax369799.ExtremalSituations
    20open RankedSystems (RankedSet)
    21open FinitePresentations FiniteContexts FiniteContextualOrder FiniteSyntacticAlgebra
    22open FiniteAcceptance ExpandedSyntacticAlgebra
    23open ExtremalContexts (Data)
    24
    25abbrev Situation {A : RankedSet} (F : ClosedProperty A) (k : ℕ) :=
    26 Data (Carrier F) k × Carrier F k
    27
    28def Below {A : RankedSet} (F : ClosedProperty A) {k : ℕ}
    29 (x y : Situation F k) : Prop :=
    30 FiniteExtremal.DataBelow F x.1 y.1 ∧ ClassBelow F x.2 y.2
    31
    32def Accepted {A : RankedSet} (F : ClosedProperty A) (E : Algebra (Carrier F))
    33 {k : ℕ} (x : Situation F k) : Prop :=
    34 FiniteExtremal.Accepts F E x.2 x.1
    35
    36def IsExtremal {A : RankedSet} (F : ClosedProperty A) (E : Algebra (Carrier F))
    37 {k : ℕ} (x : Situation F k) : Prop :=
    38 Accepted F E x ∧ ∀ y, Below F y x → Accepted F E y → y = x
    39
    40def ExtremalElement {A : RankedSet} (F : ClosedProperty A) (E : Algebra (Carrier F))
    41 {k : ℕ} (a : Carrier F k) : Prop :=
    42 ∃ x : Data (Carrier F) k, IsExtremal F E (x, a)
    43
    44axiom choice {A : RankedSet} (F : ClosedProperty A) (E : Algebra (Carrier F))
    45 (hfinite : ∀ n, Finite (Carrier F n)) {k : ℕ} (x : Situation F k)
    46 (hx : Accepted F E x) :
    47 ∃ y, Below F y x ∧ IsExtremal F E y
    48
    49axiom replacement {A : RankedSet} (L : Algebras.Language A)
    50 (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L)
    51 (E : SyntacticAlgebra L) {k : ℕ}
    52 (C : Context (Carrier (Accepting L)) k 0) (a : Carrier (Accepting L) k)
    53 (ha : AcceptingClass (Accepting L) (E.algebra.eval 0 (plug C (atomic a)))) :
    54 ∃ b, ExtremalElement (Accepting L) E.algebra b ∧ ClassBelow (Accepting L) b a ∧
    55 AcceptingClass (Accepting L) (E.algebra.eval 0 (plug C (atomic b)))
    56
    57axiom simultaneous {A B : RankedSet} (L : Algebras.Language A)
    58 (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L)
    59 (E : SyntacticAlgebra L) (P : FiniteSystem B 0)
    60 (q : ∀ v : P.Vertex, Carrier (Accepting L) (P.graph.label v).1) :
    61 AcceptingClass (Accepting L) (E.algebra.eval 0 (withLabels P q)) ↔
    62 ∃ r : ∀ v : P.Vertex, Carrier (Accepting L) (P.graph.label v).1,
    63 (∀ v, ExtremalElement (Accepting L) E.algebra (r v) ∧
    64 ClassBelow (Accepting L) (r v) (q v)) ∧
    65 AcceptingClass (Accepting L) (E.algebra.eval 0 (withLabels P r))
    66
    67axiom fixed_element {A : RankedSet} (F : ClosedProperty A) (E : Algebra (Carrier F))
    68 {k : ℕ} (x : Data (Carrier F) k) (a : Carrier F k)
    69 (hx : IsExtremal F E (x, a)) : FiniteExtremal.IsExtremal F E a x
    70
    71axiom split_value {A : RankedSet} (L : Algebras.Language A)
    72 (E : SyntacticAlgebra L) {k : ℕ} (hk : 1 ≤ k)
    73 (x : Data (Carrier (Accepting L)) k) (a : Carrier (Accepting L) k)
    74 (hx : IsExtremal (Accepting L) E.algebra (x, a)) :
    75 E.algebra.eval k (SplitExtremal.delta x.1 x.2 a) = a
    76
    77axiom normal_test {A : RankedSet} (L : Algebras.Language A)
    78 (E : SyntacticAlgebra L) {k : ℕ}
    79 (x : Data (Carrier (Accepting L)) k) (a : Carrier (Accepting L) k)
    80 (hx : IsExtremal (Accepting L) E.algebra (x, a))
    81 (y : Data (Carrier (Accepting L)) k) :
    82 FiniteExtremal.Accepts (Accepting L) E.algebra a y ↔
    83 FiniteExtremal.DataBelow (Accepting L) x y
    84
    85axiom unary_selected {A : RankedSet} (L : Algebras.Language A)
    86 (E : SyntacticAlgebra L) (b : Carrier (Accepting L) 1)
    87 (hb : ExtremalElement (Accepting L) E.algebra b) :
    88 ExtremalUnaryTypes.Selected L E b
    89
    90axiom parallel_decomposition {A : RankedSet} (L : Algebras.Language A)
    91 (E : SyntacticAlgebra L) {k : ℕ} (hk : 1 ≤ k) (a : Carrier (Accepting L) k)
    92 (ha : ExtremalElement (Accepting L) E.algebra a) :
    93 ∃ b : Fin k → Carrier (Accepting L) 1,
    94 E.algebra.eval k (ofSetSystem (DeterministicElements.parallel b)) = a
    95
    96end Lax369799.ExtremalSituations
    97
    Show ProofShow ProofShow 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…