Compression of the variables of flatten-resolutions
Lax369799.ResolutionCompression · concepts/Lax369799/ResolutionCompression.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Rename the variables of each inner system and retain one outer edge for each new variable. If the selected representatives preserve the original variable maps, the resulting outer system is still a flatten-resolution. Uniform bounds on the representative fibres pass to the new resolution.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.Renaming |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Compression of the variables of flatten-resolutions |
| 6 | type: theorem |
| 7 | --- |
| 8 | Rename the variables of each inner system and retain one outer edge for |
| 9 | each new variable. If the selected representatives preserve the original |
| 10 | variable maps, the resulting outer system is still a flatten-resolution. |
| 11 | Uniform bounds on the representative fibres pass to the new resolution. |
| 12 | -/ |
| 13 | namespace Lax369799.ResolutionCompression |
| 14 | open RankedSystems Resolutions Renaming |
| 15 | |
| 16 | def compressedPresentation {A : RankedSet} {n : ℕ} (T : System (System A) n) |
| 17 | (arity : T.val.Vertex → ℕ) |
| 18 | (τ : ∀ v, Fin (T.val.graph.label v).1 → Fin (arity v)) |
| 19 | (sectionMap : ∀ v, Fin (arity v) → Fin (T.val.graph.label v).1) : |
| 20 | Presentation (System A) n T.val.Vertex where |
| 21 | label := fun v => ⟨arity v, renameSystem (τ v) (T.val.graph.label v).2⟩ |
| 22 | initial := T.val.graph.initial |
| 23 | root := T.val.graph.root |
| 24 | edge := fun v d t => ∃ i : Fin (arity v), d = i.val ∧ T.val.graph.edge v (sectionMap v i).val t |
| 25 | direction_valid := by rintro v d t ⟨i, rfl, _⟩; exact i.isLt |
| 26 | |
| 27 | def backPresentation {A : RankedSet} {n : ℕ} (T : System (System A) n) |
| 28 | (arity : T.val.Vertex → ℕ) |
| 29 | (τ : ∀ v, Fin (T.val.graph.label v).1 → Fin (arity v)) |
| 30 | (sectionMap : ∀ v, Fin (arity v) → Fin (T.val.graph.label v).1) : |
| 31 | Presentation (System A) n T.val.Vertex := { |
| 32 | T.val.graph with label := fun v => ⟨(T.val.graph.label v).1, |
| 33 | renameSystem (sectionMap v ∘ τ v) (T.val.graph.label v).2⟩ } |
| 34 | |
| 35 | |
| 36 | axiom compress_flatten_resolution {A : RankedSet} {n : ℕ} (S : SetSystem (SetSystem A) n) |
| 37 | (T : System (System A) n) (r : FlattenResolution S T) |
| 38 | (arity : T.val.Vertex → ℕ) |
| 39 | (τ : ∀ v, Fin (T.val.graph.label v).1 → Fin (arity v)) |
| 40 | (sectionMap : ∀ v, Fin (arity v) → Fin (T.val.graph.label v).1) |
| 41 | (hσ : ∀ v i, r.variableMap v (sectionMap v (τ v i)) = r.variableMap v i) |
| 42 | (bound : ℕ) (hb : ∀ v j, Nat.card {i // r.variableMap v (sectionMap v i) = j} ≤ bound) : |
| 43 | ∃ U : System (System A) n, |
| 44 | U.val = trim (compressedPresentation T arity τ sectionMap) ∧ |
| 45 | ∃ r' : FlattenResolution S U, |
| 46 | ∀ v j, Nat.card {i // r'.variableMap v i = j} ≤ bound |
| 47 | |
| 48 | axiom evaluation {A : RankedSet} (E : Algebras.Algebra A) (hE : Algebras.UnfoldInvariant E) {n : ℕ} |
| 49 | (T : System (System A) n) (arity : T.val.Vertex → ℕ) |
| 50 | (τ : ∀ v, Fin (T.val.graph.label v).1 → Fin (arity v)) |
| 51 | (sectionMap : ∀ v, Fin (arity v) → Fin (T.val.graph.label v).1) : |
| 52 | ∃ U V : System (System A) n, |
| 53 | U.val = trim (backPresentation T arity τ sectionMap) ∧ |
| 54 | V.val = trim (compressedPresentation T arity τ sectionMap) ∧ |
| 55 | E.eval n (relabelSystem E.eval U) = E.eval n (relabelSystem E.eval V) |
| 56 | |
| 57 | end Lax369799.ResolutionCompression |
| 58 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments