Ranked sets, set-systems, and systems
Lax369799.RankedSystems · concepts/Lax369799/RankedSystems.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A ranked set is a family of sets indexed by natural numbers. A set-system has finitely many labelled vertices, initial and root vertices, and edges with a direction and either a vertex or a variable as target. Every vertex is reachable from an initial or root vertex. A system has one initial vertex, no roots, and exactly one successor in every available direction.
This is the earlier reachable interface. The revised Section 2.2 allows unreachable vertices in set-systems () and requires all output variables of a deterministic system to be reachable (). Finite vertex sets are enumerated by ; directions and variables use zero-based indices. allows an arbitrary finite vertex type when constructing these objects.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Fintype.EquivFin |
| 2 | import Mathlib.Data.Fintype.Sum |
| 3 | import Mathlib.Data.Fintype.Sigma |
| 4 | import Mathlib.Logic.Relation |
| 5 | import Mathlib.Data.Set.Finite.Basic |
| 6 | |
| 7 | /-! |
| 8 | --- |
| 9 | title: Ranked sets, set-systems, and systems |
| 10 | type: definition |
| 11 | --- |
| 12 | A ranked set is a family of sets indexed by natural numbers. A set-system |
| 13 | has finitely many labelled vertices, initial and root vertices, and edges |
| 14 | with a direction and either a vertex or a variable as target. Every vertex |
| 15 | is reachable from an initial or root vertex. A system has one initial |
| 16 | vertex, no roots, and exactly one successor in every available direction. |
| 17 | |
| 18 | This is the earlier reachable interface. The revised Section 2.2 allows |
| 19 | unreachable vertices in set-systems (`FinitePresentations`) and requires |
| 20 | all output variables of a deterministic system to be reachable |
| 21 | (`SupportedSystems`). Finite vertex sets are enumerated by |
| 22 | `Fin size`; directions and variables use zero-based indices. `Presentation` |
| 23 | allows an arbitrary finite vertex type when constructing these objects. |
| 24 | -/ |
| 25 | |
| 26 | namespace Lax369799.RankedSystems |
| 27 | |
| 28 | abbrev RankedSet := ℕ → Type |
| 29 | abbrev Symbol (A : RankedSet) := (n : ℕ) × A n |
| 30 | abbrev RankedMap (A B : RankedSet) := ∀ n, A n → B n |
| 31 | |
| 32 | def RankwiseFinite (A : RankedSet) : Prop := ∀ n, Finite (A n) |
| 33 | |
| 34 | structure Presentation (A : RankedSet) (n : ℕ) (V : Type) where |
| 35 | label : V → Symbol A |
| 36 | initial : Set V |
| 37 | root : Set V |
| 38 | edge : V → ℕ → V ⊕ Fin n → Prop |
| 39 | direction_valid : ∀ v d t, edge v d t → d < (label v).1 |
| 40 | |
| 41 | def Presentation.Step {A : RankedSet} {n : ℕ} {V : Type} |
| 42 | (S : Presentation A n V) (v w : V) : Prop := |
| 43 | ∃ d, S.edge v d (.inl w) |
| 44 | |
| 45 | def Presentation.Reachable {A : RankedSet} {n : ℕ} {V : Type} |
| 46 | (S : Presentation A n V) (v : V) : Prop := |
| 47 | ∃ r, (r ∈ S.initial ∨ r ∈ S.root) ∧ Relation.ReflTransGen S.Step r v |
| 48 | |
| 49 | structure SetSystem (A : RankedSet) (n : ℕ) where |
| 50 | size : ℕ |
| 51 | graph : Presentation A n (Fin size) |
| 52 | reachable : ∀ v, graph.Reachable v |
| 53 | |
| 54 | abbrev SetSystem.Vertex {A : RankedSet} {n : ℕ} (S : SetSystem A n) := Fin S.size |
| 55 | |
| 56 | /-- Restrict to reachable vertices and enumerate the resulting finite set. -/ |
| 57 | noncomputable def trim {A : RankedSet} {n : ℕ} {V : Type} [Fintype V] |
| 58 | (S : Presentation A n V) : SetSystem A n := by |
| 59 | classical |
| 60 | let W := {v : V // S.Reachable v} |
| 61 | let e : W ≃ Fin (Fintype.card W) := Fintype.equivFin W |
| 62 | let g : Fin (Fintype.card W) → V := fun v => (e.symm v).val |
| 63 | let G : Presentation A n (Fin (Fintype.card W)) := { |
| 64 | label := fun v => S.label (g v) |
| 65 | initial := fun v => S.initial (g v) |
| 66 | root := fun v => S.root (g v) |
| 67 | edge := fun v d t => S.edge (g v) d (Sum.map g id t) |
| 68 | direction_valid := fun v d t h => S.direction_valid (g v) d _ h } |
| 69 | refine ⟨Fintype.card W, G, ?_⟩ |
| 70 | intro v |
| 71 | obtain ⟨r, hr, hp⟩ := (e.symm v).property |
| 72 | have rr : S.Reachable r := ⟨r, hr, .refl⟩ |
| 73 | refine ⟨e ⟨r, rr⟩, ?_, ?_⟩ |
| 74 | · change S.initial (g (e ⟨r, rr⟩)) ∨ S.root (g (e ⟨r, rr⟩)) |
| 75 | simp only [g, Equiv.symm_apply_apply] |
| 76 | exact hr |
| 77 | · have liftPath : ∀ {a b : V} (h : Relation.ReflTransGen S.Step a b) |
| 78 | (ha : S.Reachable a) (hb : S.Reachable b), |
| 79 | Relation.ReflTransGen G.Step (e ⟨a, ha⟩) (e ⟨b, hb⟩) := by |
| 80 | intro a b h |
| 81 | induction h with |
| 82 | | refl => intro ha hb; exact .refl |
| 83 | | @tail b c h hbc ih => |
| 84 | intro ha hc |
| 85 | have hb : S.Reachable b := by |
| 86 | obtain ⟨r, hr, hp⟩ := ha |
| 87 | exact ⟨r, hr, hp.trans h⟩ |
| 88 | apply Relation.ReflTransGen.tail (ih ha hb) |
| 89 | obtain ⟨d, hd⟩ := hbc |
| 90 | exact ⟨d, by simpa [G, g] using hd⟩ |
| 91 | simpa using liftPath hp rr (e.symm v).property |
| 92 | |
| 93 | def SetSystem.Deterministic {A : RankedSet} {n : ℕ} (S : SetSystem A n) : Prop := |
| 94 | (∃ i, S.graph.initial = {i}) ∧ S.graph.root = ∅ ∧ |
| 95 | ∀ v d, d < (S.graph.label v).1 → ∃! t, S.graph.edge v d t |
| 96 | |
| 97 | abbrev System (A : RankedSet) (n : ℕ) := {S : SetSystem A n // S.Deterministic} |
| 98 | |
| 99 | def relabel {A B : RankedSet} (f : RankedMap A B) {n : ℕ} |
| 100 | (S : SetSystem A n) : SetSystem B n where |
| 101 | size := S.size |
| 102 | graph := { S.graph with label := fun v => ⟨(S.graph.label v).1, |
| 103 | f _ (S.graph.label v).2⟩ } |
| 104 | reachable := S.reachable |
| 105 | |
| 106 | def relabelSystem {A B : RankedSet} (f : RankedMap A B) {n : ℕ} |
| 107 | (S : System A n) : System B n := ⟨relabel f S.val, S.property⟩ |
| 108 | |
| 109 | def atomic {A : RankedSet} {n : ℕ} (a : A n) : SetSystem A n where |
| 110 | size := 1 |
| 111 | graph := { |
| 112 | label := fun _ => ⟨n, a⟩ |
| 113 | initial := Set.univ |
| 114 | root := ∅ |
| 115 | edge := fun _ d t => ∃ i : Fin n, d = i.val ∧ t = Sum.inr i |
| 116 | direction_valid := by rintro _ _ _ ⟨i, rfl, rfl⟩; exact i.isLt } |
| 117 | reachable := fun v => ⟨v, Or.inl (Set.mem_univ v), .refl⟩ |
| 118 | |
| 119 | def atomicSystem {A : RankedSet} {n : ℕ} (a : A n) : System A n := |
| 120 | ⟨atomic a, by |
| 121 | change (∃ i : Fin 1, Set.univ = {i}) ∧ (∅ : Set (Fin 1)) = ∅ ∧ _ |
| 122 | refine ⟨⟨0, by ext v; simp [Subsingleton.elim v 0]⟩, rfl, ?_⟩ |
| 123 | intro v d hd |
| 124 | refine ⟨Sum.inr ⟨d, hd⟩, ⟨⟨d, hd⟩, rfl, rfl⟩, ?_⟩ |
| 125 | rintro t ⟨i, hi, rfl⟩ |
| 126 | congr 1 |
| 127 | exact Fin.ext hi.symm⟩ |
| 128 | |
| 129 | noncomputable def uproot {A : RankedSet} {n : ℕ} (S : SetSystem A n) : SetSystem A n := |
| 130 | trim { S.graph with initial := S.graph.root, root := ∅ } |
| 131 | |
| 132 | def plant {A : RankedSet} {n : ℕ} (S : SetSystem A n) : SetSystem A n where |
| 133 | size := S.size |
| 134 | graph := { S.graph with initial := ∅, root := S.graph.root ∪ S.graph.initial } |
| 135 | reachable := by |
| 136 | intro v |
| 137 | obtain ⟨r, hr, hp⟩ := S.reachable v |
| 138 | exact ⟨r, Or.inr (hr.elim Or.inr Or.inl), hp⟩ |
| 139 | |
| 140 | noncomputable def sum {A : RankedSet} {n : ℕ} (S T : SetSystem A n) : SetSystem A n := |
| 141 | trim { |
| 142 | label := Sum.elim S.graph.label T.graph.label |
| 143 | initial := Sum.elim S.graph.initial T.graph.initial |
| 144 | root := Sum.elim S.graph.root T.graph.root |
| 145 | edge := fun v d t => match v with |
| 146 | | .inl v => ∃ t', S.graph.edge v d t' ∧ t = Sum.map Sum.inl id t' |
| 147 | | .inr v => ∃ t', T.graph.edge v d t' ∧ t = Sum.map Sum.inr id t' |
| 148 | direction_valid := by |
| 149 | intro v d t h |
| 150 | cases v with |
| 151 | | inl v => obtain ⟨t', ht, _⟩ := h; exact S.graph.direction_valid v d t' ht |
| 152 | | inr v => obtain ⟨t', ht, _⟩ := h; exact T.graph.direction_valid v d t' ht } |
| 153 | |
| 154 | end Lax369799.RankedSystems |
| 155 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments