Extremal accepted situations in the syntactic algebra
Lax369799.ExtremalSituations · concepts/Lax369799/ExtremalSituations.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Evidence
This concept declares 8 statements. Each proof establishes one of them relative to its assumptions.
1 choice proven
2 fixed_element proven
3 normal_test proven
4 parallel_decomposition proven
5 replacement proven
6 simultaneous proven
7 split_value proven
8 unary_selected proven
Lean source view on GitHub
| 1 | import Lax369799.ExpandedSyntacticAlgebra |
| 2 | import Lax369799.ExtremalUnaryTypes |
| 3 | import Lax369799.FiniteLocalReplacement |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Extremal accepted situations in the syntactic algebra |
| 8 | type: theorem |
| 9 | --- |
| 10 | Sections 5.1–5.2 minimize the element in the hole as well as its context |
| 11 | pieces. In the syntactic algebra, planting allows context pieces to be |
| 12 | recorded by their unary values, a root flag, and self-loop directions. |
| 13 | An extremal situation is a componentwise minimal accepted pair of these |
| 14 | data and an element. This is the planted form of Definition 85. |
| 15 | Unlike extremality of context data for a fixed element, it also forces |
| 16 | every accepted decrease of that element to be equal to it. |
| 17 | -/ |
| 18 | |
| 19 | namespace Lax369799.ExtremalSituations |
| 20 | open RankedSystems (RankedSet) |
| 21 | open FinitePresentations FiniteContexts FiniteContextualOrder FiniteSyntacticAlgebra |
| 22 | open FiniteAcceptance ExpandedSyntacticAlgebra |
| 23 | open ExtremalContexts (Data) |
| 24 | |
| 25 | abbrev Situation {A : RankedSet} (F : ClosedProperty A) (k : ℕ) := |
| 26 | Data (Carrier F) k × Carrier F k |
| 27 | |
| 28 | def 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 | |
| 32 | def 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 | |
| 36 | def 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 | |
| 40 | def 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 | |
| 44 | axiom 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 | |
| 49 | axiom 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 | |
| 57 | axiom 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 | |
| 67 | axiom 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 | |
| 71 | axiom 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 | |
| 77 | axiom 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 | |
| 85 | axiom 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 | |
| 90 | axiom 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 | |
| 96 | end Lax369799.ExtremalSituations |
| 97 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments