Filtered categories

A category is filtered if every finite diagram admits a cocone. We give a simple characterisation of this condition as

1. for every pair of objects there exists another object "to the right",
2. for every pair of parallel morphisms there exists a morphism to the right so the compositions are equal, and
3. there exists some object.

Filtered colimits are often better behaved than arbitrary colimits. See CategoryTheory/Limits/Types for some details.

Filtered categories are nice because colimits indexed by filtered categories tend to be easier to describe than general colimits (and more often preserved by functors).

In this file we show that any functor from a finite category to a filtered category admits a cocone:

• cocone_nonempty [FinCategory J] [IsFiltered C] (F : J ⥤ C) : Nonempty (Cocone F) More generally, for any finite collection of objects and morphisms between them in a filtered category (even if not closed under composition) there exists some object Z receiving maps from all of them, so that all the triangles (one edge from the finite set, two from morphisms to Z) commute. This formulation is often more useful in practice and is available via sup_exists, which takes a finset of objects, and an indexed family (indexed by source and target) of finsets of morphisms.

We also prove the converse of cocone_nonempty as of_cocone_nonempty.

Furthermore, we give special support for two diagram categories: The bowtie and the tulip. This is because these shapes show up in the proofs that forgetful functors of algebraic categories (e.g. MonCat, CommRingCat, ...) preserve filtered colimits.

All of the above API, except for the bowtie and the tulip, is also provided for cofiltered categories.

See also

In CategoryTheory.Limits.FilteredColimitCommutesFiniteLimit we show that filtered colimits commute with finite limits.

There is another characterization of filtered categories, namely that whenever F : J ⥤ C is a functor from a finite category, there is X : C such that Nonempty (limit (F.op ⋙ yoneda.obj X)). This is shown in CategoryTheory.Limits.Filtered.

class CategoryTheory.IsFilteredOrEmpty (C : Type u) [Category.{v, u} C] : Prop

A category IsFilteredOrEmpty if

1. for every pair of objects there exists another object "to the right", and
2. for every pair of parallel morphisms there exists a morphism to the right so the compositions are equal.

• cocone_objs (X Y : C) : ∃ (Z : C) (x : X ⟶ Z) (x : Y ⟶ Z), True

  for every pair of objects there exists another object "to the right"

• cocone_maps ⦃X Y : C⦄ (f g : X ⟶ Y) : ∃ (Z : C) (h : Y ⟶ Z), CategoryStruct.comp f h = CategoryStruct.comp g h

  for every pair of parallel morphisms there exists a morphism to the right so the compositions are equal

class CategoryTheory.IsFiltered (C : Type u) [Category.{v, u} C] extends CategoryTheory.IsFilteredOrEmpty C : Prop

A category IsFiltered if

1. for every pair of objects there exists another object "to the right",
2. for every pair of parallel morphisms there exists a morphism to the right so the compositions are equal, and
3. there exists some object.

• cocone_objs (X Y : C) : ∃ (Z : C) (x : X ⟶ Z) (x : Y ⟶ Z), True
• cocone_maps ⦃X Y : C⦄ (f g : X ⟶ Y) : ∃ (Z : C) (h : Y ⟶ Z), CategoryStruct.comp f h = CategoryStruct.comp g h
• nonempty : Nonempty C

  a filtered category must be non empty

@[instance 100]

instance CategoryTheory.isFilteredOrEmpty_of_semilatticeSup (α : Type u) [SemilatticeSup α] : IsFilteredOrEmpty α

@[instance 100]

instance CategoryTheory.isFiltered_of_semilatticeSup_nonempty (α : Type u) [SemilatticeSup α] [Nonempty α] : IsFiltered α

@[instance 100]

instance CategoryTheory.isFilteredOrEmpty_of_directed_le (α : Type u) [Preorder α] [IsDirected α fun (x1 x2 : α) => x1 ≤ x2] : IsFilteredOrEmpty α

@[instance 100]

instance CategoryTheory.isFiltered_of_directed_le_nonempty (α : Type u) [Preorder α] [IsDirected α fun (x1 x2 : α) => x1 ≤ x2] [Nonempty α] : IsFiltered α

instance CategoryTheory.instIsFilteredDiscretePUnit : IsFiltered (Discrete PUnit.{u_1 + 1})

noncomputable def CategoryTheory.IsFiltered.max {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] (j j' : C) : C

max j j' is an arbitrary choice of object to the right of both j and j', whose existence is ensured by IsFiltered.

Equations

• CategoryTheory.IsFiltered.max j j' = ⋯.choose

noncomputable def CategoryTheory.IsFiltered.leftToMax {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] (j j' : C) : j ⟶ max j j'

leftToMax j j' is an arbitrary choice of morphism from j to max j j', whose existence is ensured by IsFiltered.

Equations

• CategoryTheory.IsFiltered.leftToMax j j' = ⋯.choose

noncomputable def CategoryTheory.IsFiltered.rightToMax {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] (j j' : C) : j' ⟶ max j j'

rightToMax j j' is an arbitrary choice of morphism from j' to max j j', whose existence is ensured by IsFiltered.

Equations

• CategoryTheory.IsFiltered.rightToMax j j' = ⋯.choose

noncomputable def CategoryTheory.IsFiltered.coeq {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j j' : C} (f f' : j ⟶ j') : C

coeq f f', for morphisms f f' : j ⟶ j', is an arbitrary choice of object which admits a morphism coeqHom f f' : j' ⟶ coeq f f' such that coeq_condition : f ≫ coeqHom f f' = f' ≫ coeqHom f f'. Its existence is ensured by IsFiltered.

Equations

• CategoryTheory.IsFiltered.coeq f f' = ⋯.choose

noncomputable def CategoryTheory.IsFiltered.coeqHom {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j j' : C} (f f' : j ⟶ j') : j' ⟶ coeq f f'

coeqHom f f', for morphisms f f' : j ⟶ j', is an arbitrary choice of morphism coeqHom f f' : j' ⟶ coeq f f' such that coeq_condition : f ≫ coeqHom f f' = f' ≫ coeqHom f f'. Its existence is ensured by IsFiltered.

Equations

• CategoryTheory.IsFiltered.coeqHom f f' = ⋯.choose

theorem CategoryTheory.IsFiltered.coeq_condition {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j j' : C} (f f' : j ⟶ j') : CategoryStruct.comp f (coeqHom f f') = CategoryStruct.comp f' (coeqHom f f')

coeq_condition f f', for morphisms f f' : j ⟶ j', is the proof that f ≫ coeqHom f f' = f' ≫ coeqHom f f'.

theorem CategoryTheory.IsFiltered.coeq_condition_assoc {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j j' : C} (f f' : j ⟶ j') {Z : C} (h : coeq f f' ⟶ Z) : CategoryStruct.comp f (CategoryStruct.comp (coeqHom f f') h) = CategoryStruct.comp f' (CategoryStruct.comp (coeqHom f f') h)

theorem CategoryTheory.IsFilteredOrEmpty.of_right_adjoint {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {D : Type u₁} [Category.{v₁, u₁} D] {L : Functor D C} {R : Functor C D} (h : L ⊣ R) : IsFilteredOrEmpty D

If C is filtered or empty, and we have a functor R : C ⥤ D with a left adjoint, then D is filtered or empty.

theorem CategoryTheory.IsFilteredOrEmpty.of_isRightAdjoint {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {D : Type u₁} [Category.{v₁, u₁} D] (R : Functor C D) [R.IsRightAdjoint] : IsFilteredOrEmpty D

If C is filtered or empty, and we have a right adjoint functor R : C ⥤ D, then D is filtered or empty.

theorem CategoryTheory.IsFilteredOrEmpty.of_equivalence {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {D : Type u₁} [Category.{v₁, u₁} D] (h : C ≌ D) : IsFilteredOrEmpty D

Being filtered or empty is preserved by equivalence of categories.

theorem CategoryTheory.IsFiltered.sup_objs_exists {C : Type u} [Category.{v, u} C] [IsFiltered C] (O : Finset C) : ∃ (S : C), ∀ {X : C}, X ∈ O → Nonempty (X ⟶ S)

Any finite collection of objects in a filtered category has an object "to the right".

theorem CategoryTheory.IsFiltered.sup_exists {C : Type u} [Category.{v, u} C] [IsFiltered C] (O : Finset C) (H : Finset ((X : C) ×' (Y : C) ×' (_ : X ∈ O) ×' (_ : Y ∈ O) ×' (X ⟶ Y))) : ∃ (S : C) (T : {X : C} → X ∈ O → (X ⟶ S)), ∀ {X Y : C} (mX : X ∈ O) (mY : Y ∈ O) {f : X ⟶ Y}, ⟨X, ⟨Y, ⟨mX, ⟨mY, f⟩⟩⟩⟩ ∈ H → CategoryStruct.comp f (T mY) = T mX

Given any Finset of objects {X, ...} and indexed collection of Finsets of morphisms {f, ...} in C, there exists an object S, with a morphism T X : X ⟶ S from each X, such that the triangles commute: f ≫ T Y = T X, for f : X ⟶ Y in the Finset.

noncomputable def CategoryTheory.IsFiltered.sup {C : Type u} [Category.{v, u} C] [IsFiltered C] (O : Finset C) (H : Finset ((X : C) ×' (Y : C) ×' (_ : X ∈ O) ×' (_ : Y ∈ O) ×' (X ⟶ Y))) : C

An arbitrary choice of object "to the right" of a finite collection of objects O and morphisms H, making all the triangles commute.

Equations

• CategoryTheory.IsFiltered.sup O H = ⋯.choose

noncomputable def CategoryTheory.IsFiltered.toSup {C : Type u} [Category.{v, u} C] [IsFiltered C] (O : Finset C) (H : Finset ((X : C) ×' (Y : C) ×' (_ : X ∈ O) ×' (_ : Y ∈ O) ×' (X ⟶ Y))) {X : C} (m : X ∈ O) : X ⟶ sup O H

The morphisms to sup O H.

Equations

• CategoryTheory.IsFiltered.toSup O H m = ⋯.choose m

theorem CategoryTheory.IsFiltered.toSup_commutes {C : Type u} [Category.{v, u} C] [IsFiltered C] (O : Finset C) (H : Finset ((X : C) ×' (Y : C) ×' (_ : X ∈ O) ×' (_ : Y ∈ O) ×' (X ⟶ Y))) {X Y : C} (mX : X ∈ O) (mY : Y ∈ O) {f : X ⟶ Y} (mf : ⟨X, ⟨Y, ⟨mX, ⟨mY, f⟩⟩⟩⟩ ∈ H) : CategoryStruct.comp f (toSup O H mY) = toSup O H mX

The triangles of consisting of a morphism in H and the maps to sup O H commute.

theorem CategoryTheory.IsFiltered.cocone_nonempty {C : Type u} [Category.{v, u} C] [IsFiltered C] {J : Type w} [SmallCategory J] [FinCategory J] (F : Functor J C) : Nonempty (Limits.Cocone F)

If we have IsFiltered C, then for any functor F : J ⥤ C with FinCategory J, there exists a cocone over F.

noncomputable def CategoryTheory.IsFiltered.cocone {C : Type u} [Category.{v, u} C] [IsFiltered C] {J : Type w} [SmallCategory J] [FinCategory J] (F : Functor J C) : Limits.Cocone F

An arbitrary choice of cocone over F : J ⥤ C, for FinCategory J and IsFiltered C.

Equations

• CategoryTheory.IsFiltered.cocone F = ⋯.some

theorem CategoryTheory.IsFiltered.of_right_adjoint {C : Type u} [Category.{v, u} C] [IsFiltered C] {D : Type u₁} [Category.{v₁, u₁} D] {L : Functor D C} {R : Functor C D} (h : L ⊣ R) : IsFiltered D

If C is filtered, and we have a functor R : C ⥤ D with a left adjoint, then D is filtered.

theorem CategoryTheory.IsFiltered.of_isRightAdjoint {C : Type u} [Category.{v, u} C] [IsFiltered C] {D : Type u₁} [Category.{v₁, u₁} D] (R : Functor C D) [R.IsRightAdjoint] : IsFiltered D

If C is filtered, and we have a right adjoint functor R : C ⥤ D, then D is filtered.

theorem CategoryTheory.IsFiltered.of_equivalence {C : Type u} [Category.{v, u} C] [IsFiltered C] {D : Type u₁} [Category.{v₁, u₁} D] (h : C ≌ D) : IsFiltered D

Being filtered is preserved by equivalence of categories.

theorem CategoryTheory.IsFiltered.of_cocone_nonempty (C : Type u) [Category.{v, u} C] (h : ∀ {J : Type w} [inst : SmallCategory J] [FinCategory J] (F : Functor J C), Nonempty (Limits.Cocone F)) : IsFiltered C

If every finite diagram in C admits a cocone, then C is filtered. It is sufficient to verify this for diagrams whose shape lives in any one fixed universe.

theorem CategoryTheory.IsFiltered.of_hasFiniteColimits (C : Type u) [Category.{v, u} C] [Limits.HasFiniteColimits C] : IsFiltered C

theorem CategoryTheory.IsFiltered.of_isTerminal (C : Type u) [Category.{v, u} C] {X : C} (h : Limits.IsTerminal X) : IsFiltered C

@[instance 100]

instance CategoryTheory.IsFiltered.of_hasTerminal (C : Type u) [Category.{v, u} C] [Limits.HasTerminal C] : IsFiltered C

theorem CategoryTheory.IsFiltered.iff_cocone_nonempty (C : Type u) [Category.{v, u} C] : IsFiltered C ↔ ∀ {J : Type w} [inst : SmallCategory J] [FinCategory J] (F : Functor J C), Nonempty (Limits.Cocone F)

For every universe w, C is filtered if and only if every finite diagram in C with shape in w admits a cocone.

noncomputable def CategoryTheory.IsFiltered.max₃ {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] (j₁ j₂ j₃ : C) : C

max₃ j₁ j₂ j₃ is an arbitrary choice of object to the right of j₁, j₂ and j₃, whose existence is ensured by IsFiltered.

Equations

• CategoryTheory.IsFiltered.max₃ j₁ j₂ j₃ = CategoryTheory.IsFiltered.max (CategoryTheory.IsFiltered.max j₁ j₂) j₃

noncomputable def CategoryTheory.IsFiltered.firstToMax₃ {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] (j₁ j₂ j₃ : C) : j₁ ⟶ max₃ j₁ j₂ j₃

firstToMax₃ j₁ j₂ j₃ is an arbitrary choice of morphism from j₁ to max₃ j₁ j₂ j₃, whose existence is ensured by IsFiltered.

Equations

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

noncomputable def CategoryTheory.IsFiltered.secondToMax₃ {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] (j₁ j₂ j₃ : C) : j₂ ⟶ max₃ j₁ j₂ j₃

secondToMax₃ j₁ j₂ j₃ is an arbitrary choice of morphism from j₂ to max₃ j₁ j₂ j₃, whose existence is ensured by IsFiltered.

Equations

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

noncomputable def CategoryTheory.IsFiltered.thirdToMax₃ {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] (j₁ j₂ j₃ : C) : j₃ ⟶ max₃ j₁ j₂ j₃

thirdToMax₃ j₁ j₂ j₃ is an arbitrary choice of morphism from j₃ to max₃ j₁ j₂ j₃, whose existence is ensured by IsFiltered.

Equations

• CategoryTheory.IsFiltered.thirdToMax₃ j₁ j₂ j₃ = CategoryTheory.IsFiltered.rightToMax (CategoryTheory.IsFiltered.max j₁ j₂) j₃

noncomputable def CategoryTheory.IsFiltered.coeq₃ {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j₁ j₂ : C} (f g h : j₁ ⟶ j₂) : C

coeq₃ f g h, for morphisms f g h : j₁ ⟶ j₂, is an arbitrary choice of object which admits a morphism coeq₃Hom f g h : j₂ ⟶ coeq₃ f g h such that coeq₃_condition₁, coeq₃_condition₂ and coeq₃_condition₃ are satisfied. Its existence is ensured by IsFiltered.

Equations

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

noncomputable def CategoryTheory.IsFiltered.coeq₃Hom {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j₁ j₂ : C} (f g h : j₁ ⟶ j₂) : j₂ ⟶ coeq₃ f g h

coeq₃Hom f g h, for morphisms f g h : j₁ ⟶ j₂, is an arbitrary choice of morphism j₂ ⟶ coeq₃ f g h such that coeq₃_condition₁, coeq₃_condition₂ and coeq₃_condition₃ are satisfied. Its existence is ensured by IsFiltered.

Equations

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

theorem CategoryTheory.IsFiltered.coeq₃_condition₁ {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j₁ j₂ : C} (f g h : j₁ ⟶ j₂) : CategoryStruct.comp f (coeq₃Hom f g h) = CategoryStruct.comp g (coeq₃Hom f g h)

theorem CategoryTheory.IsFiltered.coeq₃_condition₂ {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j₁ j₂ : C} (f g h : j₁ ⟶ j₂) : CategoryStruct.comp g (coeq₃Hom f g h) = CategoryStruct.comp h (coeq₃Hom f g h)

theorem CategoryTheory.IsFiltered.coeq₃_condition₃ {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j₁ j₂ : C} (f g h : j₁ ⟶ j₂) : CategoryStruct.comp f (coeq₃Hom f g h) = CategoryStruct.comp h (coeq₃Hom f g h)

theorem CategoryTheory.IsFiltered.span {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {i j j' : C} (f : i ⟶ j) (f' : i ⟶ j') : ∃ (k : C) (g : j ⟶ k) (g' : j' ⟶ k), CategoryStruct.comp f g = CategoryStruct.comp f' g'

For every span j ⟵ i ⟶ j', there exists a cocone j ⟶ k ⟵ j' such that the square commutes.

theorem CategoryTheory.IsFiltered.bowtie {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j₁ j₂ k₁ k₂ : C} (f₁ : j₁ ⟶ k₁) (g₁ : j₁ ⟶ k₂) (f₂ : j₂ ⟶ k₁) (g₂ : j₂ ⟶ k₂) : ∃ (s : C) (α : k₁ ⟶ s) (β : k₂ ⟶ s), CategoryStruct.comp f₁ α = CategoryStruct.comp g₁ β ∧ CategoryStruct.comp f₂ α = CategoryStruct.comp g₂ β

Given a "bowtie" of morphisms

 j₁   j₂
 |\  /|
 | \/ |
 | /\ |
 |/  \∣
 vv  vv
 k₁  k₂

in a filtered category, we can construct an object s and two morphisms from k₁ and k₂ to s, making the resulting squares commute.

theorem CategoryTheory.IsFiltered.tulip {C : Type u} [Category.{v, u} C] [IsFilteredOrEmpty C] {j₁ j₂ j₃ k₁ k₂ l : C} (f₁ : j₁ ⟶ k₁) (f₂ : j₂ ⟶ k₁) (f₃ : j₂ ⟶ k₂) (f₄ : j₃ ⟶ k₂) (g₁ : j₁ ⟶ l) (g₂ : j₃ ⟶ l) : ∃ (s : C) (α : k₁ ⟶ s) (β : l ⟶ s) (γ : k₂ ⟶ s), CategoryStruct.comp f₁ α = CategoryStruct.comp g₁ β ∧ CategoryStruct.comp f₂ α = CategoryStruct.comp f₃ γ ∧ CategoryStruct.comp f₄ γ = CategoryStruct.comp g₂ β

Given a "tulip" of morphisms

 j₁    j₂    j₃
 |\   / \   / |
 | \ /   \ /  |
 |  vv    vv  |
 \  k₁    k₂ /
  \         /
   \       /
    \     /
     \   /
      v v
       l

in a filtered category, we can construct an object s and three morphisms from k₁, k₂ and l to s, making the resulting squares commute.

class CategoryTheory.IsCofilteredOrEmpty (C : Type u) [Category.{v, u} C] : Prop

A category IsCofilteredOrEmpty if

1. for every pair of objects there exists another object "to the left", and
2. for every pair of parallel morphisms there exists a morphism to the left so the compositions are equal.

• cone_objs (X Y : C) : ∃ (W : C) (x : W ⟶ X) (x : W ⟶ Y), True

  for every pair of objects there exists another object "to the left"

• cone_maps ⦃X Y : C⦄ (f g : X ⟶ Y) : ∃ (W : C) (h : W ⟶ X), CategoryStruct.comp h f = CategoryStruct.comp h g

  for every pair of parallel morphisms there exists a morphism to the left so the compositions are equal

class CategoryTheory.IsCofiltered (C : Type u) [Category.{v, u} C] extends CategoryTheory.IsCofilteredOrEmpty C : Prop

A category IsCofiltered if

1. for every pair of objects there exists another object "to the left",
2. for every pair of parallel morphisms there exists a morphism to the left so the compositions are equal, and
3. there exists some object.

• cone_objs (X Y : C) : ∃ (W : C) (x : W ⟶ X) (x : W ⟶ Y), True
• cone_maps ⦃X Y : C⦄ (f g : X ⟶ Y) : ∃ (W : C) (h : W ⟶ X), CategoryStruct.comp h f = CategoryStruct.comp h g
• nonempty : Nonempty C

  a cofiltered category must be non empty

@[instance 100]

instance CategoryTheory.isCofilteredOrEmpty_of_semilatticeInf (α : Type u) [SemilatticeInf α] : IsCofilteredOrEmpty α

@[instance 100]

instance CategoryTheory.isCofiltered_of_semilatticeInf_nonempty (α : Type u) [SemilatticeInf α] [Nonempty α] : IsCofiltered α

@[instance 100]

instance CategoryTheory.isCofilteredOrEmpty_of_directed_ge (α : Type u) [Preorder α] [IsDirected α fun (x1 x2 : α) => x1 ≥ x2] : IsCofilteredOrEmpty α

@[instance 100]

instance CategoryTheory.isCofiltered_of_directed_ge_nonempty (α : Type u) [Preorder α] [IsDirected α fun (x1 x2 : α) => x1 ≥ x2] [Nonempty α] : IsCofiltered α

instance CategoryTheory.instIsCofilteredDiscretePUnit : IsCofiltered (Discrete PUnit.{u_1 + 1})

noncomputable def CategoryTheory.IsCofiltered.min {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] (j j' : C) : C

min j j' is an arbitrary choice of object to the left of both j and j', whose existence is ensured by IsCofiltered.

Equations

• CategoryTheory.IsCofiltered.min j j' = ⋯.choose

noncomputable def CategoryTheory.IsCofiltered.minToLeft {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] (j j' : C) : min j j' ⟶ j

minToLeft j j' is an arbitrary choice of morphism from min j j' to j, whose existence is ensured by IsCofiltered.

Equations

• CategoryTheory.IsCofiltered.minToLeft j j' = ⋯.choose

noncomputable def CategoryTheory.IsCofiltered.minToRight {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] (j j' : C) : min j j' ⟶ j'

minToRight j j' is an arbitrary choice of morphism from min j j' to j', whose existence is ensured by IsCofiltered.

Equations

• CategoryTheory.IsCofiltered.minToRight j j' = ⋯.choose

noncomputable def CategoryTheory.IsCofiltered.eq {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {j j' : C} (f f' : j ⟶ j') : C

eq f f', for morphisms f f' : j ⟶ j', is an arbitrary choice of object which admits a morphism eqHom f f' : eq f f' ⟶ j such that eq_condition : eqHom f f' ≫ f = eqHom f f' ≫ f'. Its existence is ensured by IsCofiltered.

Equations

• CategoryTheory.IsCofiltered.eq f f' = ⋯.choose

noncomputable def CategoryTheory.IsCofiltered.eqHom {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {j j' : C} (f f' : j ⟶ j') : eq f f' ⟶ j

eqHom f f', for morphisms f f' : j ⟶ j', is an arbitrary choice of morphism eqHom f f' : eq f f' ⟶ j such that eq_condition : eqHom f f' ≫ f = eqHom f f' ≫ f'. Its existence is ensured by IsCofiltered.

Equations

• CategoryTheory.IsCofiltered.eqHom f f' = ⋯.choose

theorem CategoryTheory.IsCofiltered.eq_condition {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {j j' : C} (f f' : j ⟶ j') : CategoryStruct.comp (eqHom f f') f = CategoryStruct.comp (eqHom f f') f'

eq_condition f f', for morphisms f f' : j ⟶ j', is the proof that eqHom f f' ≫ f = eqHom f f' ≫ f'.

theorem CategoryTheory.IsCofiltered.eq_condition_assoc {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {j j' : C} (f f' : j ⟶ j') {Z : C} (h : j' ⟶ Z) : CategoryStruct.comp (eqHom f f') (CategoryStruct.comp f h) = CategoryStruct.comp (eqHom f f') (CategoryStruct.comp f' h)

theorem CategoryTheory.IsCofiltered.cospan {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {i j j' : C} (f : j ⟶ i) (f' : j' ⟶ i) : ∃ (k : C) (g : k ⟶ j) (g' : k ⟶ j'), CategoryStruct.comp g f = CategoryStruct.comp g' f'

For every cospan j ⟶ i ⟵ j', there exists a cone j ⟵ k ⟶ j' such that the square commutes.

theorem CategoryTheory.Functor.ranges_directed {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] (F : Functor C (Type u_1)) (j : C) : Directed (fun (x1 x2 : Set (F.obj j)) => x1 ⊇ x2) fun (f : (i : C) ×' (i ⟶ j)) => Set.range (F.map f.snd)

theorem CategoryTheory.IsCofiltered.bowtie {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {j₁ j₂ k₁ k₂ : C} (f₁ : k₁ ⟶ j₁) (g₁ : k₂ ⟶ j₁) (f₂ : k₁ ⟶ j₂) (g₂ : k₂ ⟶ j₂) : ∃ (s : C) (α : s ⟶ k₁) (β : s ⟶ k₂), CategoryStruct.comp α f₁ = CategoryStruct.comp β g₁ ∧ CategoryStruct.comp α f₂ = CategoryStruct.comp β g₂

Given a "bowtie" of morphisms

 k₁   k₂
 |\  /|
 | \/ |
 | /\ |
 |/  \∣
 vv  vv
 j₁  j₂

in a cofiltered category, we can construct an object s and two morphisms from s to k₁ and k₂, making the resulting squares commute.

theorem CategoryTheory.IsCofilteredOrEmpty.of_left_adjoint {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {D : Type u₁} [Category.{v₁, u₁} D] {L : Functor C D} {R : Functor D C} (h : L ⊣ R) : IsCofilteredOrEmpty D

If C is cofiltered or empty, and we have a functor L : C ⥤ D with a right adjoint, then D is cofiltered or empty.

theorem CategoryTheory.IsCofilteredOrEmpty.of_isLeftAdjoint {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {D : Type u₁} [Category.{v₁, u₁} D] (L : Functor C D) [L.IsLeftAdjoint] : IsCofilteredOrEmpty D

If C is cofiltered or empty, and we have a left adjoint functor L : C ⥤ D, then D is cofiltered or empty.

theorem CategoryTheory.IsCofilteredOrEmpty.of_equivalence {C : Type u} [Category.{v, u} C] [IsCofilteredOrEmpty C] {D : Type u₁} [Category.{v₁, u₁} D] (h : C ≌ D) : IsCofilteredOrEmpty D

Being cofiltered or empty is preserved by equivalence of categories.

theorem CategoryTheory.IsCofiltered.inf_objs_exists {C : Type u} [Category.{v, u} C] [IsCofiltered C] (O : Finset C) : ∃ (S : C), ∀ {X : C}, X ∈ O → Nonempty (S ⟶ X)

Any finite collection of objects in a cofiltered category has an object "to the left".

theorem CategoryTheory.IsCofiltered.inf_exists {C : Type u} [Category.{v, u} C] [IsCofiltered C] (O : Finset C) (H : Finset ((X : C) ×' (Y : C) ×' (_ : X ∈ O) ×' (_ : Y ∈ O) ×' (X ⟶ Y))) : ∃ (S : C) (T : {X : C} → X ∈ O → (S ⟶ X)), ∀ {X Y : C} (mX : X ∈ O) (mY : Y ∈ O) {f : X ⟶ Y}, ⟨X, ⟨Y, ⟨mX, ⟨mY, f⟩⟩⟩⟩ ∈ H → CategoryStruct.comp (T mX) f = T mY

Given any Finset of objects {X, ...} and indexed collection of Finsets of morphisms {f, ...} in C, there exists an object S, with a morphism T X : S ⟶ X from each X, such that the triangles commute: T X ≫ f = T Y, for f : X ⟶ Y in the Finset.

noncomputable def CategoryTheory.IsCofiltered.inf {C : Type u} [Category.{v, u} C] [IsCofiltered C] (O : Finset C) (H : Finset ((X : C) ×' (Y : C) ×' (_ : X ∈ O) ×' (_ : Y ∈ O) ×' (X ⟶ Y))) : C

An arbitrary choice of object "to the left" of a finite collection of objects O and morphisms H, making all the triangles commute.

Equations

• CategoryTheory.IsCofiltered.inf O H = ⋯.choose

noncomputable def CategoryTheory.IsCofiltered.infTo {C : Type u} [Category.{v, u} C] [IsCofiltered C] (O : Finset C) (H : Finset ((X : C) ×' (Y : C) ×' (_ : X ∈ O) ×' (_ : Y ∈ O) ×' (X ⟶ Y))) {X : C} (m : X ∈ O) : inf O H ⟶ X

The morphisms from inf O H.

Equations

• CategoryTheory.IsCofiltered.infTo O H m = ⋯.choose m

theorem CategoryTheory.IsCofiltered.infTo_commutes {C : Type u} [Category.{v, u} C] [IsCofiltered C] (O : Finset C) (H : Finset ((X : C) ×' (Y : C) ×' (_ : X ∈ O) ×' (_ : Y ∈ O) ×' (X ⟶ Y))) {X Y : C} (mX : X ∈ O) (mY : Y ∈ O) {f : X ⟶ Y} (mf : ⟨X, ⟨Y, ⟨mX, ⟨mY, f⟩⟩⟩⟩ ∈ H) : CategoryStruct.comp (infTo O H mX) f = infTo O H mY

The triangles consisting of a morphism in H and the maps from inf O H commute.

theorem CategoryTheory.IsCofiltered.cone_nonempty {C : Type u} [Category.{v, u} C] [IsCofiltered C] {J : Type w} [SmallCategory J] [FinCategory J] (F : Functor J C) : Nonempty (Limits.Cone F)

If we have IsCofiltered C, then for any functor F : J ⥤ C with FinCategory J, there exists a cone over F.

noncomputable def CategoryTheory.IsCofiltered.cone {C : Type u} [Category.{v, u} C] [IsCofiltered C] {J : Type w} [SmallCategory J] [FinCategory J] (F : Functor J C) : Limits.Cone F

An arbitrary choice of cone over F : J ⥤ C, for FinCategory J and IsCofiltered C.

Equations

• CategoryTheory.IsCofiltered.cone F = ⋯.some

theorem CategoryTheory.IsCofiltered.of_left_adjoint {C : Type u} [Category.{v, u} C] [IsCofiltered C] {D : Type u₁} [Category.{v₁, u₁} D] {L : Functor C D} {R : Functor D C} (h : L ⊣ R) : IsCofiltered D

If C is cofiltered, and we have a functor L : C ⥤ D with a right adjoint, then D is cofiltered.

theorem CategoryTheory.IsCofiltered.of_isLeftAdjoint {C : Type u} [Category.{v, u} C] [IsCofiltered C] {D : Type u₁} [Category.{v₁, u₁} D] (L : Functor C D) [L.IsLeftAdjoint] : IsCofiltered D

If C is cofiltered, and we have a left adjoint functor L : C ⥤ D, then D is cofiltered.

theorem CategoryTheory.IsCofiltered.of_equivalence {C : Type u} [Category.{v, u} C] [IsCofiltered C] {D : Type u₁} [Category.{v₁, u₁} D] (h : C ≌ D) : IsCofiltered D

Being cofiltered is preserved by equivalence of categories.

theorem CategoryTheory.IsCofiltered.of_cone_nonempty (C : Type u) [Category.{v, u} C] (h : ∀ {J : Type w} [inst : SmallCategory J] [FinCategory J] (F : Functor J C), Nonempty (Limits.Cone F)) : IsCofiltered C

If every finite diagram in C admits a cone, then C is cofiltered. It is sufficient to verify this for diagrams whose shape lives in any one fixed universe.

theorem CategoryTheory.IsCofiltered.of_hasFiniteLimits (C : Type u) [Category.{v, u} C] [Limits.HasFiniteLimits C] : IsCofiltered C

theorem CategoryTheory.IsCofiltered.of_isInitial (C : Type u) [Category.{v, u} C] {X : C} (h : Limits.IsInitial X) : IsCofiltered C

@[instance 100]

instance CategoryTheory.IsCofiltered.of_hasInitial (C : Type u) [Category.{v, u} C] [Limits.HasInitial C] : IsCofiltered C

theorem CategoryTheory.IsCofiltered.iff_cone_nonempty (C : Type u) [Category.{v, u} C] : IsCofiltered C ↔ ∀ {J : Type w} [inst : SmallCategory J] [FinCategory J] (F : Functor J C), Nonempty (Limits.Cone F)

For every universe w, C is filtered if and only if every finite diagram in C with shape in w admits a cocone.

instance CategoryTheory.isCofilteredOrEmpty_op_of_isFilteredOrEmpty (C : Type u) [Category.{v, u} C] [IsFilteredOrEmpty C] : IsCofilteredOrEmpty Cᵒᵖ

instance CategoryTheory.isCofiltered_op_of_isFiltered (C : Type u) [Category.{v, u} C] [IsFiltered C] : IsCofiltered Cᵒᵖ

instance CategoryTheory.isFilteredOrEmpty_op_of_isCofilteredOrEmpty (C : Type u) [Category.{v, u} C] [IsCofilteredOrEmpty C] : IsFilteredOrEmpty Cᵒᵖ

instance CategoryTheory.isFiltered_op_of_isCofiltered (C : Type u) [Category.{v, u} C] [IsCofiltered C] : IsFiltered Cᵒᵖ

theorem CategoryTheory.isCofilteredOrEmpty_of_isFilteredOrEmpty_op (C : Type u) [Category.{v, u} C] [IsFilteredOrEmpty Cᵒᵖ] : IsCofilteredOrEmpty C

If Cᵒᵖ is filtered or empty, then C is cofiltered or empty.

theorem CategoryTheory.isFilteredOrEmpty_of_isCofilteredOrEmpty_op (C : Type u) [Category.{v, u} C] [IsCofilteredOrEmpty Cᵒᵖ] : IsFilteredOrEmpty C

If Cᵒᵖ is cofiltered or empty, then C is filtered or empty.

theorem CategoryTheory.isCofiltered_of_isFiltered_op (C : Type u) [Category.{v, u} C] [IsFiltered Cᵒᵖ] : IsCofiltered C

If Cᵒᵖ is filtered, then C is cofiltered.

theorem CategoryTheory.isFiltered_of_isCofiltered_op (C : Type u) [Category.{v, u} C] [IsCofiltered Cᵒᵖ] : IsFiltered C

If Cᵒᵖ is cofiltered, then C is filtered.

instance CategoryTheory.instIsFilteredULift (C : Type u) [Category.{v, u} C] [IsFiltered C] : IsFiltered (ULift.{u₂, u} C)

instance CategoryTheory.instIsCofilteredULift (C : Type u) [Category.{v, u} C] [IsCofiltered C] : IsCofiltered (ULift.{u₂, u} C)

instance CategoryTheory.instIsFilteredULiftHom (C : Type u) [Category.{v, u} C] [IsFiltered C] : IsFiltered (ULiftHom C)

instance CategoryTheory.instIsCofilteredULiftHom (C : Type u) [Category.{v, u} C] [IsCofiltered C] : IsCofiltered (ULiftHom C)

instance CategoryTheory.instIsFilteredAsSmall (C : Type u) [Category.{v, u} C] [IsFiltered C] : IsFiltered (AsSmall C)

instance CategoryTheory.instIsCofilteredAsSmall (C : Type u) [Category.{v, u} C] [IsCofiltered C] : IsCofiltered (AsSmall C)

instance CategoryTheory.instIsFilteredOrEmptyForall {α : Type w} {I : α → Type u₁} [(i : α) → Category.{v₁, u₁} (I i)] [∀ (i : α), IsFilteredOrEmpty (I i)] : IsFilteredOrEmpty ((i : α) → I i)

instance CategoryTheory.instIsFilteredForall {α : Type w} {I : α → Type u₁} [(i : α) → Category.{v₁, u₁} (I i)] [∀ (i : α), IsFiltered (I i)] : IsFiltered ((i : α) → I i)

instance CategoryTheory.instIsCofilteredOrEmptyForall {α : Type w} {I : α → Type u₁} [(i : α) → Category.{v₁, u₁} (I i)] [∀ (i : α), IsCofilteredOrEmpty (I i)] : IsCofilteredOrEmpty ((i : α) → I i)

instance CategoryTheory.instIsCofilteredForall {α : Type w} {I : α → Type u₁} [(i : α) → Category.{v₁, u₁} (I i)] [∀ (i : α), IsCofiltered (I i)] : IsCofiltered ((i : α) → I i)

instance CategoryTheory.instIsFilteredOrEmptyProd {C : Type u₁} [Category.{v₁, u₁} C] {D : Type u₂} [Category.{v₂, u₂} D] [IsFilteredOrEmpty C] [IsFilteredOrEmpty D] : IsFilteredOrEmpty (C × D)

instance CategoryTheory.instIsFilteredProd {C : Type u₁} [Category.{v₁, u₁} C] {D : Type u₂} [Category.{v₂, u₂} D] [IsFiltered C] [IsFiltered D] : IsFiltered (C × D)

instance CategoryTheory.instIsCofilteredOrEmptyProd {C : Type u₁} [Category.{v₁, u₁} C] {D : Type u₂} [Category.{v₂, u₂} D] [IsCofilteredOrEmpty C] [IsCofilteredOrEmpty D] : IsCofilteredOrEmpty (C × D)

instance CategoryTheory.instIsCofilteredProd {C : Type u₁} [Category.{v₁, u₁} C] {D : Type u₂} [Category.{v₂, u₂} D] [IsCofiltered C] [IsCofiltered D] : IsCofiltered (C × D)