Quivers

This module defines quivers. A quiver on a type V of vertices assigns to every pair a b : V of vertices a type a ⟶ b of arrows from a to b. This is a very permissive notion of directed graph.

Implementation notes

Currently Quiver is defined with Hom : V → V → Sort v. This is different from the category theory setup, where we insist that morphisms live in some Type. There's some balance here: it's nice to allow Prop to ensure there are no multiple arrows, but it is also results in error-prone universe signatures when constraints require a Type.

class Quiver (V : Type u) : Type (max u v)

A quiver G on a type V of vertices assigns to every pair a b : V of vertices a type a ⟶ b of arrows from a to b.

For graphs with no repeated edges, one can use Quiver.{0} V, which ensures a ⟶ b : Prop. For multigraphs, one can use Quiver.{v+1} V, which ensures a ⟶ b : Type v.

Because Category will later extend this class, we call the field Hom. Except when constructing instances, you should rarely see this, and use the ⟶ notation instead.

• Hom : V → V → Sort v

  The type of edges/arrows/morphisms between a given source and target.

def «term_⟶_» : Lean.TrailingParserDescr

Notation for the type of edges/arrows/morphisms between a given source and target in a quiver or category.

Equations

• «term_⟶_» = Lean.ParserDescr.trailingNode `«term_⟶_» 10 11 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ⟶ ") (Lean.ParserDescr.cat `term 10))

instance Quiver.opposite {V : Type u_1} [Quiver V] : Quiver Vᵒᵖ

Vᵒᵖ reverses the direction of all arrows of V.

Equations

• Quiver.opposite = { Hom := fun (a b : Vᵒᵖ) => (Opposite.unop b ⟶ Opposite.unop a)ᵒᵖ }

def Quiver.Hom.op {V : Type u_1} [Quiver V] {X Y : V} (f : X ⟶ Y) : Opposite.op Y ⟶ Opposite.op X

The opposite of an arrow in V.

Equations

• f.op = Opposite.op f

def Quiver.Hom.unop {V : Type u_1} [Quiver V] {X Y : Vᵒᵖ} (f : X ⟶ Y) : Opposite.unop Y ⟶ Opposite.unop X

Given an arrow in Vᵒᵖ, we can take the "unopposite" back in V.

Equations

• f.unop = Opposite.unop f

def Quiver.Hom.opEquiv {V : Type u_1} [Quiver V] {X Y : V} : (X ⟶ Y) ≃ (Opposite.op Y ⟶ Opposite.op X)

The bijection (X ⟶ Y) ≃ (op Y ⟶ op X).

Equations

• Quiver.Hom.opEquiv = { toFun := Opposite.op, invFun := Opposite.unop, left_inv := ⋯, right_inv := ⋯ }

@[simp]

theorem Quiver.Hom.opEquiv_apply {V : Type u_1} [Quiver V] {X Y : V} (unop : X ⟶ Y) : Quiver.Hom.opEquiv unop = Opposite.op unop

@[simp]

theorem Quiver.Hom.opEquiv_symm_apply {V : Type u_1} [Quiver V] {X Y : V} (self : (Opposite.unop (Opposite.op X) ⟶ Opposite.unop (Opposite.op Y))ᵒᵖ) : Quiver.Hom.opEquiv.symm self = Opposite.unop self

def Quiver.Empty (V : Type u) : Type u

A type synonym for a quiver with no arrows.

Equations

• Quiver.Empty V = V

instance Quiver.emptyQuiver (V : Type u) : Quiver (Quiver.Empty V)

Equations

• Quiver.emptyQuiver V = { Hom := fun (x x : Quiver.Empty V) => PEmpty.{?u.13} }

@[simp]

theorem Quiver.empty_arrow {V : Type u} (a b : Quiver.Empty V) : (a ⟶ b) = PEmpty.{u}

@[reducible, inline]

abbrev Quiver.IsThin (V : Type u) [Quiver V] : Prop

A quiver is thin if it has no parallel arrows.

Equations

• Quiver.IsThin V = ∀ (a b : V), Subsingleton (a ⟶ b)