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

Extremal witnesses with separate rooted components

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

    Each unary component has its own rooted copy of the incoming context piece. There is no choice between different successors beneath that root.

    Concept map
    23 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

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

    1 acceptance_iff_dataBelow proven

    4 delta_boundary_comparison proven

    Lean source view on GitHub

    1import Lax369799.FiniteExtremal
    2import Lax369799.DeterministicElements
    3
    4/-!
    5---
    6title: Extremal witnesses with separate rooted components
    7type: theorem
    8---
    9Each unary component has its own rooted copy of the incoming context piece.
    10There is no choice between different successors beneath that root.
    11-/
    12namespace Lax369799.SplitExtremal
    13open RankedSystems (RankedSet)
    14open FinitePresentations FiniteContextualOrder FiniteSyntacticAlgebra
    15open ExtremalContexts (Boundary Data)
    16open FiniteExtremal (IsExtremal Accepts value)
    17
    18def component {A : RankedSet} {k : ℕ} (B : Boundary k)
    19 (m : Fin (k + 1) → A 1) (a : A k) (i : Fin k) : FiniteSystem A 1 where
    20 size := k + 2
    21 graph := {
    22 label := Fin.cases ⟨k, a⟩ (fun j => ⟨1, m j⟩)
    23 initial := {0}
    24 root := fun v => v = (0 : Fin (k + 1)).succ ∨ (v = 0 ∧ B.root)
    25 edge := fun v d t => Fin.cases
    26 ((∃ j : Fin k, d = j.val ∧ t = .inl j.succ.succ) ∨
    27 (∃ j : Fin k, j ∈ B.loops ∧ d = j.val ∧ t = .inl 0) ∨
    28 (d = i.val ∧ t = .inr 0))
    29 (fun _ => d = 0 ∧ t = .inl 0) v
    30 direction_valid := by
    31 intro v d t
    32 refine Fin.cases ?_ (fun j => ?_) v
    33 · rintro (⟨j, rfl, _⟩ | ⟨j, _, rfl, _⟩ | ⟨rfl, _⟩)
    34 · exact j.isLt
    35 · exact j.isLt
    36 · exact i.isLt
    37 · rintro ⟨rfl, _⟩; exact Nat.zero_lt_one }
    38
    39def pattern {A : RankedSet} {k : ℕ} (B : Boundary k)
    40 (m : Fin (k + 1) → A 1) (a : A k) : FiniteSystem (FiniteSystem A) k where
    41 size := k
    42 graph := {
    43 label := fun i => ⟨1, component B m a i⟩
    44 initial := Set.univ
    45 root := ∅
    46 edge := fun i d t => d = 0 ∧ t = .inr i
    47 direction_valid := by rintro i d t ⟨rfl, _⟩; exact Nat.zero_lt_one }
    48
    49noncomputable def delta {A : RankedSet} {k : ℕ} (B : Boundary k)
    50 (m : Fin (k + 1) → A 1) (a : A k) : FiniteSystem A k := flatten (pattern B m a)
    51
    52axiom delta_boundary_comparison {A : RankedSet} (L : Algebras.Language A)
    53 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    54 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    55 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    56 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    57 {k : ℕ} (hk : 1 ≤ k) (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    58 (a : Carrier (FiniteAcceptance.Accepting L) k)
    59 (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x)
    60 (hy : Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y) :
    61 (y.1.root → x.1.root) ∧ y.1.loops ⊆ x.1.loops
    62
    63axiom delta_piece_comparison {A : RankedSet} (L : Algebras.Language A)
    64 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    65 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    66 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    67 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    68 {k : ℕ} (hk : 1 ≤ k) (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    69 (a : Carrier (FiniteAcceptance.Accepting L) k)
    70 (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x)
    71 (hy : Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y) :
    72 ∀ j, ClassBelow (FiniteAcceptance.Accepting L) (x.2 j) (y.2 j)
    73
    74axiom delta_below {A : RankedSet} (L : Algebras.Language A)
    75 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    76 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    77 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    78 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    79 {k : ℕ} (hk : 1 ≤ k) (x : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    80 (a : Carrier (FiniteAcceptance.Accepting L) k)
    81 (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) :
    82 ClassBelow (FiniteAcceptance.Accepting L) (E.eval k (delta x.1 x.2 a)) a
    83
    84axiom delta_in_context {A : RankedSet} (L : Algebras.Language A)
    85 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    86 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    87 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    88 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    89 {k : ℕ} (x : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    90 (a : Carrier (FiniteAcceptance.Accepting L) k) :
    91 ClassBelow (FiniteAcceptance.Accepting L) (value E a x)
    92 (value E (E.eval k (delta x.1 x.2 a)) x)
    93
    94axiom parallel_value {A : RankedSet} (E : Algebra A) {k : ℕ}
    95 (B : Boundary k) (m : Fin (k + 1) → A 1) (a : A k) :
    96 E.eval k (ofSetSystem (DeterministicElements.parallel (fun i => E.eval 1 (component B m a i)))) =
    97 E.eval k (delta B m a)
    98
    99/-- The witness accepts precisely the normal data above its extremal datum. -/
    100axiom acceptance_iff_dataBelow {A : RankedSet} (L : Algebras.Language A)
    101 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    102 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    103 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    104 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    105 {k : ℕ} (hk : 1 ≤ k) (x y : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    106 (a : Carrier (FiniteAcceptance.Accepting L) k)
    107 (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) :
    108 Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y ↔
    109 FiniteExtremal.DataBelow (FiniteAcceptance.Accepting L) x y
    110
    111/-- Meet of normal context data: union the boundary marks and sum the pieces. -/
    112def meetData {A : RankedSet} (E : Algebra A) {k : ℕ} (y z : Data A k) : Data A k :=
    113 (⟨y.1.root ∨ z.1.root, y.1.loops ∪ z.1.loops⟩, fun i => sumValue E (y.2 i) (z.2 i))
    114
    115axiom accepting_meetData {A : RankedSet} (L : Algebras.Language A)
    116 (E : Algebra (Carrier (FiniteAcceptance.Accepting L)))
    117 (hE : ∀ n (S : FiniteSystem (FiniteSystem A) n),
    118 E.eval n (relabel (quotientMap (FiniteAcceptance.Accepting L)) S) =
    119 quotientMap (FiniteAcceptance.Accepting L) n (flatten S))
    120 {k : ℕ} (hk : 1 ≤ k) (x y z : Data (Carrier (FiniteAcceptance.Accepting L)) k)
    121 (a : Carrier (FiniteAcceptance.Accepting L) k)
    122 (hx : IsExtremal (FiniteAcceptance.Accepting L) E a x) :
    123 Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) (meetData E y z) ↔
    124 Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) y ∧
    125 Accepts (FiniteAcceptance.Accepting L) E (E.eval k (delta x.1 x.2 a)) z
    126
    127end Lax369799.SplitExtremal
    128
    Show 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…