Formal unary pieces and extremal accepted situations
Lax369799.ExtendedContexts · concepts/Lax369799/ExtendedContexts.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Definition 65 retains the immediate initial and root exits as two formal markers alongside an ordinary unary value. A closed context made from these pieces is an ordinary finite presentation: the initial marker of piece zero marks the hole initial, a root marker in any piece marks it root, and an initial marker in direction i adds a self-loop in that direction. In the syntactic algebra, planting identifies the two hole marks. Saturating their redundant formal representations relates Definition 85 exactly to minimal planted situations.
Concept map
Evidence
This concept declares 9 statements. Each proof establishes one of them relative to its assumptions.
1 acceptance_normalize proven
2 canonical_order proven
3 element_iff proven
4 extremal_choice proven
5 extremal_iff proven
6 normal_test proven
7 normalize_canonical proven
8 replacement proven
9 simultaneous proven
Lean source view on GitHub
| 1 | import Lax369799.ExtremalSituations |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Formal unary pieces and extremal accepted situations |
| 6 | type: theorem |
| 7 | --- |
| 8 | Definition 65 retains the immediate initial and root exits as two formal |
| 9 | markers alongside an ordinary unary value. A closed context made from |
| 10 | these pieces is an ordinary finite presentation: the initial marker of |
| 11 | piece zero marks the hole initial, a root marker in any piece marks it |
| 12 | root, and an initial marker in direction i adds a self-loop in that |
| 13 | direction. In the syntactic algebra, planting identifies the two hole |
| 14 | marks. Saturating their redundant formal representations relates |
| 15 | Definition 85 exactly to minimal planted situations. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax369799.ExtendedContexts |
| 19 | open RankedSystems (RankedSet) |
| 20 | open FinitePresentations FiniteContexts FiniteContextualOrder FiniteSyntacticAlgebra |
| 21 | open FiniteAcceptance ExpandedSyntacticAlgebra |
| 22 | open ExtremalContexts (Data) |
| 23 | |
| 24 | inductive Marker where |
| 25 | | initial |
| 26 | | root |
| 27 | deriving DecidableEq |
| 28 | |
| 29 | instance : Fintype Marker where |
| 30 | elems := {.initial, .root} |
| 31 | complete := by intro m; cases m <;> simp |
| 32 | |
| 33 | abbrev Piece (A : RankedSet) := A 1 × Set Marker |
| 34 | abbrev Pieces (A : RankedSet) (k : ℕ) := Fin (k + 1) → Piece A |
| 35 | |
| 36 | def PieceBelow {A : RankedSet} (F : ClosedProperty A) |
| 37 | (p q : Piece (Carrier F)) : Prop := |
| 38 | ClassBelow F p.1 q.1 ∧ q.2 ⊆ p.2 |
| 39 | |
| 40 | def context {A : RankedSet} {k : ℕ} (p : Pieces A k) : Context A k 0 where |
| 41 | system := { |
| 42 | size := k + 2 |
| 43 | graph := { |
| 44 | label := (ExtremalContexts.normalPresentation |
| 45 | (A := A) ⟨False, ∅⟩ (fun i => (p i).1)).label |
| 46 | initial := fun v => v = (0 : Fin (k + 1)).succ ∨ |
| 47 | (v = 0 ∧ Marker.initial ∈ (p 0).2) |
| 48 | root := fun v => v = 0 ∧ ∃ i, Marker.root ∈ (p i).2 |
| 49 | edge := (ExtremalContexts.normalPresentation |
| 50 | ⟨False, {i | Marker.initial ∈ (p i.succ).2}⟩ (fun i => (p i).1)).edge |
| 51 | direction_valid := (ExtremalContexts.normalPresentation |
| 52 | ⟨False, {i | Marker.initial ∈ (p i.succ).2}⟩ (fun i => (p i).1)).direction_valid } } |
| 53 | one_hole := (ExtremalContexts.normalContext |
| 54 | ⟨False, {i | Marker.initial ∈ (p i.succ).2}⟩ (fun i => (p i).1)).one_hole |
| 55 | |
| 56 | def normalize {A : RankedSet} {k : ℕ} (p : Pieces A k) : Data A k := |
| 57 | ⟨⟨Marker.initial ∈ (p 0).2 ∨ ∃ i, Marker.root ∈ (p i).2, |
| 58 | {i | Marker.initial ∈ (p i.succ).2}⟩, fun i => (p i).1⟩ |
| 59 | |
| 60 | def canonical {A : RankedSet} {k : ℕ} (x : Data A k) : Pieces A k := |
| 61 | fun i => ⟨x.2 i, {m | match m with |
| 62 | | .root => x.1.root |
| 63 | | .initial => Fin.cases x.1.root (fun j => j ∈ x.1.loops) i}⟩ |
| 64 | |
| 65 | def Accepted {A : RankedSet} (L : Algebras.Language A) (E : SyntacticAlgebra L) |
| 66 | {k : ℕ} (p : Pieces (Carrier (Accepting L)) k) (a : Carrier (Accepting L) k) : Prop := |
| 67 | AcceptingClass (Accepting L) (E.algebra.eval 0 (plug (context p) (atomic a))) |
| 68 | |
| 69 | def IsExtremal {A : RankedSet} (L : Algebras.Language A) (E : SyntacticAlgebra L) |
| 70 | {k : ℕ} (p : Pieces (Carrier (Accepting L)) k) (a : Carrier (Accepting L) k) : Prop := |
| 71 | Accepted L E p a ∧ ∀ q b, |
| 72 | (∀ i, PieceBelow (Accepting L) (q i) (p i)) → ClassBelow (Accepting L) b a → |
| 73 | Accepted L E q b → q = p ∧ b = a |
| 74 | |
| 75 | def ExtremalElement {A : RankedSet} (L : Algebras.Language A) (E : SyntacticAlgebra L) |
| 76 | {k : ℕ} (a : Carrier (Accepting L) k) : Prop := ∃ p, IsExtremal L E p a |
| 77 | |
| 78 | axiom normalize_canonical {A : RankedSet} {k : ℕ} (x : Data A k) : |
| 79 | normalize (canonical x) = x |
| 80 | |
| 81 | axiom canonical_order {A : RankedSet} (F : ClosedProperty A) {k : ℕ} |
| 82 | (x : Data (Carrier F) k) (p : Pieces (Carrier F) k) : |
| 83 | (∀ i, PieceBelow F (canonical x i) (p i)) ↔ |
| 84 | FiniteExtremal.DataBelow F x (normalize p) |
| 85 | |
| 86 | axiom acceptance_normalize {A : RankedSet} (L : Algebras.Language A) |
| 87 | (E : SyntacticAlgebra L) {k : ℕ} (p : Pieces (Carrier (Accepting L)) k) |
| 88 | (a : Carrier (Accepting L) k) : |
| 89 | Accepted L E p a ↔ FiniteExtremal.Accepts (Accepting L) E.algebra a (normalize p) |
| 90 | |
| 91 | axiom extremal_iff {A : RankedSet} (L : Algebras.Language A) |
| 92 | (E : SyntacticAlgebra L) {k : ℕ} (p : Pieces (Carrier (Accepting L)) k) |
| 93 | (a : Carrier (Accepting L) k) : |
| 94 | IsExtremal L E p a ↔ canonical (normalize p) = p ∧ |
| 95 | ExtremalSituations.IsExtremal (Accepting L) E.algebra (normalize p, a) |
| 96 | |
| 97 | axiom element_iff {A : RankedSet} (L : Algebras.Language A) |
| 98 | (E : SyntacticAlgebra L) {k : ℕ} (a : Carrier (Accepting L) k) : |
| 99 | ExtremalElement L E a ↔ ExtremalSituations.ExtremalElement (Accepting L) E.algebra a |
| 100 | |
| 101 | axiom extremal_choice {A : RankedSet} (L : Algebras.Language A) |
| 102 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 103 | (E : SyntacticAlgebra L) {k : ℕ} (p : Pieces (Carrier (Accepting L)) k) |
| 104 | (a : Carrier (Accepting L) k) (ha : Accepted L E p a) : |
| 105 | ∃ q b, IsExtremal L E q b ∧ |
| 106 | (∀ i, PieceBelow (Accepting L) (q i) (p i)) ∧ ClassBelow (Accepting L) b a |
| 107 | |
| 108 | axiom replacement {A : RankedSet} (L : Algebras.Language A) |
| 109 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 110 | (E : SyntacticAlgebra L) {k : ℕ} |
| 111 | (C : Context (Carrier (Accepting L)) k 0) (a : Carrier (Accepting L) k) |
| 112 | (ha : AcceptingClass (Accepting L) (E.algebra.eval 0 (plug C (atomic a)))) : |
| 113 | ∃ b, ExtremalElement L E b ∧ ClassBelow (Accepting L) b a ∧ |
| 114 | AcceptingClass (Accepting L) (E.algebra.eval 0 (plug C (atomic b))) |
| 115 | |
| 116 | axiom simultaneous {A B : RankedSet} (L : Algebras.Language A) |
| 117 | (hL : Algebras.UnfoldInvariantLanguage L) (hrec : Algebras.Recognizable L) |
| 118 | (E : SyntacticAlgebra L) (P : FiniteSystem B 0) |
| 119 | (q : ∀ v : P.Vertex, Carrier (Accepting L) (P.graph.label v).1) : |
| 120 | AcceptingClass (Accepting L) (E.algebra.eval 0 (withLabels P q)) ↔ |
| 121 | ∃ r : ∀ v : P.Vertex, Carrier (Accepting L) (P.graph.label v).1, |
| 122 | (∀ v, ExtremalElement L E (r v) ∧ ClassBelow (Accepting L) (r v) (q v)) ∧ |
| 123 | AcceptingClass (Accepting L) (E.algebra.eval 0 (withLabels P r)) |
| 124 | |
| 125 | axiom normal_test {A : RankedSet} (L : Algebras.Language A) |
| 126 | (E : SyntacticAlgebra L) {k : ℕ} |
| 127 | (p q : Pieces (Carrier (Accepting L)) k) (a : Carrier (Accepting L) k) |
| 128 | (ha : IsExtremal L E p a) : |
| 129 | Accepted L E q a ↔ ∀ i, PieceBelow (Accepting L) (p i) (q i) |
| 130 | |
| 131 | end Lax369799.ExtendedContexts |
| 132 |
Builds on
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments