While this submission is a draft, it cannot be used by other submissions.

Ranked sets, set-systems, and systems

Lax369799.RankedSystems · concepts/Lax369799/RankedSystems.lean · lax-369799

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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 (FinitePresentationsFinitePresentations) and requires all output variables of a deterministic system to be reachable (SupportedSystemsSupportedSystems). Finite vertex sets are enumerated by FinsizeFin size; directions and variables use zero-based indices. PresentationPresentation allows an arbitrary finite vertex type when constructing these objects.

    Concept map
    1 concept
    100%
    DefinitionThis conceptDescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Mathlib.Data.Fintype.EquivFin
    2import Mathlib.Data.Fintype.Sum
    3import Mathlib.Data.Fintype.Sigma
    4import Mathlib.Logic.Relation
    5import Mathlib.Data.Set.Finite.Basic
    6
    7/-!
    8---
    9title: Ranked sets, set-systems, and systems
    10type: definition
    11---
    12A ranked set is a family of sets indexed by natural numbers. A set-system
    13has finitely many labelled vertices, initial and root vertices, and edges
    14with a direction and either a vertex or a variable as target. Every vertex
    15is reachable from an initial or root vertex. A system has one initial
    16vertex, no roots, and exactly one successor in every available direction.
    17
    18This is the earlier reachable interface. The revised Section 2.2 allows
    19unreachable vertices in set-systems (`FinitePresentations`) and requires
    20all 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`
    23allows an arbitrary finite vertex type when constructing these objects.
    24-/
    25
    26namespace Lax369799.RankedSystems
    27
    28abbrev RankedSet := ℕ → Type
    29abbrev Symbol (A : RankedSet) := (n : ℕ) × A n
    30abbrev RankedMap (A B : RankedSet) := ∀ n, A n → B n
    31
    32def RankwiseFinite (A : RankedSet) : Prop := ∀ n, Finite (A n)
    33
    34structure 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
    41def 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
    45def 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
    49structure SetSystem (A : RankedSet) (n : ℕ) where
    50 size : ℕ
    51 graph : Presentation A n (Fin size)
    52 reachable : ∀ v, graph.Reachable v
    53
    54abbrev SetSystem.Vertex {A : RankedSet} {n : ℕ} (S : SetSystem A n) := Fin S.size
    55
    56/-- Restrict to reachable vertices and enumerate the resulting finite set. -/
    57noncomputable 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
    93def 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
    97abbrev System (A : RankedSet) (n : ℕ) := {S : SetSystem A n // S.Deterministic}
    98
    99def 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
    106def relabelSystem {A B : RankedSet} (f : RankedMap A B) {n : ℕ}
    107 (S : System A n) : System B n := ⟨relabel f S.val, S.property⟩
    108
    109def 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
    119def 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
    129noncomputable def uproot {A : RankedSet} {n : ℕ} (S : SetSystem A n) : SetSystem A n :=
    130 trim { S.graph with initial := S.graph.root, root := ∅ }
    131
    132def 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
    140noncomputable 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
    154end Lax369799.RankedSystems
    155

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…