Systems with all output variables reachable
Lax369799.SupportedSystems · concepts/Lax369799/SupportedSystems.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Definition 6 requires every vertex and every output variable to be reachable from the unique initial vertex. The earlier deterministic presentation interface already requires vertex reachability; full support adds occurrence of every variable edge. Relabelling and surjective renaming preserve this condition. Flattening fully supported systems retains all vertices and all output variables (Lemma 33). In rank zero, the support condition is vacuous.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FinitePresentations |
| 2 | import Lax369799.FlatteningTheorems |
| 3 | import Lax369799.Renaming |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Systems with all output variables reachable |
| 8 | type: theorem |
| 9 | --- |
| 10 | Definition 6 requires every vertex and every output variable to be |
| 11 | reachable from the unique initial vertex. The earlier deterministic |
| 12 | presentation interface already requires vertex reachability; full support |
| 13 | adds occurrence of every variable edge. Relabelling and surjective |
| 14 | renaming preserve this condition. Flattening fully supported systems |
| 15 | retains all vertices and all output variables (Lemma 33). In rank zero, |
| 16 | the support condition is vacuous. |
| 17 | -/ |
| 18 | |
| 19 | namespace Lax369799.SupportedSystems |
| 20 | open RankedSystems (RankedSet RankedMap) |
| 21 | open FinitePresentations |
| 22 | |
| 23 | def FullySupported {A : RankedSet} {n : ℕ} (S : RankedSystems.System A n) : Prop := |
| 24 | ∀ i : Fin n, ∃ v d, S.val.graph.edge v d (.inr i) |
| 25 | |
| 26 | abbrev System (A : RankedSet) (n : ℕ) := {S : RankedSystems.System A n // FullySupported S} |
| 27 | |
| 28 | def forget {A : RankedSet} : RankedMap (System A) (RankedSystems.System A) := fun _ S => S.val |
| 29 | |
| 30 | def relabel {A B : RankedSet} (f : RankedMap A B) {n : ℕ} (S : System A n) : System B n := |
| 31 | ⟨RankedSystems.relabelSystem f S.val, S.property⟩ |
| 32 | |
| 33 | def atomic {A : RankedSet} {n : ℕ} (a : A n) : System A n := |
| 34 | ⟨RankedSystems.atomicSystem a, fun i => ⟨(0 : Fin 1), i.val, i, rfl, rfl⟩⟩ |
| 35 | |
| 36 | def closedEquiv (A : RankedSet) : System A 0 ≃ RankedSystems.System A 0 where |
| 37 | toFun := Subtype.val |
| 38 | invFun := fun S => ⟨S, fun i => Fin.elim0 i⟩ |
| 39 | left_inv := fun _ => rfl |
| 40 | right_inv := fun _ => rfl |
| 41 | |
| 42 | def rename {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n) |
| 43 | (hσ : Function.Surjective σ) (S : System A m) : System A n := |
| 44 | ⟨Renaming.renameSystem σ S.val, fun j => by |
| 45 | obtain ⟨i, rfl⟩ := hσ j |
| 46 | obtain ⟨v, d, hd⟩ := S.property i |
| 47 | exact ⟨v, d, .inr i, hd, rfl⟩⟩ |
| 48 | |
| 49 | def pattern {A : RankedSet} {n : ℕ} (S : System (System A) n) : |
| 50 | FiniteSystem (FiniteSystem A) n := |
| 51 | FinitePresentations.relabel (fun _ T => ofSetSystem T.val.val) (ofSetSystem S.val.val) |
| 52 | |
| 53 | def forgetPattern {A : RankedSet} {n : ℕ} (S : System (System A) n) : |
| 54 | RankedSystems.System (RankedSystems.System A) n := |
| 55 | RankedSystems.relabelSystem forget S.val |
| 56 | |
| 57 | axiom flatten_reachable {A : RankedSet} {n : ℕ} (S : System (System A) n) : |
| 58 | ∀ v, (flattenPresentation (pattern S).graph).Reachable v |
| 59 | |
| 60 | axiom flatten_system {A : RankedSet} {n : ℕ} (S : System (System A) n) : |
| 61 | ∃ T : System A n, Flattening.SystemFlattening (forgetPattern S) T.val |
| 62 | |
| 63 | end Lax369799.SupportedSystems |
| 64 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments