Symmetric quivers and arrow reversal

This file contains constructions related to symmetric quivers:

• Symmetrify V adds formal inverses to each arrow of V.
• HasReverse is the class of quivers where each arrow has an assigned formal inverse.
• HasInvolutiveReverse extends HasReverse by requiring that the reverse of the reverse is equal to the original arrow.
• Prefunctor.PreserveReverse is the class of prefunctors mapping reverses to reverses.
• Symmetrify.of, Symmetrify.lift, and the associated lemmas witness the universal property of Symmetrify.

def Quiver.Symmetrify (V : Type u_1) : Type u_1

A type synonym for the symmetrized quiver (with an arrow both ways for each original arrow). NB: this does not work for Prop-valued quivers. It requires [Quiver.{v+1} V].

Equations

• Quiver.Symmetrify V = V

instance Quiver.symmetrifyQuiver (V : Type u) [Quiver V] : Quiver (Quiver.Symmetrify V)

Equations

• Quiver.symmetrifyQuiver V = { Hom := fun a b => (a ⟶ b) ⊕ (b ⟶ a) }

class Quiver.HasReverse (V : Type u_2) [Quiver V] : Type (max u_2 v)

• reverse' : {a b : V} → (a ⟶ b) → (b ⟶ a)

  the map which sends an arrow to its reverse

A quiver HasReverse if we can reverse an arrow p from a to b to get an arrow p.reverse from b to a.

def Quiver.reverse {V : Type u_4} [Quiver V] [Quiver.HasReverse V] {a : V} {b : V} : (a ⟶ b) → (b ⟶ a)

Reverse the direction of an arrow.

Equations

• Quiver.reverse = Quiver.HasReverse.reverse'

class Quiver.HasInvolutiveReverse (V : Type u_2) [Quiver V] extends Quiver.HasReverse : Type (max u_2 v)

• reverse' : {a b : V} → (a ⟶ b) → (b ⟶ a)
• inv' : ∀ {a b : V} (f : a ⟶ b), Quiver.reverse (Quiver.reverse f) = f

  reverse is involutive

A quiver HasInvolutiveReverse if reversing twice is the identity.

@[simp]

theorem Quiver.reverse_reverse {V : Type u_2} [Quiver V] [h : Quiver.HasInvolutiveReverse V] {a : V} {b : V} (f : a ⟶ b) : Quiver.reverse (Quiver.reverse f) = f

@[simp]

theorem Quiver.reverse_inj {V : Type u_2} [Quiver V] [h : Quiver.HasInvolutiveReverse V] {a : V} {b : V} (f : a ⟶ b) (g : a ⟶ b) : Quiver.reverse f = Quiver.reverse g ↔ f = g

theorem Quiver.eq_reverse_iff {V : Type u_2} [Quiver V] [h : Quiver.HasInvolutiveReverse V] {a : V} {b : V} (f : a ⟶ b) (g : b ⟶ a) : f = Quiver.reverse g ↔ Quiver.reverse f = g

class Prefunctor.MapReverse {U : Type u_1} {V : Type u_2} [Quiver U] [Quiver V] [Quiver.HasReverse U] [Quiver.HasReverse V] (φ : U ⥤q V) : Prop

• map_reverse' : ∀ {u v : U} (e : u ⟶ v), φ.map (Quiver.reverse e) = Quiver.reverse (φ.map e)

  The image of a reverse is the reverse of the image.

A prefunctor preserving reversal of arrows

@[simp]

theorem Prefunctor.map_reverse {U : Type u_1} {V : Type u_2} [Quiver U] [Quiver V] [Quiver.HasReverse U] [Quiver.HasReverse V] (φ : U ⥤q V) [Prefunctor.MapReverse φ] {u : U} {v : U} (e : u ⟶ v) : φ.map (Quiver.reverse e) = Quiver.reverse (φ.map e)

instance Prefunctor.mapReverseComp {U : Type u_1} {V : Type u_2} {W : Type u_3} [Quiver U] [Quiver V] [Quiver W] [Quiver.HasReverse U] [Quiver.HasReverse V] [Quiver.HasReverse W] (φ : U ⥤q V) (ψ : V ⥤q W) [Prefunctor.MapReverse φ] [Prefunctor.MapReverse ψ] : Prefunctor.MapReverse (φ ⋙q ψ)

Equations

• @Prefunctor.mapReverseComp = @Prefunctor.mapReverseComp.proof_1

instance Prefunctor.mapReverseId {U : Type u_1} [Quiver U] [Quiver.HasReverse U] : Prefunctor.MapReverse (𝟭q U)

Equations

• @Prefunctor.mapReverseId = @Prefunctor.mapReverseId.proof_1

instance Quiver.instHasReverseSymmetrifySymmetrifyQuiver {V : Type u_2} [Quiver V] : Quiver.HasReverse (Quiver.Symmetrify V)

Equations

• Quiver.instHasReverseSymmetrifySymmetrifyQuiver = { reverse' := fun {a b} e => Sum.swap e }

instance Quiver.instHasInvolutiveReverseSymmetrifySymmetrifyQuiver {V : Type u_2} [Quiver V] : Quiver.HasInvolutiveReverse (Quiver.Symmetrify V)

Equations

• Quiver.instHasInvolutiveReverseSymmetrifySymmetrifyQuiver = Quiver.HasInvolutiveReverse.mk (_ : ∀ {a b : Quiver.Symmetrify V} (e : a ⟶ b), (Sum.swap ∘ Sum.swap) e = id e)

@[simp]

theorem Quiver.symmetrify_reverse {V : Type u_2} [Quiver V] {a : Quiver.Symmetrify V} {b : Quiver.Symmetrify V} (e : a ⟶ b) : Quiver.reverse e = Sum.swap e

@[inline, reducible]

abbrev Quiver.Hom.toPos {V : Type u_2} [Quiver V] {X : V} {Y : V} (f : X ⟶ Y) : X ⟶ Y

Shorthand for the "forward" arrow corresponding to f in symmetrify V

Equations

• Quiver.Hom.toPos f = Sum.inl f

@[inline, reducible]

abbrev Quiver.Hom.toNeg {V : Type u_2} [Quiver V] {X : V} {Y : V} (f : X ⟶ Y) : Y ⟶ X

Shorthand for the "backward" arrow corresponding to f in symmetrify V

Equations

• Quiver.Hom.toNeg f = Sum.inr f

def Quiver.Path.reverse {V : Type u_2} [Quiver V] [Quiver.HasReverse V] {a : V} {b : V} : Quiver.Path a b → Quiver.Path b a

Reverse the direction of a path.

Equations

• Quiver.Path.reverse Quiver.Path.nil = Quiver.Path.nil
• Quiver.Path.reverse (Quiver.Path.cons p e) = Quiver.Path.comp (Quiver.Hom.toPath (Quiver.reverse e)) (Quiver.Path.reverse p)

@[simp]

theorem Quiver.Path.reverse_toPath {V : Type u_2} [Quiver V] [Quiver.HasReverse V] {a : V} {b : V} (f : a ⟶ b) : Quiver.Path.reverse (Quiver.Hom.toPath f) = Quiver.Hom.toPath (Quiver.reverse f)

@[simp]

theorem Quiver.Path.reverse_comp {V : Type u_2} [Quiver V] [Quiver.HasReverse V] {a : V} {b : V} {c : V} (p : Quiver.Path a b) (q : Quiver.Path b c) : Quiver.Path.reverse (Quiver.Path.comp p q) = Quiver.Path.comp (Quiver.Path.reverse q) (Quiver.Path.reverse p)

@[simp]

theorem Quiver.Path.reverse_reverse {V : Type u_2} [Quiver V] [h : Quiver.HasInvolutiveReverse V] {a : V} {b : V} (p : Quiver.Path a b) : Quiver.Path.reverse (Quiver.Path.reverse p) = p

def Quiver.Symmetrify.of {V : Type u_2} [Quiver V] : V ⥤q Quiver.Symmetrify V

The inclusion of a quiver in its symmetrification

Equations

• Quiver.Symmetrify.of = { obj := id, map := fun {X Y} => Sum.inl }

def Quiver.Symmetrify.lift {V : Type u_2} [Quiver V] {V' : Type u_4} [Quiver V'] [Quiver.HasReverse V'] (φ : V ⥤q V') : Quiver.Symmetrify V ⥤q V'

Given a quiver V' with reversible arrows, a prefunctor to V' can be lifted to one from Symmetrify V to V'

Equations

• Quiver.Symmetrify.lift φ = { obj := φ.obj, map := fun {X Y} f => match f with | Sum.inl g => φ.map g | Sum.inr g => Quiver.reverse (φ.map g) }

theorem Quiver.Symmetrify.lift_spec {V : Type u_2} [Quiver V] {V' : Type u_4} [Quiver V'] [Quiver.HasReverse V'] (φ : V ⥤q V') : Quiver.Symmetrify.of ⋙q Quiver.Symmetrify.lift φ = φ

theorem Quiver.Symmetrify.lift_reverse {V : Type u_2} [Quiver V] {V' : Type u_4} [Quiver V'] [h : Quiver.HasInvolutiveReverse V'] (φ : V ⥤q V') {X : Quiver.Symmetrify V} {Y : Quiver.Symmetrify V} (f : X ⟶ Y) : (Quiver.Symmetrify.lift φ).map (Quiver.reverse f) = Quiver.reverse ((Quiver.Symmetrify.lift φ).map f)

theorem Quiver.Symmetrify.lift_unique {V : Type u_2} [Quiver V] {V' : Type u_4} [Quiver V'] [Quiver.HasReverse V'] (φ : V ⥤q V') (Φ : Quiver.Symmetrify V ⥤q V') (hΦ : Quiver.Symmetrify.of ⋙q Φ = φ) (hΦinv : ∀ {X Y : Quiver.Symmetrify V} (f : X ⟶ Y), Φ.map (Quiver.reverse f) = Quiver.reverse (Φ.map f)) : Φ = Quiver.Symmetrify.lift φ

lift φ is the only prefunctor extending φ and preserving reverses.

@[simp]

theorem Prefunctor.symmetrify_map {U : Type u_1} {V : Type u_2} [Quiver U] [Quiver V] (φ : U ⥤q V) : ∀ {X Y : Quiver.Symmetrify U} (a : (X ⟶ Y) ⊕ (Y ⟶ X)), (Prefunctor.symmetrify φ).map a = Sum.map φ.map φ.map a

@[simp]

theorem Prefunctor.symmetrify_obj {U : Type u_1} {V : Type u_2} [Quiver U] [Quiver V] (φ : U ⥤q V) : ∀ (a : U), (Prefunctor.symmetrify φ).obj a = φ.obj a

def Prefunctor.symmetrify {U : Type u_1} {V : Type u_2} [Quiver U] [Quiver V] (φ : U ⥤q V) : Quiver.Symmetrify U ⥤q Quiver.Symmetrify V

A prefunctor canonically defines a prefunctor of the symmetrifications.

Equations

• Prefunctor.symmetrify φ = { obj := φ.obj, map := fun {X Y} => Sum.map φ.map φ.map }

instance Prefunctor.symmetrify_mapReverse {U : Type u_1} {V : Type u_2} [Quiver U] [Quiver V] (φ : U ⥤q V) : Prefunctor.MapReverse (Prefunctor.symmetrify φ)

Equations

• @Prefunctor.symmetrify_mapReverse = @Prefunctor.symmetrify_mapReverse.proof_1

instance Quiver.Push.instHasReversePushInstQuiverPush {V : Type u_2} [Quiver V] {V' : Type u_4} (σ : V → V') [Quiver.HasReverse V] : Quiver.HasReverse (Quiver.Push σ)

Equations

• One or more equations did not get rendered due to their size.

instance Quiver.Push.instHasInvolutiveReversePushInstQuiverPush {V : Type u_2} [Quiver V] {V' : Type u_4} (σ : V → V') [h : Quiver.HasInvolutiveReverse V] : Quiver.HasInvolutiveReverse (Quiver.Push σ)

Equations

• Quiver.Push.instHasInvolutiveReversePushInstQuiverPush σ = Quiver.HasInvolutiveReverse.mk (_ : ∀ {a b : Quiver.Push σ} (x : a ⟶ b), Quiver.reverse (Quiver.reverse x) = x)

theorem Quiver.Push.of_reverse {V : Type u_2} [Quiver V] {V' : Type u_4} (σ : V → V') [Quiver.HasInvolutiveReverse V] (X : V) (Y : V) (f : X ⟶ Y) : Quiver.reverse ((Quiver.Push.of σ).map f) = (Quiver.Push.of σ).map (Quiver.reverse f)

instance Quiver.Push.ofMapReverse {V : Type u_2} [Quiver V] {V' : Type u_4} (σ : V → V') [h : Quiver.HasInvolutiveReverse V] : Prefunctor.MapReverse (Quiver.Push.of σ)

Equations

• @Quiver.Push.ofMapReverse = @Quiver.Push.ofMapReverse.proof_1

def Quiver.IsPreconnected (V : Type u_4) [Quiver V] : Prop

A quiver is preconnected iff there exists a path between any pair of vertices. Note that if V doesn't HasReverse, then the definition is stronger than simply having a preconnected underlying SimpleGraph, since a path in one direction doesn't induce one in the other.

Equations

• Quiver.IsPreconnected V = ∀ (X Y : V), Nonempty (Quiver.Path X Y)