Paths in quivers

Given a quiver V, we define the type of paths from a : V to b : V as an inductive family. We define composition of paths and the action of prefunctors on paths.

We also define Quiver.Reachable a b, the existence of a directed path from a to b.

inductive Quiver.Path {V : Type u} [Quiver V] (a : V) : V → Type (max u v)

Path a b is the type of paths from a to b through the arrows of G.

• nil {V : Type u} [Quiver V] {a : V} : Path a a
• cons {V : Type u} [Quiver V] {a b c : V} : Path a b → (b ⟶ c) → Path a c

def Quiver.Hom.toPath {V : Type u_1} [Quiver V] {a b : V} (e : a ⟶ b) : Path a b

An arrow viewed as a path of length one.

theorem Quiver.Path.nil_ne_cons {V : Type u} [Quiver V] {a b : V} (p : Path a b) (e : b ⟶ a) : nil ≠ p.cons e

theorem Quiver.Path.cons_ne_nil {V : Type u} [Quiver V] {a b : V} (p : Path a b) (e : b ⟶ a) : p.cons e ≠ nil

theorem Quiver.Path.obj_eq_of_cons_eq_cons {V : Type u} [Quiver V] {a b c d : V} {p : Path a b} {p' : Path a c} {e : b ⟶ d} {e' : c ⟶ d} (h : p.cons e = p'.cons e') : b = c

theorem Quiver.Path.heq_of_cons_eq_cons {V : Type u} [Quiver V] {a b c d : V} {p : Path a b} {p' : Path a c} {e : b ⟶ d} {e' : c ⟶ d} (h : p.cons e = p'.cons e') : p ≍ p'

theorem Quiver.Path.hom_heq_of_cons_eq_cons {V : Type u} [Quiver V] {a b c d : V} {p : Path a b} {p' : Path a c} {e : b ⟶ d} {e' : c ⟶ d} (h : p.cons e = p'.cons e') : e ≍ e'

def Quiver.Path.length {V : Type u} [Quiver V] {a b : V} : Path a b → ℕ

The length of a path is the number of arrows it uses.

@[instance_reducible]

instance Quiver.Path.instInhabited {V : Type u} [Quiver V] {a : V} : Inhabited (Path a a)

@[simp]

theorem Quiver.Path.length_nil {V : Type u} [Quiver V] {a : V} : nil.length = 0

@[simp]

theorem Quiver.Path.length_cons {V : Type u} [Quiver V] (a b c : V) (p : Path a b) (e : b ⟶ c) : (p.cons e).length = p.length + 1

theorem Quiver.Path.eq_of_length_zero {V : Type u} [Quiver V] {a b : V} (p : Path a b) (hzero : p.length = 0) : a = b

theorem Quiver.Path.eq_nil_of_length_zero {V : Type u} [Quiver V] {a : V} (p : Path a a) (hzero : p.length = 0) : p = nil

@[simp]

theorem Quiver.Path.length_toPath {V : Type u} [Quiver V] {a b : V} (e : a ⟶ b) : e.toPath.length = 1

def Quiver.Path.comp {V : Type u} [Quiver V] {a b c : V} : Path a b → Path b c → Path a c

Composition of paths.

@[simp]

theorem Quiver.Path.comp_cons {V : Type u} [Quiver V] {a b c d : V} (p : Path a b) (q : Path b c) (e : c ⟶ d) : p.comp (q.cons e) = (p.comp q).cons e

@[simp]

theorem Quiver.Path.comp_nil {V : Type u} [Quiver V] {a b : V} (p : Path a b) : p.comp nil = p

@[simp]

theorem Quiver.Path.nil_comp {V : Type u} [Quiver V] {a b : V} (p : Path a b) : nil.comp p = p

@[simp]

theorem Quiver.Path.comp_assoc {V : Type u} [Quiver V] {a b c d : V} (p : Path a b) (q : Path b c) (r : Path c d) : (p.comp q).comp r = p.comp (q.comp r)

@[simp]

theorem Quiver.Path.length_comp {V : Type u} [Quiver V] {a b : V} (p : Path a b) {c : V} (q : Path b c) : (p.comp q).length = p.length + q.length

theorem Quiver.Path.comp_inj {V : Type u} [Quiver V] {a b c : V} {p₁ p₂ : Path a b} {q₁ q₂ : Path b c} (hq : q₁.length = q₂.length) : p₁.comp q₁ = p₂.comp q₂ ↔ p₁ = p₂ ∧ q₁ = q₂

theorem Quiver.Path.comp_inj' {V : Type u} [Quiver V] {a b c : V} {p₁ p₂ : Path a b} {q₁ q₂ : Path b c} (h : p₁.length = p₂.length) : p₁.comp q₁ = p₂.comp q₂ ↔ p₁ = p₂ ∧ q₁ = q₂

theorem Quiver.Path.comp_injective_left {V : Type u} [Quiver V] {a b c : V} (q : Path b c) : Function.Injective fun (p : Path a b) => p.comp q

theorem Quiver.Path.comp_injective_right {V : Type u} [Quiver V] {a b c : V} (p : Path a b) : Function.Injective p.comp

@[simp]

theorem Quiver.Path.comp_inj_left {V : Type u} [Quiver V] {a b c : V} {p₁ p₂ : Path a b} {q : Path b c} : p₁.comp q = p₂.comp q ↔ p₁ = p₂

@[simp]

theorem Quiver.Path.comp_inj_right {V : Type u} [Quiver V] {a b c : V} {p : Path a b} {q₁ q₂ : Path b c} : p.comp q₁ = p.comp q₂ ↔ q₁ = q₂

theorem Quiver.Path.eq_toPath_comp_of_length_eq_succ {V : Type u} [Quiver V] {a b : V} (p : Path a b) {n : ℕ} (hp : p.length = n + 1) : ∃ (c : V), ∃ (f : a ⟶ c), ∃ (q : Path c b), ∃ (x : q.length = n), p = f.toPath.comp q

theorem Quiver.Path.length_ne_zero_iff_eq_comp {V : Type u_1} [Quiver V] {a b : V} (p : Path a b) : p.length ≠ 0 ↔ ∃ (c : V), ∃ (e : a ⟶ c), ∃ (p' : Path c b), p = e.toPath.comp p' ∧ p.length = p'.length + 1

theorem Quiver.Path.length_ne_zero_iff_eq_cons {V : Type u_1} [Quiver V] {a b : V} (p : Path a b) : p.length ≠ 0 ↔ ∃ (c : V), ∃ (p' : Path a c), ∃ (e : c ⟶ b), p = p'.cons e

Every non-empty path can be decomposed as an initial path plus a final edge.

@[simp]

theorem Quiver.Path.comp_toPath_eq_cons {V : Type u_1} [Quiver V] {a b c : V} (p : Path a b) (e : b ⟶ c) : p.comp e.toPath = p.cons e

def Quiver.Path.toList {V : Type u} [Quiver V] {a b : V} : Path a b → List V

Turn a path into a list. The list contains a at its head, but not b a priori.

@[simp]

theorem Quiver.Path.toList_comp {V : Type u} [Quiver V] {a b : V} (p : Path a b) {c : V} (q : Path b c) : (p.comp q).toList = q.toList ++ p.toList

Quiver.Path.toList is a contravariant functor. The inversion comes from Quiver.Path and List having different preferred directions for adding elements.

theorem Quiver.Path.isChain_toList_nonempty {V : Type u} [Quiver V] {a b : V} (p : Path a b) : List.IsChain (fun (x y : V) => Nonempty (y ⟶ x)) p.toList

theorem Quiver.Path.isChain_cons_toList_nonempty {V : Type u} [Quiver V] {a b : V} (p : Path a b) : List.IsChain (fun (x y : V) => Nonempty (y ⟶ x)) (b :: p.toList)

theorem Quiver.Path.toList_injective {V : Type u} [Quiver V] [∀ (a b : V), Subsingleton (a ⟶ b)] (a b : V) : Function.Injective toList

@[simp]

theorem Quiver.Path.toList_inj {V : Type u} [Quiver V] {a b : V} [∀ (a b : V), Subsingleton (a ⟶ b)] {p q : Path a b} : p.toList = q.toList ↔ p = q

def Quiver.Path.BoundedPaths {V : Type u_1} [Quiver V] (v w : V) (n : ℕ) : Type (max 0 u_1 u_2)

A bounded path is a path with a uniform bound on its length.

instance Quiver.Path.instSubsingletonBddPaths {V : Type u_1} [Quiver V] (v w : V) : Subsingleton (BoundedPaths v w 0)

Bounded paths of length zero between two vertices form a subsingleton.

def Quiver.Path.decidableEqBddPathsZero {V : Type u_1} [Quiver V] (v w : V) : DecidableEq (BoundedPaths v w 0)

Bounded paths of length zero between two vertices have decidable equality.

def Quiver.Path.decidableEqBddPathsOfDecidableEq {V : Type u_1} [Quiver V] (n : ℕ) (h₁ : DecidableEq V) (h₂ : (v w : V) → DecidableEq (v ⟶ w)) (h₃ : (v w : V) → DecidableEq (BoundedPaths v w n)) (v w : V) : DecidableEq (BoundedPaths v w (n + 1))

Given decidable equality on paths of length up to n, we can construct decidable equality on paths of length up to n + 1.

@[instance_reducible]

instance Quiver.Path.decidableEqBoundedPaths {V : Type u_1} [Quiver V] [DecidableEq V] [(v w : V) → DecidableEq (v ⟶ w)] (n : ℕ) (v w : V) : DecidableEq (BoundedPaths v w n)

Equality is decidable on all uniformly bounded paths given decidable equality on the vertices and the arrows.

@[instance_reducible]

instance Quiver.Path.instDecidableEq {V : Type u_1} [Quiver V] [DecidableEq V] [(v w : V) → DecidableEq (v ⟶ w)] (v w : V) : DecidableEq (Path v w)

Equality is decidable on paths in a quiver given decidable equality on the vertices and arrows.

def Quiver.Reachable {V : Type u} [Quiver V] (a b : V) : Prop

Reachable a b holds when there is a directed path from a to b.

This is a preorder rather than an equivalence, since quiver paths are directed (compare the symmetric SimpleGraph.Reachable).

theorem Quiver.Reachable.elim {V : Type u} [Quiver V] {a b : V} {p : Prop} (h : Reachable a b) (hp : ∀ (a : Path a b), p) : p

theorem Quiver.Reachable.refl {V : Type u} [Quiver V] (a : V) : Reachable a a

@[simp]

theorem Quiver.Reachable.rfl {V : Type u} [Quiver V] {a : V} : Reachable a a

theorem Quiver.Reachable.trans {V : Type u} [Quiver V] {a b c : V} (hab : Reachable a b) (hbc : Reachable b c) : Reachable a c

instance Quiver.instIsPreorderReachable {V : Type u} [Quiver V] : IsPreorder V Reachable

theorem Quiver.Path.reachable {V : Type u} [Quiver V] {a b : V} (p : Path a b) : Reachable a b

A path witnesses that its target is reachable from its source.

theorem Quiver.Hom.reachable {V : Type u} [Quiver V] {a b : V} (e : a ⟶ b) : Reachable a b

An arrow witnesses that its target is reachable from its source.

def Prefunctor.mapPath {V : Type u₁} [Quiver V] {W : Type u₂} [Quiver W] (F : V ⥤q W) {a b : V} : Quiver.Path a b → Quiver.Path (F.obj a) (F.obj b)

The image of a path under a prefunctor.

@[simp]

theorem Prefunctor.mapPath_nil {V : Type u₁} [Quiver V] {W : Type u₂} [Quiver W] (F : V ⥤q W) (a : V) : F.mapPath Quiver.Path.nil = Quiver.Path.nil

@[simp]

theorem Prefunctor.mapPath_cons {V : Type u₁} [Quiver V] {W : Type u₂} [Quiver W] (F : V ⥤q W) {a b c : V} (p : Quiver.Path a b) (e : b ⟶ c) : F.mapPath (p.cons e) = (F.mapPath p).cons (F.map e)

@[simp]

theorem Prefunctor.mapPath_comp {V : Type u₁} [Quiver V] {W : Type u₂} [Quiver W] (F : V ⥤q W) {a b : V} (p : Quiver.Path a b) {c : V} (q : Quiver.Path b c) : F.mapPath (p.comp q) = (F.mapPath p).comp (F.mapPath q)

@[simp]

theorem Prefunctor.mapPath_toPath {V : Type u₁} [Quiver V] {W : Type u₂} [Quiver W] (F : V ⥤q W) {a b : V} (f : a ⟶ b) : F.mapPath f.toPath = (F.map f).toPath

@[simp]

theorem Prefunctor.mapPath_id {V : Type u₁} [Quiver V] {a b : V} (p : Quiver.Path a b) : (𝟭q V).mapPath p = p

@[simp]

theorem Prefunctor.mapPath_comp_apply {V : Type u₁} [Quiver V] {W : Type u₂} [Quiver W] (F : V ⥤q W) {U : Type u₃} [Quiver U] (G : W ⥤q U) {a b : V} (p : Quiver.Path a b) : (F ⋙q G).mapPath p = G.mapPath (F.mapPath p)