Categories #
THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.
Defines a category, as a type class parametrised by the type of objects.
Notations #
Introduces notations
X ⟶ Y
for the morphism spaces (type as\hom
),𝟙 X
for the identity morphism onX
(type as\b1
),f ≫ g
for composition in the 'arrows' convention (type as\gg
).
Users may like to add f ⊚ g
for composition in the standard convention, using
local notation f ` ⊚ `:80 g:80 := category.comp g f -- type as \oo
The typeclass category C
describes morphisms associated to objects of type C : Type u
.
The universe levels of the objects and morphisms are independent, and will often need to be
specified explicitly, as category.{v} C
.
Typically any concrete example will either be a small_category
, where v = u
,
which can be introduced as
universes u
variables {C : Type u} [small_category C]
or a large_category
, where u = v+1
, which can be introduced as
universes u
variables {C : Type (u+1)} [large_category C]
In order for the library to handle these cases uniformly,
we generally work with the unconstrained category.{v u}
,
for which objects live in Type u
and morphisms live in Type v
.
Because the universe parameter u
for the objects can be inferred from C
when we write category C
, while the universe parameter v
for the morphisms
can not be automatically inferred, through the category theory library
we introduce universe parameters with morphism levels listed first,
as in
universes v u
or
universes v₁ v₂ u₁ u₂
when multiple independent universes are needed.
This has the effect that we can simply write category.{v} C
(that is, only specifying a single parameter) while u
will be inferred.
Often, however, it's not even necessary to include the .{v}
.
(Although it was in earlier versions of Lean.)
If it is omitted a "free" universe will be used.
A preliminary structure on the way to defining a category, containing the data, but none of the axioms.
Instances of this typeclass
Instances of other typeclasses for category_theory.category_struct
- category_theory.category_struct.has_sizeof_inst
- to_category_struct : category_theory.category_struct obj
- id_comp' : (∀ {X Y : obj} (f : X ⟶ Y), 𝟙 X ≫ f = f) . "obviously"
- comp_id' : (∀ {X Y : obj} (f : X ⟶ Y), f ≫ 𝟙 Y = f) . "obviously"
- assoc' : (∀ {W X Y Z : obj} (f : W ⟶ X) (g : X ⟶ Y) (h : Y ⟶ Z), (f ≫ g) ≫ h = f ≫ g ≫ h) . "obviously"
The typeclass category C
describes morphisms associated to objects of type C
.
The universe levels of the objects and morphisms are unconstrained, and will often need to be
specified explicitly, as category.{v} C
. (See also large_category
and small_category
.)
See https://stacks.math.columbia.edu/tag/0014.
Instances of this typeclass
- category_theory.groupoid.to_category
- preorder.small_category
- category_theory.strict_bicategory.category
- category_theory.ulift_category
- category_theory.functor.category
- category_theory.induced_category.category
- category_theory.full_subcategory.category
- category_theory.functor.ess_image_subcategory.category
- category_theory.category.opposite
- category_theory.prod
- category_theory.uniform_prod
- category_theory.pi
- category_theory.pi'
- category_theory.pi.sum_elim_category
- category_theory.types
- category_theory.comma_category
- category_theory.arrow.category
- category_theory.discrete_category
- category_theory.prod_category_instance_1
- category_theory.prod_category_instance_2
- category_theory.limits.cone.category
- category_theory.limits.cocone.category
- category_theory.ulift_hom.category
- category_theory.as_small.small_category
- category_theory.limits.wide_pullback_shape.category
- category_theory.limits.wide_pushout_shape.category
- category_theory.bicategory.hom_category
- category_theory.Cat.str
- category_theory.Cat.category
- category_theory.skeleton.category
- category_theory.small_category_small_model
- category_theory.shrink_homs.category_theory.category
- category_theory.structured_arrow.category
- category_theory.costructured_arrow.category
- category_theory.over.category
- category_theory.under.category
- category_theory.bundled_hom.category
- Mon.large_category
- AddMon.large_category
- CommMon.large_category
- AddCommMon.large_category
- Group.large_category
- AddGroup.large_category
- CommGroup.large_category
- AddCommGroup.large_category
- SemiRing.large_category
- Ring.large_category
- CommSemiRing.large_category
- CommRing.large_category
- category_theory.limits.walking_parallel_pair_hom_category
- category_theory.fin_category.category_as_type
- category_theory.LeftExactFunctor.category
- category_theory.RightExactFunctor.category
- category_theory.ExactFunctor.category
- category_theory.AdditiveFunctor.category
- Module.Module_category
- Algebra.category_theory.category
- QuadraticModule.category
- Cliff.category_theory.category
Instances of other typeclasses for category_theory.category
- category_theory.category.has_sizeof_inst
A large_category
has objects in one universe level higher than the universe level of
the morphisms. It is useful for examples such as the category of types, or the category
of groups, etc.
A small_category
has objects and morphisms in the same universe level.
postcompose an equation between morphisms by another morphism
precompose an equation between morphisms by another morphism
A morphism f
is an epimorphism if it can be "cancelled" when precomposed:
f ≫ g = f ≫ h
implies g = h
.
See https://stacks.math.columbia.edu/tag/003B.
Instances of this typeclass
- category_theory.is_iso.epi_of_iso
- category_theory.is_split_epi.epi
- category_theory.epi_of_strong_epi
- category_theory.category_struct.id.epi
- category_theory.unop_epi_of_mono
- category_theory.op_epi_of_mono
- category_theory.arrow.epi_right
- category_theory.functor.map_epi
- category_theory.limits.colim_map_epi'
- category_theory.limits.colim_map_epi
- category_theory.structured_arrow.epi_hom_mk
- category_theory.costructured_arrow.epi_hom_mk
- category_theory.under.epi_right_of_epi
- category_theory.limits.coprod.epi_desc_of_epi_left
- category_theory.limits.coprod.epi_desc_of_epi_right
- category_theory.limits.coprod.map_epi
- category_theory.limits.pushout.inl_of_epi
- category_theory.limits.pushout.inr_of_epi
- category_theory.limits.epi_coprod_to_pushout
- category_theory.limits.sigma.map_epi
- category_theory.limits.coequalizer.π_epi
- category_theory.limits.factor_thru_image.category_theory.epi
- category_theory.limits.image.pre_comp_epi_of_epi
- category_theory.limits.has_zero_object.category_theory.epi
- category_theory.limits.cokernel.desc_epi
- category_theory.preadditive.has_neg.neg.category_theory.epi
- category_theory.linear.has_smul.smul.category_theory.epi
- category_theory.limits.biprod.epi_desc_of_epi_left
- category_theory.limits.biprod.epi_desc_of_epi_right
A morphism f
is a monomorphism if it can be "cancelled" when postcomposed:
g ≫ f = h ≫ f
implies g = h
.
See https://stacks.math.columbia.edu/tag/003B.
Instances of this typeclass
- category_theory.is_iso.mono_of_iso
- category_theory.is_split_mono.mono
- category_theory.mono_of_strong_mono
- category_theory.limits.initial.mono_from
- category_theory.category_struct.id.mono
- category_theory.unop_mono_of_epi
- category_theory.op_mono_of_epi
- category_theory.arrow.mono_left
- category_theory.functor.map_mono
- category_theory.limits.lim_map_mono'
- category_theory.limits.lim_map_mono
- category_theory.structured_arrow.mono_hom_mk
- category_theory.costructured_arrow.mono_hom_mk
- category_theory.over.mono_left_of_mono
- category_theory.limits.prod.mono_lift_of_mono_left
- category_theory.limits.prod.mono_lift_of_mono_right
- category_theory.limits.prod.map_mono
- category_theory.limits.pullback.fst_of_mono
- category_theory.limits.pullback.snd_of_mono
- category_theory.limits.mono_pullback_to_prod
- category_theory.limits.pi.map_mono
- category_theory.limits.equalizer.ι_mono
- category_theory.limits.mono_factorisation.m_mono
- category_theory.limits.image.ι.category_theory.mono
- category_theory.limits.image.lift_mono
- category_theory.limits.image.pre_comp_mono
- category_theory.limits.has_zero_object.category_theory.mono
- category_theory.limits.kernel.lift_mono
- category_theory.preadditive.has_neg.neg.category_theory.mono
- category_theory.linear.has_smul.smul.category_theory.mono
- category_theory.limits.biprod.mono_lift_of_mono_left
- category_theory.limits.biprod.mono_lift_of_mono_right
Many proofs in the category theory library use the dsimp, simp
pattern,
which typically isn't necessary elsewhere.
One would usually hope that the same effect could be achieved simply with simp
.
The essential issue is that composition of morphisms involves dependent types.
When you have a chain of morphisms being composed, say f : X ⟶ Y
and g : Y ⟶ Z
,
then simp
can operate succesfully on the morphisms
(e.g. if f
is the identity it can strip that off).
However if we have an equality of objects, say Y = Y'
,
then simp
can't operate because it would break the typing of the composition operations.
We rarely have interesting equalities of objects
(because that would be "evil" --- anything interesting should be expressed as an isomorphism
and tracked explicitly),
except of course that we have plenty of definitional equalities of objects.
dsimp
can apply these safely, even inside a composition.
After dsimp
has cleared up the object level, simp
can resume work on the morphism level ---
but without the dsimp
step, because simp
looks at expressions syntactically,
the relevant lemmas might not fire.
There's no bound on how many times you potentially could have to switch back and forth,
if the simp
introduced new objects we again need to dsimp
.
In practice this does occur, but only rarely, because simp
tends to shorten chains of compositions
(i.e. not introduce new objects at all).