mathlib documentation

category_theory.limits.shapes.equalizers

Equalizers and coequalizers #

This file defines (co)equalizers as special cases of (co)limits.

An equalizer is the categorical generalization of the subobject {a ∈ A | f(a) = g(a)} known from abelian groups or modules. It is a limit cone over the diagram formed by f and g.

A coequalizer is the dual concept.

Main definitions #

Each of these has a dual.

Main statements #

Implementation notes #

As with the other special shapes in the limits library, all the definitions here are given as abbreviations of the general statements for limits, so all the simp lemmas and theorems about general limits can be used.

References #

@[protected, instance]
Equations

The functor walking_parallel_pair ⥤ walking_parallel_pairᵒᵖ sending left to left and right to right.

Equations

The equivalence walking_parallel_pair ⥤ walking_parallel_pairᵒᵖ sending left to left and right to right.

Equations

parallel_pair f g is the diagram in C consisting of the two morphisms f and g with common domain and codomain.

Equations
Instances for category_theory.limits.parallel_pair
def category_theory.limits.parallel_pair_hom {C : Type u} [category_theory.category C] {X Y X' Y' : C} (f g : X Y) (f' g' : X' Y') (p : X X') (q : Y Y') (wf : f q = p f') (wg : g q = p g') :

Construct a morphism between parallel pairs.

Equations
@[simp]
theorem category_theory.limits.parallel_pair_hom_app_zero {C : Type u} [category_theory.category C] {X Y X' Y' : C} (f g : X Y) (f' g' : X' Y') (p : X X') (q : Y Y') (wf : f q = p f') (wg : g q = p g') :
@[simp]
theorem category_theory.limits.parallel_pair_hom_app_one {C : Type u} [category_theory.category C] {X Y X' Y' : C} (f g : X Y) (f' g' : X' Y') (p : X X') (q : Y Y') (wf : f q = p f') (wg : g q = p g') :
@[simp]
theorem category_theory.limits.parallel_pair.eq_of_hom_eq_inv_app {C : Type u} [category_theory.category C] {X Y : C} {f g f' g' : X Y} (hf : f = f') (hg : g = g') (X_1 : category_theory.limits.walking_parallel_pair) :
(category_theory.limits.parallel_pair.eq_of_hom_eq hf hg).inv.app X_1 = (category_theory.limits.walking_parallel_pair.rec (category_theory.iso.refl X) (category_theory.iso.refl Y) X_1).inv
@[simp]
theorem category_theory.limits.parallel_pair.eq_of_hom_eq_hom_app {C : Type u} [category_theory.category C] {X Y : C} {f g f' g' : X Y} (hf : f = f') (hg : g = g') (X_1 : category_theory.limits.walking_parallel_pair) :
(category_theory.limits.parallel_pair.eq_of_hom_eq hf hg).hom.app X_1 = (category_theory.limits.walking_parallel_pair.rec (category_theory.iso.refl X) (category_theory.iso.refl Y) X_1).hom
@[reducible]
def category_theory.limits.fork {C : Type u} [category_theory.category C] {X Y : C} (f g : X Y) :
Type (max u v)

A fork on f and g is just a cone (parallel_pair f g).

@[reducible]
def category_theory.limits.cofork {C : Type u} [category_theory.category C] {X Y : C} (f g : X Y) :
Type (max u v)

A cofork on f and g is just a cocone (parallel_pair f g).

A fork t on the parallel pair f g : X ⟶ Y consists of two morphisms t.π.app zero : t.X ⟶ X and t.π.app one : t.X ⟶ Y. Of these, only the first one is interesting, and we give it the shorter name fork.ι t.

Equations
Instances for category_theory.limits.fork.ι

A cofork t on the parallel_pair f g : X ⟶ Y consists of two morphisms t.ι.app zero : X ⟶ t.X and t.ι.app one : Y ⟶ t.X. Of these, only the second one is interesting, and we give it the shorter name cofork.π t.

Equations
@[simp]
theorem category_theory.limits.fork.of_ι_X {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {P : C} (ι : P X) (w : ι f = ι g) :
@[simp]
theorem category_theory.limits.fork.of_ι_π_app {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {P : C} (ι : P X) (w : ι f = ι g) (X_1 : category_theory.limits.walking_parallel_pair) :
(category_theory.limits.fork.of_ι ι w).π.app X_1 = X_1.cases_on ι f)
def category_theory.limits.fork.of_ι {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {P : C} (ι : P X) (w : ι f = ι g) :

A fork on f g : X ⟶ Y is determined by the morphism ι : P ⟶ X satisfying ι ≫ f = ι ≫ g.

Equations
def category_theory.limits.cofork.of_π {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {P : C} (π : Y P) (w : f π = g π) :

A cofork on f g : X ⟶ Y is determined by the morphism π : Y ⟶ P satisfying f ≫ π = g ≫ π.

Equations
@[simp]
theorem category_theory.limits.cofork.of_π_X {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {P : C} (π : Y P) (w : f π = g π) :
@[simp]
theorem category_theory.limits.cofork.of_π_ι_app {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {P : C} (π : Y P) (w : f π = g π) (X_1 : category_theory.limits.walking_parallel_pair) :
(category_theory.limits.cofork.of_π π w).ι.app X_1 = X_1.cases_on (f π) π
@[simp]
theorem category_theory.limits.fork.ι_of_ι {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {P : C} (ι : P X) (w : ι f = ι g) :
@[simp]
theorem category_theory.limits.cofork.π_of_π {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {P : C} (π : Y P) (w : f π = g π) :
@[simp]
theorem category_theory.limits.fork.condition {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (t : category_theory.limits.fork f g) :
t.ι f = t.ι g
@[simp]
theorem category_theory.limits.fork.condition_assoc {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (t : category_theory.limits.fork f g) {X' : C} (f' : Y X') :
t.ι f f' = t.ι g f'
@[simp]
theorem category_theory.limits.cofork.condition {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (t : category_theory.limits.cofork f g) :
f t.π = g t.π
theorem category_theory.limits.fork.equalizer_ext {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (s : category_theory.limits.fork f g) {W : C} {k l : W s.X} (h : k s.ι = l s.ι) (j : category_theory.limits.walking_parallel_pair) :
k s.π.app j = l s.π.app j

To check whether two maps are equalized by both maps of a fork, it suffices to check it for the first map

theorem category_theory.limits.cofork.coequalizer_ext {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (s : category_theory.limits.cofork f g) {W : C} {k l : s.X W} (h : s.π k = s.π l) (j : category_theory.limits.walking_parallel_pair) :
s.ι.app j k = s.ι.app j l

To check whether two maps are coequalized by both maps of a cofork, it suffices to check it for the second map

theorem category_theory.limits.fork.is_limit.hom_ext {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s : category_theory.limits.fork f g} (hs : category_theory.limits.is_limit s) {W : C} {k l : W s.X} (h : k s.ι = l s.ι) :
k = l
theorem category_theory.limits.cofork.is_colimit.hom_ext {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s : category_theory.limits.cofork f g} (hs : category_theory.limits.is_colimit s) {W : C} {k l : s.X W} (h : s.π k = s.π l) :
k = l
@[simp]
@[simp]
theorem category_theory.limits.cofork.is_colimit.π_desc_assoc {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s t : category_theory.limits.cofork f g} (hs : category_theory.limits.is_colimit s) {X' : C} (f' : t.X X') :
s.π hs.desc t f' = t.π f'
def category_theory.limits.fork.is_limit.lift' {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s : category_theory.limits.fork f g} (hs : category_theory.limits.is_limit s) {W : C} (k : W X) (h : k f = k g) :
{l // l s.ι = k}

If s is a limit fork over f and g, then a morphism k : W ⟶ X satisfying k ≫ f = k ≫ g induces a morphism l : W ⟶ s.X such that l ≫ fork.ι s = k.

Equations
def category_theory.limits.cofork.is_colimit.desc' {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s : category_theory.limits.cofork f g} (hs : category_theory.limits.is_colimit s) {W : C} (k : Y W) (h : f k = g k) :
{l // s.π l = k}

If s is a colimit cofork over f and g, then a morphism k : Y ⟶ W satisfying f ≫ k = g ≫ k induces a morphism l : s.X ⟶ W such that cofork.π s ≫ l = k.

Equations
theorem category_theory.limits.fork.is_limit.exists_unique {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s : category_theory.limits.fork f g} (hs : category_theory.limits.is_limit s) {W : C} (k : W X) (h : k f = k g) :
∃! (l : W s.X), l s.ι = k
theorem category_theory.limits.cofork.is_colimit.exists_unique {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s : category_theory.limits.cofork f g} (hs : category_theory.limits.is_colimit s) {W : C} (k : Y W) (h : f k = g k) :
∃! (d : s.X W), s.π d = k
def category_theory.limits.fork.is_limit.mk {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (t : category_theory.limits.fork f g) (lift : Π (s : category_theory.limits.fork f g), s.X t.X) (fac : ∀ (s : category_theory.limits.fork f g), lift s t.ι = s.ι) (uniq : ∀ (s : category_theory.limits.fork f g) (m : s.X t.X), m t.ι = s.ιm = lift s) :

This is a slightly more convenient method to verify that a fork is a limit cone. It only asks for a proof of facts that carry any mathematical content

Equations
@[simp]
theorem category_theory.limits.fork.is_limit.mk_lift {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (t : category_theory.limits.fork f g) (lift : Π (s : category_theory.limits.fork f g), s.X t.X) (fac : ∀ (s : category_theory.limits.fork f g), lift s t.ι = s.ι) (uniq : ∀ (s : category_theory.limits.fork f g) (m : s.X t.X), m t.ι = s.ιm = lift s) (s : category_theory.limits.fork f g) :

This is another convenient method to verify that a fork is a limit cone. It only asks for a proof of facts that carry any mathematical content, and allows access to the same s for all parts.

Equations
def category_theory.limits.cofork.is_colimit.mk {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (t : category_theory.limits.cofork f g) (desc : Π (s : category_theory.limits.cofork f g), t.X s.X) (fac : ∀ (s : category_theory.limits.cofork f g), t.π desc s = s.π) (uniq : ∀ (s : category_theory.limits.cofork f g) (m : t.X s.X), t.π m = s.πm = desc s) :

This is a slightly more convenient method to verify that a cofork is a colimit cocone. It only asks for a proof of facts that carry any mathematical content

Equations

This is another convenient method to verify that a fork is a limit cone. It only asks for a proof of facts that carry any mathematical content, and allows access to the same s for all parts.

Equations
noncomputable def category_theory.limits.fork.is_limit.of_exists_unique {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {t : category_theory.limits.fork f g} (hs : ∀ (s : category_theory.limits.fork f g), ∃! (l : s.X t.X), l t.ι = s.ι) :

Noncomputably make a limit cone from the existence of unique factorizations.

Equations
noncomputable def category_theory.limits.cofork.is_colimit.of_exists_unique {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {t : category_theory.limits.cofork f g} (hs : ∀ (s : category_theory.limits.cofork f g), ∃! (d : t.X s.X), t.π d = s.π) :

Noncomputably make a colimit cocone from the existence of unique factorizations.

Equations
def category_theory.limits.fork.is_limit.hom_iso {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {t : category_theory.limits.fork f g} (ht : category_theory.limits.is_limit t) (Z : C) :
(Z t.X) {h // h f = h g}

Given a limit cone for the pair f g : X ⟶ Y, for any Z, morphisms from Z to its point are in bijection with morphisms h : Z ⟶ X such that h ≫ f = h ≫ g. Further, this bijection is natural in Z: see fork.is_limit.hom_iso_natural. This is a special case of is_limit.hom_iso', often useful to construct adjunctions.

Equations

The bijection of fork.is_limit.hom_iso is natural in Z.

def category_theory.limits.cofork.is_colimit.hom_iso {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {t : category_theory.limits.cofork f g} (ht : category_theory.limits.is_colimit t) (Z : C) :
(t.X Z) {h // f h = g h}

Given a colimit cocone for the pair f g : X ⟶ Y, for any Z, morphisms from the cocone point to Z are in bijection with morphisms h : Y ⟶ Z such that f ≫ h = g ≫ h. Further, this bijection is natural in Z: see cofork.is_colimit.hom_iso_natural. This is a special case of is_colimit.hom_iso', often useful to construct adjunctions.

Equations

The bijection of cofork.is_colimit.hom_iso is natural in Z.

This is a helper construction that can be useful when verifying that a category has all equalizers. Given F : walking_parallel_pair ⥤ C, which is really the same as parallel_pair (F.map left) (F.map right), and a fork on F.map left and F.map right, we get a cone on F.

If you're thinking about using this, have a look at has_equalizers_of_has_limit_parallel_pair, which you may find to be an easier way of achieving your goal.

Equations

This is a helper construction that can be useful when verifying that a category has all coequalizers. Given F : walking_parallel_pair ⥤ C, which is really the same as parallel_pair (F.map left) (F.map right), and a cofork on F.map left and F.map right, we get a cocone on F.

If you're thinking about using this, have a look at has_coequalizers_of_has_colimit_parallel_pair, which you may find to be an easier way of achieving your goal.

Equations

Given F : walking_parallel_pair ⥤ C, which is really the same as parallel_pair (F.map left) (F.map right) and a cone on F, we get a fork on F.map left and F.map right.

Equations

Given F : walking_parallel_pair ⥤ C, which is really the same as parallel_pair (F.map left) (F.map right) and a cocone on F, we get a cofork on F.map left and F.map right.

Equations
def category_theory.limits.fork.mk_hom {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s t : category_theory.limits.fork f g} (k : s.X t.X) (w : k t.ι = s.ι) :
s t

Helper function for constructing morphisms between equalizer forks.

Equations
@[simp]
theorem category_theory.limits.fork.mk_hom_hom {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s t : category_theory.limits.fork f g} (k : s.X t.X) (w : k t.ι = s.ι) :
def category_theory.limits.fork.ext {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s t : category_theory.limits.fork f g} (i : s.X t.X) (w : i.hom t.ι = s.ι) :
s t

To construct an isomorphism between forks, it suffices to give an isomorphism between the cone points and check that it commutes with the ι morphisms.

Equations

Every fork is isomorphic to one of the form fork.of_ι _ _.

Equations
def category_theory.limits.cofork.mk_hom {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s t : category_theory.limits.cofork f g} (k : s.X t.X) (w : s.π k = t.π) :
s t

Helper function for constructing morphisms between coequalizer coforks.

Equations
@[simp]
theorem category_theory.limits.cofork.mk_hom_hom {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s t : category_theory.limits.cofork f g} (k : s.X t.X) (w : s.π k = t.π) :
@[simp]
theorem category_theory.limits.fork.hom_comp_ι {C : Type u} [category_theory.category C] {X Y : C} {g f : X Y} {s t : category_theory.limits.fork f g} (f_1 : s t) :
f_1.hom t.ι = s.ι
@[simp]
theorem category_theory.limits.fork.π_comp_hom {C : Type u} [category_theory.category C] {X Y : C} {g f : X Y} {s t : category_theory.limits.cofork f g} (f_1 : s t) :
s.π f_1.hom = t.π
@[simp]
theorem category_theory.limits.fork.π_comp_hom_assoc {C : Type u} [category_theory.category C] {X Y : C} {g f : X Y} {s t : category_theory.limits.cofork f g} (f_1 : s t) {X' : C} (f' : t.X X') :
s.π f_1.hom f' = t.π f'
def category_theory.limits.cofork.ext {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} {s t : category_theory.limits.cofork f g} (i : s.X t.X) (w : s.π i.hom = t.π) :
s t

To construct an isomorphism between coforks, it suffices to give an isomorphism between the cocone points and check that it commutes with the π morphisms.

Equations

Every cofork is isomorphic to one of the form cofork.of_π _ _.

Equations
@[reducible]
def category_theory.limits.has_equalizer {C : Type u} [category_theory.category C] {X Y : C} (f g : X Y) :
Prop

has_equalizer f g represents a particular choice of limiting cone for the parallel pair of morphisms f and g.

@[reducible]
noncomputable def category_theory.limits.equalizer {C : Type u} [category_theory.category C] {X Y : C} (f g : X Y) [category_theory.limits.has_equalizer f g] :
C

If an equalizer of f and g exists, we can access an arbitrary choice of such by saying equalizer f g.

@[reducible]

If an equalizer of f and g exists, we can access the inclusion equalizer f g ⟶ X by saying equalizer.ι f g.

@[reducible]

An equalizer cone for a parallel pair f and g.

@[reducible]
noncomputable def category_theory.limits.equalizer.lift {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} [category_theory.limits.has_equalizer f g] {W : C} (k : W X) (h : k f = k g) :

A morphism k : W ⟶ X satisfying k ≫ f = k ≫ g factors through the equalizer of f and g via equalizer.lift : W ⟶ equalizer f g.

@[simp]
theorem category_theory.limits.equalizer.lift_ι_assoc {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} [category_theory.limits.has_equalizer f g] {W : C} (k : W X) (h : k f = k g) {X' : C} (f' : X X') :
noncomputable def category_theory.limits.equalizer.lift' {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} [category_theory.limits.has_equalizer f g] {W : C} (k : W X) (h : k f = k g) :

A morphism k : W ⟶ X satisfying k ≫ f = k ≫ g induces a morphism l : W ⟶ equalizer f g satisfying l ≫ equalizer.ι f g = k.

Equations
@[ext]

Two maps into an equalizer are equal if they are are equal when composed with the equalizer map.

@[protected, instance]

An equalizer morphism is a monomorphism

The equalizer morphism in any limit cone is a monomorphism.

def category_theory.limits.id_fork {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (h : f = g) :

The identity determines a cone on the equalizer diagram of f and g if f = g.

Equations

Every equalizer of (f, g), where f = g, is an isomorphism.

The equalizer of (f, g), where f = g, is an isomorphism.

Every equalizer of (f, f) is an isomorphism.

An equalizer that is an epimorphism is an isomorphism.

Two morphisms are equal if there is a fork whose inclusion is epi.

If the equalizer of two morphisms is an epimorphism, then the two morphisms are equal.

@[protected, instance]
@[protected, instance]

The equalizer inclusion for (f, f) is an isomorphism.

The equalizer of a morphism with itself is isomorphic to the source.

Equations
@[reducible]
def category_theory.limits.has_coequalizer {C : Type u} [category_theory.category C] {X Y : C} (f g : X Y) :
Prop

has_coequalizer f g represents a particular choice of colimiting cocone for the parallel pair of morphisms f and g.

@[reducible]
noncomputable def category_theory.limits.coequalizer {C : Type u} [category_theory.category C] {X Y : C} (f g : X Y) [category_theory.limits.has_coequalizer f g] :
C

If a coequalizer of f and g exists, we can access an arbitrary choice of such by saying coequalizer f g.

@[reducible]

If a coequalizer of f and g exists, we can access the corresponding projection by saying coequalizer.π f g.

@[reducible]

An arbitrary choice of coequalizer cocone for a parallel pair f and g.

@[reducible]
noncomputable def category_theory.limits.coequalizer.desc {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} [category_theory.limits.has_coequalizer f g] {W : C} (k : Y W) (h : f k = g k) :

Any morphism k : Y ⟶ W satisfying f ≫ k = g ≫ k factors through the coequalizer of f and g via coequalizer.desc : coequalizer f g ⟶ W.

@[simp]
noncomputable def category_theory.limits.coequalizer.desc' {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} [category_theory.limits.has_coequalizer f g] {W : C} (k : Y W) (h : f k = g k) :

Any morphism k : Y ⟶ W satisfying f ≫ k = g ≫ k induces a morphism l : coequalizer f g ⟶ W satisfying coequalizer.π ≫ g = l.

Equations
@[ext]

Two maps from a coequalizer are equal if they are equal when composed with the coequalizer map

@[protected, instance]

A coequalizer morphism is an epimorphism

The coequalizer morphism in any colimit cocone is an epimorphism.

def category_theory.limits.id_cofork {C : Type u} [category_theory.category C] {X Y : C} {f g : X Y} (h : f = g) :

The identity determines a cocone on the coequalizer diagram of f and g, if f = g.

Equations

The identity on Y is a coequalizer of (f, g), where f = g.

Equations

Every coequalizer of (f, g), where f = g, is an isomorphism.

The coequalizer of (f, g), where f = g, is an isomorphism.

Every coequalizer of (f, f) is an isomorphism.

A coequalizer that is a monomorphism is an isomorphism.

Two morphisms are equal if there is a cofork whose projection is mono.

If the coequalizer of two morphisms is a monomorphism, then the two morphisms are equal.

@[protected, instance]

The coequalizer projection for (f, f) is an isomorphism.

The coequalizer of a morphism with itself is isomorphic to the target.

Equations

The comparison morphism for the equalizer of f,g. This is an isomorphism iff G preserves the equalizer of f,g; see category_theory/limits/preserves/shapes/equalizers.lean

Equations
Instances for category_theory.limits.equalizer_comparison
@[reducible]

has_equalizers represents a choice of equalizer for every pair of morphisms

@[reducible]

has_coequalizers represents a choice of coequalizer for every pair of morphisms

If C has all limits of diagrams parallel_pair f g, then it has all equalizers

If C has all colimits of diagrams parallel_pair f g, then it has all coequalizers

A split mono f equalizes (retraction f ≫ f) and (𝟙 Y). Here we build the cone, and show in is_split_mono_equalizes that it is a limit cone.

Equations

We show that the converse to is_split_mono_equalizes is true: Whenever f equalizes (r ≫ f) and (𝟙 Y), then r is a retraction of f.

Equations

A split epi f coequalizes (f ≫ section_ f) and (𝟙 X). Here we build the cocone, and show in is_split_epi_coequalizes that it is a colimit cocone.

Equations

We show that the converse to is_split_epi_equalizes is true: Whenever f coequalizes (f ≫ s) and (𝟙 X), then s is a section of f.

Equations