Refactor category support for morphisms (Hom is not a functorial construction!)

[nthiery]

Before this ticket, Hom was implemented as a covariant functorial construction:

    sage: Rings().hom_category()
    Category of hom sets in Category of rings
    sage: Rings().hom_category().super_categories()
    [Category of hom sets in Category of sets]

The intention was to model the fact that a morphism in a category is
also a morphism in any super category, via the forgetful functor. With
the example above, if A and B are rings, then a ring morphism phi:
A->B is also a set morphism. However, at the level of parents, and as
noted in the documentation of sage.category.HomCategory, this is
mathematically plain wrong: if A and B are rings, then Hom(A,B) in the
category of rings does not coincide with Hom(A,B) in the category of
sets.

I, Nicolas, take full blame for this misfeature; it was just the
shortest route to implement some urgently needed features about
morphisms, and still get that huge chunk of category code done.

Status of the current reimplementation:

• Add support for a MorphismsMethods subclass, similar to
  ElementMethods and ParentMethods. If Cat is a category, then
  Cat.MorphismMethods will provide generic methods for morphisms in
  Cat and in any subcategory. This can be achieved by:

  • Building of a hierarchy of abstract classes Cat.morphism_class,
    similar to Cat.element_class and Cat.parent_class (10 lines of
    code; see Category.element_class).

  • Having morphisms in Cat inherit from Cat.morphism_class; this
    is implemented by overriding Parent.morphism_class. An
    alternative would have been to override Category.element_class
    in HomsetsCategory.element_class.

• Rename both HomCategory and hom_category to Homsets, for consistency
  with the other constructions like CartesianProducts, ...

• Fix HomCategory: for Cat a category, the purpose of
  Cat.hom_category() shall be to provide mathematical information
  about its homsets (e.g. that a homset in the category of vector
  spaces is also a vector space). It is only a subcategory of the
  homsets of the full super categories of Cat (a homset in the
  category of finite groups is also a homset in the category of
  groups).

• Remove HomCategory from the global namespace.

Potential further desirable features for a later ticket:

• If CatA is a subcategory of CatB, add automatic coercion (or just
  conversion?) from Hom(A,B, CatA) to Hom(A, B, CatB), modeling the
  appropriate forgetful functor. There are too many such coercions
  for them to be registered explicitly. So this probably needs to be
  implemented through a specific CatB._has_coerce_map_from(A) for
  homsets.

• Extend/use sage.categories.pushout to handle mixed morphism
  arithmetic (e.g. having the sum of an algebra morphism and a
  coalgebra morphism return a vector space morphism).

Depends on #16340

CC: @sagetrac-sage-combinat @simon-king-jena

Component: categories

Author: Nicolas M. Thiéry

Branch: a937938

Reviewer: Simon King

Issue created by migration from https://trac.sagemath.org/ticket/10668

[simon-king-jena]

Replying to @nthiery:

The intention was to model the fact that a morphism in a category is
also a morphism in any super category, via the forgetful functor. With
the example above, if A and B are rings, then a ring morphism phi:
A->B is also a set morphism. However, at the level of parents, and as
noted in the documentation of sage.category.HomCategory, this is
mathematically plain wrong: if A and B are rings, then Hom(A,B) in the
category of rings does not coincide with Hom(A,B) in the category of
sets.

I don't see why this should be wrong: Any ring homomorphism is a set homomorphism. Hence, Hom_Rings()(A,B) is a subset of Hom_Sets()(A,B) -- nobody claims that they coincide.

Here are some thoughts for a proper implementation:

• Add support for a HomMethods subclass, similar to ElementMethods
  and ParentMethods. If Cat is a category, then Cat.ElementMethods
  will provide generic methods for morphisms in Cat and any
  subcategory.

You mean "Cat.HomMethods will provide...", I guess.

• Reimplement HomCategory. For Cat a category, the purpose of
  Cat.hom_category() shall be to provide mathematical information
  about its homsets (e.g. that a homset in the category of vector
  spaces is also a vector space). It should ignore the super
  categories of C in general, except if is a full subcategory (a
  homset in the category of finite groups is also a homset in the
  category of groups).

The approach with HomMethods would provide methods defined for homsets, whereas the fact that a homset of vector spaces is a vector space has implications for the methods of elements of the homsets (i.e., for methods of morphisms).

I don't know whether we need special methods for homset, but of course it would be nice to have homsets that are vector spaces.

What about the following approach:

• There is the base class sage.categories.category.HomCategory. I suggest to provide it with an optional argument hom_structure. Define, for example, H = HomCategory(Algebras(QQ),hom_structure=VectorSpaces(QQ)). Then, H is the category of homsets in the category of algebras over QQ, and each homset would automatically be a vector space over QQ. Moreover, H would be a sub-category of VectorSpaces(QQ).

• I suggest to introduce a lazy attribute C.hom_structure, that defaults to C.HomStructure if that exists, and otherwise returns the join of S.hom_structure for all S in C.super_categories(). Then, C.hom_category() defaults to HomCategory(C, hom_structure=C.hom_structure).

• Of course, any category can define a custom HomStructure (e.g., in the __init__ method of VectorSpaces(R), we would define self.HomStructure=self, ensuring that self.hom_structure is the right thing). In order to avoid an infinite recursion of the lazy attribute, we also need to define Objects().HomStructure=Objects().

• If CatA is a subcategory of catB, add automatic coercion (or just
  conversion?) from Hom(A,B, CatA) to Hom(A, B, CatB), modeling the
  appropriate forgetful functor. There are too many such coercions
  for them to be registered explicitly. So this probably need to be
  implemented through a specific CatB._has_coerce_map_from(A) for
  homsets.

That would be a good candidate for your HomMethods, don't you think?

Some extra work will probably be needed if one wants to handle
mixed morphism arithmetic (e.g. having the sum of an algebra
morphism and a coalgebra morphism return a vector space morphism).

I guess that would be an extension of the sage.categories.pushout formalism.

Anyway, my suggestion is to start with the hom_structure approach, as it seems to be relatively straight forward to implement.

[nthiery]

comment:2

Replying to @simon-king-jena:

Replying to @nthiery:

The intention was to model the fact that a morphism in a category is
also a morphism in any super category, via the forgetful functor. With
the example above, if A and B are rings, then a ring morphism phi:
A->B is also a set morphism. However, at the level of parents, and as
noted in the documentation of sage.category.HomCategory, this is
mathematically plain wrong: if A and B are rings, then Hom(A,B) in the
category of rings does not coincide with Hom(A,B) in the category of
sets.

I don't see why this should be wrong: Any ring homomorphism is a set homomorphism. Hence, Hom_Rings()(A,B) is a subset of Hom_Sets()(A,B) -- nobody claims that they coincide.

Very short answer for now: here the question is whether Hom_Rings()(A,B) is an object of Hom_Sets(). It's not. The point of VectorSpaces().HomCategory() is to encode mathematical information about the homsets, like the fact that Hom(A,B) is itself a vector space. We don't want this information to be applied to a homset of a subcategory (a homset in Algebras() being certainly not a vector space).

[nthiery]

Description changed:

--- 
+++ 
@@ -24,7 +24,7 @@
 Here are some thoughts for a proper implementation:
 
 - Add support for a HomMethods subclass, similar to ElementMethods
-  and ParentMethods. If Cat is a category, then Cat.ElementMethods
+  and ParentMethods. If Cat is a category, then Cat.HomMethods
   will provide generic methods for morphisms in Cat and any
   subcategory. This will require to implement the building of a
   hierarchy of abstract classes Cat.method_class. And to either tweak

[simon-king-jena]

comment:3

Replying to @nthiery:

Very short answer for now: here the question is whether Hom_Rings()(A,B) is an object of Hom_Sets(). It's not. The point of VectorSpaces().HomCategory() is to encode mathematical information about the homsets, like the fact that Hom(A,B) is itself a vector space. We don't want this information to be applied to a homset of a subcategory (a homset in Algebras() being certainly not a vector space).

Right.

Nevertheless, I believe that an attribute like C.hom_structure would be a convenient way to declare that the homsets of C all have a particular structure (like Rings() or VectorSpaces(C.base_ring())) and that therefore C.hom_category() is a sub-category of C.hom_structure.

So, for now, the only detail that I have to withdraw from my proposal is that C.hom_structure will not be influenced by X.hom_structure for a super-category X of C.

[nthiery]

Description changed:

--- 
+++ 
@@ -23,18 +23,22 @@
 
 Here are some thoughts for a proper implementation:
 
-- Add support for a HomMethods subclass, similar to ElementMethods
-  and ParentMethods. If Cat is a category, then Cat.HomMethods
-  will provide generic methods for morphisms in Cat and any
-  subcategory. This will require to implement the building of a
-  hierarchy of abstract classes Cat.method_class. And to either tweak
-  sage.categories.morphism.Morphism to add inheritance from this
-  class, as is done in Element and Parent, or to tweak the
-  implementation of Homset.element_class so that, for H a homset in
-  Cat, H.element_class would inherit from Cat.method_class besides
-  the usual stuff (I guess I prefer the later option).
+- Add support for a MorphismsMethods subclass, similar to
+  ElementMethods and ParentMethods. If Cat is a category, then
+  Cat.MorphismMethods will provide generic methods for morphisms in
+  Cat and in any subcategory. This can be achieved by:
 
-- Reimplement HomCategory. For Cat a category, the purpose of
+   - Building of a hierarchy of abstract classes Cat.morphism_class,
+     similar to Cat.element_class and Cat.parent_class (10 lines of
+     code; see Category.element_class).
+
+   - Having morphisms in Cat inherit from Cat.morphism_class. This
+     can be achieved by overiding either:
+
+      - Parent.element_class in Homset.element_class
+      - Category.element_class in HomCategory.element_class (my preferred choice at this point)
+
+- Fix HomCategory. For Cat a category, the purpose of
   Cat.hom_category() shall be to provide mathematical information
   about its homsets (e.g. that a homset in the category of vector
   spaces is also a vector space). It should ignore the super
@@ -42,14 +46,14 @@
   homset in the category of finite groups is also a homset in the
   category of groups).
 
-- If CatA is a subcategory of catB, add automatic coercion (or just
+- If CatA is a subcategory of CatB, add automatic coercion (or just
   conversion?) from Hom(A,B, CatA) to Hom(A, B, CatB), modeling the
   appropriate forgetful functor. There are too many such coercions
   for them to be registered explicitly. So this probably need to be
   implemented through a specific CatB._has_coerce_map_from(A) for
   homsets.
 
-  Some extra work will probably be needed if one wants to handle
-  mixed morphism arithmetic (e.g. having the sum of an algebra
-  morphism and a coalgebra morphism return a vector space morphism).
+- Extend/use sage.categories.pushout to handle mixed morphism
+  arithmetic (e.g. having the sum of an algebra morphism and a
+  coalgebra morphism return a vector space morphism).
 

[nthiery]

comment:5

Replying to @nthiery:

More later when I'll have recharged my battery ...

[simon-king-jena]

Replying to @nthiery:

• Add support for a MorphismsMethods subclass, similar to
  ElementMethods and ParentMethods. If Cat is a category, then
  Cat.MorphismMethods will provide generic methods for morphisms in
  Cat and in any subcategory.

Not in a sub-category! Namely, if Cat is the category of F-vectorspaces, then Cat.MorphismMethods would include addition and skalar multiplication. But for a sub-category of Cat, such as F-algebras, we don't want that, as you had pointed out.

This can be achieved by:

• Building of a hierarchy of abstract classes Cat.morphism_class,
  similar to Cat.element_class and Cat.parent_class (10 lines of
  code; see Category.element_class).

I don't see such hierarchy.

• Having morphisms in Cat inherit from Cat.morphism_class.

I really think the Cat.hom_structure formalism that I suggested would be easier.

Any category would provide its own hom-structure (and there would be no inheritance for sub-categories), of course Objects() being the default hom-structure.

Then, homsets in Cat would inherit from Cat.hom_structure.parent_class, whereas morphisms in Cat would inherit from Cat.hom_structure.element_class.

In particular, there is no need to provide Cat.HomMethods or Cat.MorphismMethods. In fact, they are redundant: If you simply state that Cat.hom_structure is VectorSpaces(QQ), then the morphisms already have the element methods of vector spaces, whereas in your approach you needed to restate (copy-and-paste) them as Cat.MorphismMethods.

[nthiery]

comment:7

Replying to @simon-king-jena:

Not in a sub-category! Namely, if Cat is the category of
F-vectorspaces, then Cat.MorphismMethods would include addition
and skalar multiplication. But for a sub-category of Cat, such as
F-algebras, we don't want that, as you had pointed out.

Of course addition should not be put in MorphismMethods. On the other
hand, there are a lot of generic operations on morphisms that pass
down to subcategories, like inverting a morphism (say in the category
of finite sets) or computing the matrix/the rank/the det/you_name_it
of a morphism of finite dimensional vector space. It is essential to
pass those generic methods down to subcategories.

That is not a vague though that popped up when I created this ticket,
but a concrete feature that we have been longing for years and we
could not implement in MuPAD (MuPAD categories did not handle
morphisms) despite our many use cases.

I really think the Cat.hom_structure formalism that I suggested
would be easier.

And I think mine is no more complicated, while being more consistent
with the rest of the framework :-)

It seems like most of the discussion comes from confusion and
vagueness (and I take my share of the blame for that). So let's both
write a little prototype to have a concrete ground to discuss on. We
don't have to include the coercion / push_out part in this prototype
since we agree on it. I can try to implement mine sometime next week.

In particular, there is no need to provide Cat.HomMethods or
Cat.MorphismMethods. In fact, they are redundant: If you simply
state that Cat.hom_structure is VectorSpaces(QQ), then the
morphisms already have the element methods of vector spaces, whereas
in your approach you needed to restate (copy-and-paste) them as
Cat.MorphismMethods.

Cat.HomCategory() will still use the standard super_categories()
approach to state that it is a subcategory of VectorSpaces(), and its
elements will inherit from VectorSpaces().element_class.

Cheers,
Nicolas

PS: by the way, I am wondering if we should be using Cat.objects() or
Cat.Objects() (given that we already have Cat.Quotients(),
Cat.Subobjects(), Cat.CartesianProducts(), ...). Here, I am thinking
about using the occasion to replace Cat.hom_category() by Cat.Homsets().

[simon-king-jena]

comment:8

Replying to @nthiery:

Replying to @simon-king-jena:

Not in a sub-category! Namely, if Cat is the category of
F-vectorspaces, then Cat.MorphismMethods would include addition
and skalar multiplication. But for a sub-category of Cat, such as
F-algebras, we don't want that, as you had pointed out.

Of course addition should not be put in MorphismMethods. On the other
hand, there are a lot of generic operations on morphisms that pass
down to subcategories, like inverting a morphism (say in the category
of finite sets) or computing the matrix/the rank/the det/you_name_it
of a morphism of finite dimensional vector space. It is essential to
pass those generic methods down to subcategories.

I see. Yes, for those kind of methods, your approach makes very much sense.

But what would actually prevent us from doing both? Our two approaches are good for different things, and they are orthogonal to each other. If I understand correctly, you suggest that there should be Cat.morphism_class from which morphisms inherit, analogous to Cat.element_class, thereby getting "hereditary" (to sub-categories) methods. I suggest that Cat should have an attribute that allows Cat.hom_category() to assign the correct category to the homset category (hence, Cat.hom_category().is_subcategory(Cat.hom_structure)), so that homomorphism would inherit from Cat.hom_structure.element_class (by the existing framework - hence, my suggestion is indeed very consistent with with the existing framework :-).

Is there any reason to not have a double inheritance from Cat.morphism_class and Cat.hom_structure.element_class (Cat.hom_structure being a category)?

So let's both
write a little prototype to have a concrete ground to discuss on. We
don't have to include the coercion / push_out part in this prototype
since we agree on it. I can try to implement mine sometime next week.

OK.

Cat.HomCategory() will still use the standard super_categories()
approach to state that it is a subcategory of VectorSpaces(), and its
elements will inherit from VectorSpaces().element_class.

OK, this is what I suggested above: One needs to introduce a standard mechanism to declare the category which Cat.hom_category() is sub-category of.

[nthiery]

comment:9

But what would actually prevent us from doing both?

Ah, good, we now fund the point were we did not understand each
other. The plan is definitely to do both! That is have inheritance
from Cat.morphism_class and Cat.hom_category().element_class.

OK, this is what I suggested above: One needs to introduce a
standard mechanism to declare the category which
Cat.hom_category() is sub-category of.

And that's a second misunderstanding: this mechanism already exists,
and I am not planning to remove it (though the syntax might change a
tiny bit; we probably don't need the extra_super_categories thingy,
and just use super_categories.

What do you think of using the occasion to rename Cat.hom_category()
into Cat.Homsets(), for consistency with Cat.Quotients() and the like?

Cheers,
Nicolas

[simon-king-jena]

comment:10

Replying to @nthiery:

OK, this is what I suggested above: One needs to introduce a
standard mechanism to declare the category which
Cat.hom_category() is sub-category of.

And that's a second misunderstanding: this mechanism already exists,
and I am not planning to remove it (though the syntax might change a
tiny bit; we probably don't need the extra_super_categories thingy,
and just use super_categories.

What mechanism do you mean? I am of course aware of the extra_super_category method - but sage.categories.category.HomCategory.extra_super_category() returns [], and sage.categories.category.HomCategory.super_categories() returns stuff that we don't want (namely C.hom_category() for all C in self.base_category.super_categories()).

Of course, it would suffice to make VectorSpaces(QQ).hom_category().extra_super_categories() return [VectorSpaces(QQ)]. But this would currently require to introduce a custom HomCategory class for VectorSpaces that overrides the method of the HomCategory base class. This is not nice and should be simplified.

What I plan is: Remove inheritance of the hom-categories of the super-categories of the base-category from sage.categories.category.HomCategory.super_categories(); it should basically return self.extra_super_categories()+[Sets()]. Moreover, define sage.categories.category.HomCategory.extra_super_categories() like this:

def extra_super_categories(self):
    try:
        return [self.base_category.hom_structure]
    except AttributeError:
        return []

Then, in the init-method of the category of vector spaces, one would simply add the line

        self.hom_structure = self

Similarly (I hope that I am not confusing things now), one would add the line

        self.hom_structure = LeftModules(self.base_ring())

to the init method of right modules; and self.hom_structure = RightModules(self.base_ring()) for left modules, and so on. That seems easier than defining a whole class HomCategory for LeftModules.

What do you think of using the occasion to rename Cat.hom_category()
into Cat.Homsets(), for consistency with Cat.Quotients() and the like?

Personally, I don't like uppercase method names, and I remember that it is officially recommended to avoid capital letters in Python method or function or module names, whereas upper case is recommended to use for classes (but I do not remember where I was reading that recommendation).

Best regards,

Simon