Variable renaming and inverse renaming without pruning
Lax369799.FiniteRenaming · concepts/Lax369799/FiniteRenaming.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Direct images and inverse images of variable edges retain all vertices. Their adjunction is Lemma 17 of the revised manuscript. Both operations preserve morphisms, local surjectivity, and foldings.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FiniteStructureTheorems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Variable renaming and inverse renaming without pruning |
| 6 | type: theorem |
| 7 | --- |
| 8 | Direct images and inverse images of variable edges retain all vertices. |
| 9 | Their adjunction is Lemma 17 of the revised manuscript. Both operations |
| 10 | preserve morphisms, local surjectivity, and foldings. |
| 11 | -/ |
| 12 | |
| 13 | namespace Lax369799.FiniteRenaming |
| 14 | open RankedSystems FinitePresentations FiniteMorphisms FiniteStructureTheorems |
| 15 | |
| 16 | def push {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) (S : FiniteSystem A m) : |
| 17 | FiniteSystem A n where |
| 18 | size := S.size |
| 19 | graph := { |
| 20 | label := S.graph.label, initial := S.graph.initial, root := S.graph.root |
| 21 | edge := fun v d t => ∃ s, S.graph.edge v d s ∧ t = Sum.map id σ s |
| 22 | direction_valid := by rintro v d t ⟨s,hs,_⟩; exact S.graph.direction_valid v d s hs } |
| 23 | |
| 24 | def pull {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) (S : FiniteSystem A n) : |
| 25 | FiniteSystem A m where |
| 26 | size := S.size |
| 27 | graph := { |
| 28 | label := S.graph.label, initial := S.graph.initial, root := S.graph.root |
| 29 | edge := fun v d t => S.graph.edge v d (Sum.map id σ t) |
| 30 | direction_valid := fun v d _t h => S.graph.direction_valid v d _ h } |
| 31 | |
| 32 | axiom adjunction {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 33 | (S : FiniteSystem A m) (T : FiniteSystem A n) (ρ : S.Vertex → T.Vertex) : |
| 34 | (∃ f : Morphism (push σ S) T, f.toFun = ρ) ↔ |
| 35 | (∃ g : Morphism S (pull σ T), g.toFun = ρ) |
| 36 | |
| 37 | axiom push_morphism {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 38 | {S T : FiniteSystem A m} (f : Morphism S T) : |
| 39 | ∃ g : Morphism (push σ S) (push σ T), g.toFun = f.toFun ∧ |
| 40 | (LocallySurjective f → LocallySurjective g) ∧ (Folding f → Folding g) |
| 41 | |
| 42 | axiom pull_morphism {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 43 | {S T : FiniteSystem A n} (f : Morphism S T) : |
| 44 | ∃ g : Morphism (pull σ S) (pull σ T), g.toFun = f.toFun ∧ |
| 45 | (LocallySurjective f → LocallySurjective g) ∧ (Folding f → Folding g) |
| 46 | |
| 47 | axiom pull_flatten {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 48 | (P : FiniteSystem (FiniteSystem A) n) : pull σ (flatten P) = flatten (pull σ P) |
| 49 | |
| 50 | end Lax369799.FiniteRenaming |
| 51 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments