Planted normal contexts and deterministic witnesses
Lax369799.ExtremalContexts · concepts/Lax369799/ExtremalContexts.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A planted normal context records the hole's root mark and self-loop directions, together with its unary pieces. Planting merges the original initial and root marks. The unary components of the witness construction retain these loops; its outer presentation retains the root mark. This extends the construction of Section 5 to ordinary holes with arbitrary boundary data. The extremal choice and comparison inequalities require separate proofs.
Concept map
Evidence
This concept declares 7 statements. Each proof establishes one of them relative to its assumptions.
1 data_monotone proven
2 delta_below proven
3 delta_boundary_comparison proven
4 delta_deterministic proven
5 delta_in_context proven
6 delta_piece_comparison proven
7 extremal_choice proven
Lean source view on GitHub
| 1 | import Lax369799.AutomatonProperty |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Planted normal contexts and deterministic witnesses |
| 6 | type: definition |
| 7 | --- |
| 8 | A planted normal context records the hole's root mark and self-loop |
| 9 | directions, together with its unary pieces. Planting merges the original |
| 10 | initial and root marks. The unary components of the witness construction |
| 11 | retain these loops; its outer presentation retains the root mark. This |
| 12 | extends the construction of Section 5 to ordinary holes with arbitrary |
| 13 | boundary data. The extremal choice and comparison inequalities require |
| 14 | separate proofs. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax369799.ExtremalContexts |
| 18 | open RankedSystems Flattening SetAlgebras AutomatonProperty |
| 19 | |
| 20 | structure Boundary (k : ℕ) where |
| 21 | root : Prop |
| 22 | loops : Set (Fin k) |
| 23 | |
| 24 | /-- The root piece has index zero; direction i uses piece i+1. -/ |
| 25 | def normalPresentation {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 26 | (m : Fin (k + 1) → A 1) : Presentation (WithHole A k) 0 (Fin (k + 2)) where |
| 27 | label := Fin.cases ⟨k, Sum.inr ⟨rfl⟩⟩ (fun i => ⟨1, Sum.inl (m i)⟩) |
| 28 | initial := ∅ |
| 29 | root := fun v => v = (0 : Fin (k + 1)).succ ∨ (v = 0 ∧ B.root) |
| 30 | edge := fun v d t => Fin.cases |
| 31 | ((∃ i : Fin k, d = i.val ∧ t = .inl i.succ.succ) ∨ |
| 32 | (∃ i : Fin k, i ∈ B.loops ∧ d = i.val ∧ t = .inl 0)) |
| 33 | (fun _ => d = 0 ∧ t = .inl 0) v |
| 34 | direction_valid := by |
| 35 | intro v d t |
| 36 | refine Fin.cases ?_ (fun i => ?_) v |
| 37 | · rintro (⟨i, rfl, _⟩ | ⟨i, _, rfl, _⟩) <;> exact i.isLt |
| 38 | · rintro ⟨rfl, _⟩; exact Nat.zero_lt_one |
| 39 | |
| 40 | def normalSystem {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 41 | (m : Fin (k + 1) → A 1) : SetSystem (WithHole A k) 0 where |
| 42 | size := k + 2 |
| 43 | graph := normalPresentation B m |
| 44 | reachable := by |
| 45 | let G := normalPresentation B m |
| 46 | have h1 : G.Reachable (0 : Fin (k + 1)).succ := |
| 47 | ⟨_, Or.inr (Or.inl rfl), .refl⟩ |
| 48 | have h0 : G.Reachable 0 := by |
| 49 | obtain ⟨r, hr, hp⟩ := h1 |
| 50 | exact ⟨r, hr, hp.tail ⟨0, rfl, rfl⟩⟩ |
| 51 | intro v |
| 52 | refine Fin.cases h0 (fun i => ?_) v |
| 53 | refine Fin.cases h1 (fun j => ?_) i |
| 54 | obtain ⟨r, hr, hp⟩ := h0 |
| 55 | exact ⟨r, hr, hp.tail ⟨j.val, Or.inl ⟨j, rfl, rfl⟩⟩⟩ |
| 56 | |
| 57 | def normalContext {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 58 | (m : Fin (k + 1) → A 1) : SetContext A k 0 where |
| 59 | system := normalSystem B m |
| 60 | one_hole := by |
| 61 | change ∃! v : Fin (k + 2), IsHole ((normalPresentation B m).label v) |
| 62 | refine ⟨0, ⟨⟨rfl⟩, rfl⟩, ?_⟩ |
| 63 | intro v |
| 64 | refine Fin.cases (fun _ => rfl) (fun i h => ?_) v |
| 65 | obtain ⟨h, he⟩ := h |
| 66 | cases he |
| 67 | |
| 68 | /-- Unary component U_i, with the retained loop directions at its a-vertex. -/ |
| 69 | def component {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 70 | (m : Fin (k + 1) → A 1) (a : A k) (i : Fin k) : SetSystem A 1 where |
| 71 | size := k + 1 |
| 72 | graph := { |
| 73 | label := Fin.cases ⟨k, a⟩ (fun j => ⟨1, m j.succ⟩) |
| 74 | initial := {0} |
| 75 | root := ∅ |
| 76 | edge := fun v d t => Fin.cases |
| 77 | ((∃ j : Fin k, d = j.val ∧ t = .inl j.succ) ∨ |
| 78 | (∃ j : Fin k, j ∈ B.loops ∧ d = j.val ∧ t = .inl 0) ∨ |
| 79 | (d = i.val ∧ t = .inr 0)) |
| 80 | (fun _ => d = 0 ∧ t = .inl 0) v |
| 81 | direction_valid := by |
| 82 | intro v d t |
| 83 | refine Fin.cases ?_ (fun j => ?_) v |
| 84 | · rintro (⟨j, rfl, _⟩ | ⟨j, _, rfl, _⟩ | ⟨rfl, _⟩) |
| 85 | · exact j.isLt |
| 86 | · exact j.isLt |
| 87 | · exact i.isLt |
| 88 | · rintro ⟨rfl, _⟩; exact Nat.zero_lt_one } |
| 89 | reachable := by |
| 90 | intro v |
| 91 | refine ⟨0, Or.inl rfl, ?_⟩ |
| 92 | refine Fin.cases Relation.ReflTransGen.refl (fun j => ?_) v |
| 93 | exact Relation.ReflTransGen.refl.tail ⟨j.val, Or.inl ⟨j, rfl, rfl⟩⟩ |
| 94 | |
| 95 | /-- The outer presentation uses only unary labels. -/ |
| 96 | def deltaPattern {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 97 | (m : Fin (k + 1) → A 1) (a : A k) : SetSystem (SetSystem A) k where |
| 98 | size := k + 1 |
| 99 | graph := { |
| 100 | label := Fin.cases ⟨1, atomic (m 0)⟩ (fun i => ⟨1, component B m a i⟩) |
| 101 | initial := fun v => v ≠ 0 |
| 102 | root := fun v => v = 0 ∨ B.root |
| 103 | edge := fun v d t => d = 0 ∧ Fin.cases |
| 104 | (∃ i : Fin k, t = .inl i.succ) |
| 105 | (fun i => t = .inr i) v |
| 106 | direction_valid := by |
| 107 | rintro v d t ⟨rfl, _⟩ |
| 108 | refine Fin.cases Nat.zero_lt_one (fun _ => Nat.zero_lt_one) v } |
| 109 | reachable := by |
| 110 | intro v |
| 111 | refine ⟨v, ?_, .refl⟩ |
| 112 | refine Fin.cases (Or.inr (Or.inl rfl)) (fun i => Or.inl (Fin.succ_ne_zero i)) v |
| 113 | |
| 114 | noncomputable def delta {A : RankedSet} {k : ℕ} (B : Boundary k) |
| 115 | (m : Fin (k + 1) → A 1) (a : A k) : SetSystem A k := |
| 116 | flatten (deltaPattern B m a) |
| 117 | |
| 118 | axiom delta_deterministic {A : RankedSet} (E : SetAlgebra A) {k : ℕ} |
| 119 | (B : Boundary k) (m : Fin (k + 1) → A 1) (a : A k) : |
| 120 | Deterministic E (E.eval k (delta B m a)) |
| 121 | |
| 122 | abbrev Data (A : RankedSet) (k : ℕ) := Boundary k × (Fin (k + 1) → A 1) |
| 123 | |
| 124 | /-- Smaller data have more boundary marks and smaller unary values. -/ |
| 125 | def DataBelow {A : RankedSet} (E : SetAlgebra A) {k : ℕ} (x y : Data A k) : Prop := |
| 126 | (y.1.root → x.1.root) ∧ y.1.loops ⊆ x.1.loops ∧ ∀ i, Below E (x.2 i) (y.2 i) |
| 127 | |
| 128 | noncomputable def value {A : RankedSet} (E : SetAlgebra A) {k : ℕ} |
| 129 | (a : A k) (x : Data A k) : A 0 := |
| 130 | E.eval 0 (plug (normalContext x.1 x.2) (atomic a)) |
| 131 | |
| 132 | def Accepts {A : RankedSet} (E : SetAlgebra A) (f : A 0) {k : ℕ} |
| 133 | (a : A k) (x : Data A k) : Prop := Below E f (value E a x) |
| 134 | |
| 135 | def IsExtremal {A : RankedSet} (E : SetAlgebra A) (f : A 0) {k : ℕ} |
| 136 | (a : A k) (x : Data A k) : Prop := |
| 137 | Accepts E f a x ∧ ∀ y, DataBelow E y x → Accepts E f a y → DataBelow E x y |
| 138 | |
| 139 | /-- Finite minimization over boundary data as well as the unary pieces. -/ |
| 140 | axiom extremal_choice {A : RankedSet} (E : SetAlgebra A) (hA : RankwiseFinite A) |
| 141 | (f : A 0) {k : ℕ} (a : A k) (x : Data A k) (hx : Accepts E f a x) : |
| 142 | ∃ y : Data A k, DataBelow E y x ∧ Accepts E f a y ∧ |
| 143 | ∀ z : Data A k, DataBelow E z y → Accepts E f a z → DataBelow E y z |
| 144 | |
| 145 | axiom data_monotone {A : RankedSet} (E : SetAlgebra A) {k : ℕ} |
| 146 | (x y : Data A k) (h : DataBelow E x y) (a : A k) : |
| 147 | Below E (E.eval 0 (plug (normalContext x.1 x.2) (atomic a))) |
| 148 | (E.eval 0 (plug (normalContext y.1 y.2) (atomic a))) |
| 149 | |
| 150 | axiom delta_in_context {A : RankedSet} (E : SetAlgebra A) {k : ℕ} |
| 151 | (x : Data A k) (a : A k) : |
| 152 | Below E (value E a x) (value E (E.eval k (delta x.1 x.2 a)) x) |
| 153 | |
| 154 | axiom delta_boundary_comparison {A : RankedSet} (E : SetAlgebra A) (f : A 0) |
| 155 | {k : ℕ} (hk : 1 ≤ k) (x y : Data A k) (a : A k) |
| 156 | (hx : IsExtremal E f a x) (hy : Accepts E f (E.eval k (delta x.1 x.2 a)) y) : |
| 157 | (y.1.root → x.1.root) ∧ y.1.loops ⊆ x.1.loops |
| 158 | |
| 159 | axiom delta_piece_comparison {A : RankedSet} (E : SetAlgebra A) (f : A 0) |
| 160 | {k : ℕ} (hk : 1 ≤ k) (x y : Data A k) (a : A k) |
| 161 | (hx : IsExtremal E f a x) (hy : Accepts E f (E.eval k (delta x.1 x.2 a)) y) : |
| 162 | ∀ j, Below E (x.2 j) (y.2 j) |
| 163 | |
| 164 | axiom delta_below {A : RankedSet} (E : SetAlgebra A) (f : A 0) |
| 165 | (hp : PlantInvariant E f) (hs : OrderSeparating E f) {k : ℕ} (hk : 2 ≤ k) |
| 166 | (x : Data A k) (a : A k) (hx : IsExtremal E f a x) : |
| 167 | Below E (E.eval k (delta x.1 x.2 a)) a |
| 168 | |
| 169 | end Lax369799.ExtremalContexts |
| 170 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments