The closed extremal witness
Lax369799.ClosedExtremal · concepts/Lax369799/ClosedExtremal.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The rank-zero case of Lemma 91 retains the hole and its incoming unary piece, makes the hole initial, and retains the former initial vertices as roots. No direction copy or output edge is needed. Testing this closed witness forces every component of an accepting context above the original extremal datum. Minimality then identifies its value with the hole value.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ExtremalSituations |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The closed extremal witness |
| 6 | type: theorem |
| 7 | --- |
| 8 | The rank-zero case of Lemma 91 retains the hole and its incoming unary |
| 9 | piece, makes the hole initial, and retains the former initial vertices |
| 10 | as roots. No direction copy or output edge is needed. Testing this closed |
| 11 | witness forces every component of an accepting context above the original |
| 12 | extremal datum. Minimality then identifies its value with the hole value. |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.ClosedExtremal |
| 16 | open RankedSystems (RankedSet) |
| 17 | open FinitePresentations FiniteContextualOrder FiniteSyntacticAlgebra |
| 18 | open FiniteAcceptance ExpandedSyntacticAlgebra |
| 19 | open ExtremalContexts (Data) |
| 20 | open FiniteExtremal (Accepts value DataBelow) |
| 21 | |
| 22 | def witness {A : RankedSet} (x : Data A 0) (a : A 0) : FiniteSystem A 0 where |
| 23 | size := 2 |
| 24 | graph := { |
| 25 | label := Fin.cases ⟨0, a⟩ (fun i => ⟨1, x.2 i⟩) |
| 26 | initial := {0} |
| 27 | root := fun v => v = 1 ∨ (v = 0 ∧ x.1.root) |
| 28 | edge := fun v d t => v = 1 ∧ d = 0 ∧ t = .inl 0 |
| 29 | direction_valid := by |
| 30 | rintro v d t ⟨rfl, rfl, _⟩ |
| 31 | exact Nat.zero_lt_one } |
| 32 | |
| 33 | axiom comparison {A : RankedSet} (L : Algebras.Language A) |
| 34 | (E : SyntacticAlgebra L) (x y : Data (Carrier (Accepting L)) 0) |
| 35 | (a : Carrier (Accepting L) 0) |
| 36 | (hx : Lax369799.FiniteExtremal.IsExtremal (Accepting L) E.algebra a x) |
| 37 | (hy : Accepts (Accepting L) E.algebra (E.algebra.eval 0 (witness x a)) y) : |
| 38 | DataBelow (Accepting L) x y |
| 39 | |
| 40 | axiom in_context {A : RankedSet} (L : Algebras.Language A) |
| 41 | (E : SyntacticAlgebra L) (x : Data (Carrier (Accepting L)) 0) |
| 42 | (a : Carrier (Accepting L) 0) : |
| 43 | ClassBelow (Accepting L) (value E.algebra a x) |
| 44 | (value E.algebra (E.algebra.eval 0 (witness x a)) x) |
| 45 | |
| 46 | axiom below {A : RankedSet} (L : Algebras.Language A) |
| 47 | (E : SyntacticAlgebra L) (x : Data (Carrier (Accepting L)) 0) |
| 48 | (a : Carrier (Accepting L) 0) |
| 49 | (hx : Lax369799.FiniteExtremal.IsExtremal (Accepting L) E.algebra a x) : |
| 50 | ClassBelow (Accepting L) (E.algebra.eval 0 (witness x a)) a |
| 51 | |
| 52 | axiom witness_value {A : RankedSet} (L : Algebras.Language A) |
| 53 | (E : SyntacticAlgebra L) (x : Data (Carrier (Accepting L)) 0) |
| 54 | (a : Carrier (Accepting L) 0) |
| 55 | (hx : Lax369799.ExtremalSituations.IsExtremal (Accepting L) E.algebra (x, a)) : |
| 56 | E.algebra.eval 0 (witness x a) = a |
| 57 | |
| 58 | axiom normal_test {A : RankedSet} (L : Algebras.Language A) |
| 59 | (E : SyntacticAlgebra L) (x : Data (Carrier (Accepting L)) 0) |
| 60 | (a : Carrier (Accepting L) 0) |
| 61 | (hx : Lax369799.ExtremalSituations.IsExtremal (Accepting L) E.algebra (x, a)) |
| 62 | (y : Data (Carrier (Accepting L)) 0) : |
| 63 | Accepts (Accepting L) E.algebra a y ↔ DataBelow (Accepting L) x y |
| 64 | |
| 65 | end Lax369799.ClosedExtremal |
| 66 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments