Infrastructure for modelling full subcategories

[nthiery]

It has been desired for a while to be able to test, when B is a subcategory of A, whether it is a full subcategory or not; equivalently this is whether any A-morphism is a B-morphism (up to forgetfull functor; note that the converse always holds).

The main application is for #10668, which will let B.homset_class inherit from A.homset_class in this case and only in this case.

References

• http://trac.sagemath.org/wiki/CategoriesRoadMap
• The discussion around #10668 comment:16
• The terminology is subject to Improve the terminology for the hierarchy relation between categories #16183

Implementation proposal

For each category C, we encode the following data: is C is a full
subcategory of the join of its super categories? Informally, the
question is whether C introduces more structure or operations. For
the sake of the discussion, I am going to call C a structure
category in this case, but a better name is to be found.

Here are some of the main structure categories in Sage, and the
structure or main operation they introduce:

• AdditiveMagmas: +
• AdditiveMagmas.AdditiveUnital: 0
• Magmas: *
• Magmas.Unital: 1
• Module: . (product by scalars)
• Coalgebra: coproduct
• Hopf algebra: antipode
• Enumerated sets: a distinguished enumeration of the elements
• Coxeter groups: distinguished coxeter generators
• Euclidean ring: the euclidean division
• Crystals: crystal operators

Possible implementation: provide a method C.is_structure_category()
(name to be found). The default implementation would return True for
a plain category and False for a CategoryWithAxiom. This would cover
most cases, and require to implement foo methods only in a few
categories (e.g. the Unital axiom categories).

Once we have this data encoded, we can implement recursively a
(cached) method such as:

    sage: Rings().structure_super_categories()
    {Magmas(), AdditiveMagmas()}

(just take the union of the structure super categories of the super
categories of ``self``, and add ``self`` if relevant).

It is now trivial to check whether a subcategory B of A is actually a
full subcategory: they just need to have the same structure super
categories! Hence is_full_subcategory can be written as:

    def is_full_subcategory(self, other):
        return self.is_subcategory(other) and
           len(self.structure_super_categories()) == len(other.structure_super_categories())

Advantages of this proposal

This requires very little data to be encoded, and should be quite
cheap to compute.

This is generally useful; in particular, for a user, the structure
super categories together with the axioms would give an interesting
overview of a category:

    sage: Rings().structure_super_categories()
    {Magmas(), AdditiveMagmas()}
    sage: Rings().axioms()
    frozenset({'AdditiveAssociative', 'AdditiveCommutative', 'AdditiveInverse', 'AdditiveUnital', 'Associative', 'Distributive', 'Unital'})

In fact, we could hope/want to always have:

    C is Category.join(C.structure_super_categories()).with_axioms(C.axioms())

which could be used e.g. for pickling by construction while exposing
very little implementation details.

Bonus

Each structure category could name the main additional operations, so
that we could have something like:

    sage: Magmas().new_operation()
    "+"
    sage: Rings().operations()
    {"+", "0", "*", "1"}

or maybe:

    sage: Rings().operations()
    {Category of additive magmas: "+",
     Category of additive unital additive magmas: "0",
     Category of magmas: "*",
     Category of unital magmas: "1"}

Limitation

The current model forces the following assumption: C \subset B \subset A is a chain of categories and C is a full subcategory of A, then
C is a full subcategory of B and B is a full subcategory of A.
In particular, we can't model situations where, within the context of
C, any A morphism is in fact a B morphism because the B
structure is rigid.

Example: C=Groups, B=Monoids, A=Semigroups.

This is documented in details in the methods .is_fullsubcategory and
.full_super_categories.

Questions

• Find good names for all the methods above

• Ideas on how to later lift the limitation?

CC: @sagetrac-sage-combinat @hivert @simon-king-jena @darijgr @nbruin @pjbruin @vbraun

Component: categories

Keywords: full subcategories, homset

Author: Nicolas M. Thiéry

Branch: eb621c7

Reviewer: Darij Grinberg, Travis Scrimshaw, Simon King

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

[nthiery]

comment:1

Suggestions anyone before I start implementing this?

Cheers,

[darijgr]

comment:2

Ideally, for every piece of algebraic structure there should be both a full and a fully structure-aware subcategory. So there should be a UnitalAlgebrasWithUnitalMorphisms and a UnitalAlgebrasWithArbitraryMorphisms, etc.; more importantly, there should be categories for graded modules with graded morphisms and with arbitrary morphisms (I don't remember out of the hat which is the one we have) and categories for modules-with-basis with basis-preserving morphisms and with arbitrary morphisms etc.. This might not belong into this ticket, but please make sure that your model takes this into account and does not handle fullness as a hardcoded property of the relevant axiom / functorial construct.

Other than this I like the proposal!

[tscrim]

comment:3

Is it possible to have a proper subcategory (within Sage) which has the same number, but actually different set, of operators (i.e. is len a sufficient check or do we need to compare sorted lists)? I'm pretty sure this is mathematically wrong, but can someone confirm.

[nthiery]

Branch: u/nthiery/categories/full-subcategories-16340

[nthiery]

Commit: 2f2d09b

[nthiery]

comment:5

Replying to @darijgr:

Ideally, for every piece of algebraic structure there should be both a full and a fully structure-aware subcategory. So there should be a UnitalAlgebrasWithUnitalMorphisms and a UnitalAlgebrasWithArbitraryMorphisms, etc.; more importantly, there should be categories for graded modules with graded morphisms and with arbitrary morphisms (I don't remember out of the hat which is the one we have) and categories for modules-with-basis with basis-preserving morphisms and with arbitrary morphisms etc.

Agreed.

This might not belong into this ticket, but please make sure that your model takes this into account and does not handle fullness as a hardcoded property of the relevant axiom / functorial construct.

I guess that's alright: when we will want both, we will just need to
have two distinct categories/axioms/functorial construction for the
two situations. I am missing a good idiom / naming convention though.

In the mean time, the current implementation makes a default choice on
a case by case basis, according to the foreseen main use case for the
category (see the doc).

Other than this I like the proposal!

Cool. I just pushed a first attempt. It's probably reasonably
complete. The main things that need discussion are:

• Terminology and method names

• Are there categories which need special handling that I missed?

• The default choices I have made.

Cheers,
Nicolas

---

Last 10 new commits:

54c3d67	#15801: Initialize the base ring for module homsets
aa01591	#15801: doctests for CategoryObjects.base_ring + docfix in Modules.SubcategoryMethods.base_ring
79f4766	Merge branch 'public/categories/over-a-base-ring-category-15801' of trac.sagemath.org:sage into public/categories/over-a-base-ring-category-15801
281f539	Added back in import statement as per comment.
96c631f	Merge branch 'develop' into categories/axioms-10963
b1a2aed	Trac 10963: two typo fixes to let the pdf documentation compile
c16f18b	Merge branch 'public/ticket/10963-doc-distributive' of trac.sagemath.org:sage into categories/axioms-10963
dcb11d8	Merge branch 'categories/axioms-10963' into categories/over_a_base_category-15801
15658bd	Trac 15801: fixed merge with #12630
2f2d09b	16340: infrastructure for modelling full subcategories

[nthiery]

comment:6

Replying to @tscrim:

Is it possible to have a proper subcategory (within Sage) which has the same number, but actually different set, of operators (i.e. is len a sufficient check or do we need to compare sorted lists)? I'm pretty sure this is mathematically wrong, but can someone confirm.

In the current implementation, we are comparing the set of all super categories that define some structure. This set can only become larger for inclusion when going down the category hierarchy. So technically we are fine.

And this implementation seems to correctly models the mathematics, right?

[pjbruin]

comment:8

I haven't had time to look at this in detail, but at first sight it looks like a good approach to me.

For me the main point to think about is the terminology "structure category". It would be nice if the name made it slightly clearer that this property is not so much about the category itself as about its relation to its supercategories. (Some random alternative names for is_structure_category(): adds_structure()? is_augmented_category()? is_enriched_category()?)

[nthiery]

comment:9

Replying to @pjbruin:

For me the main point to think about is the terminology "structure category".
It would be nice if the name made it slightly clearer that this property is not so much about the category itself as about its relation to its supercategories.

Definitely!

(Some random alternative names for is_structure_category(): adds_structure()? is_augmented_category()? is_enriched_category()?)

Also, instead of an "is_..." method, we could name the method something like additional_structure and have it return something possibly meaningfull, like "*" for magmas or "+" for additive magmas, and None if there is none. It would still evaluate appropriately to True/False in boolean context.

[simon-king-jena]

comment:10

Replying to @nthiery:

Also, instead of an "is_..." method, we could name the method something like additional_structure and have it return something possibly meaningfull, like "*" for magmas or "+" for additive magmas, and None if there is none.

Or, even more informative: Return a pair (op, method), such that

• op is the operator (either as in operator.contains, operator.mul, operator.and, or a parent/element method such as an_element), and
• method is an abstract parent/element method that has to be implemented for op (i.e., __contains__, _mul_, or _an_element)

[nthiery]

comment:11

Replying to @simon-king-jena:

Or, even more informative: Return a pair (op, method), such that

• op is the operator (either as in operator.contains, operator.mul, operator.and, or a parent/element method such as an_element), and
• method is an abstract parent/element method that has to be implemented for op (i.e., __contains__, _mul_, or _an_element)

Possibly so indeed. Although this would be duplicating a bit the job
of required_methods. I am not sure we want to put a specific
emphasis on the methods related to an operation that adds structure
(e.g. '+') or that does not (e.g. '-').

Speaking of which: see #16363.

[nthiery]

comment:12

Any other suggestions for the terminology? At this point, I am leaning toward additional_structure. But there remains to name "structure categories", and the method returning all the super "structure categories".

[nthiery]

comment:13

One thing I don't know how to handle. Assume we want the morphisms of euclidean rings to preserve euclidean division (I'd say that this is equivalent to preserving the degree). Then, EuclideanDomains() is not a full subcategory of Rings(). Yet Fields(), which is a subcategory of EuclideanDomains(), is a full subcategory of Rings(). This is because the additional structure defined by EuclideanDomains() (the degree) is trivial in this case.

We can't model this in the current implementation. An approach might be to have Fields() explicitly remove EuclideanDomains() from its structure categories. But then we have to be more careful in the full subcategory test. Maybe we can test, for B a subcategory of A that B.super_structure_categories() is a subset of A.super_structure_categories(); given that we hash and check for equality by id, that should be fast enough if deemed correct.

A similar situation appears for graded connected hopf algebras where there is a single choice for the antipode (and, IIRC, it's preserved for free by bialgebra morphisms). So this is a full subcategory of the category of bialgebras.

Cheers,
Nicolas

[sagetrac-git]

Changed commit from 2f2d09b to c06e2ef

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c06e2ef

16340: added full_super_categories method, a test, and some doc

[rwst]

comment:15

Error building the documentation.
Traceback (most recent call last):
  File "/home/ralf/sage/src/doc/common/builder.py", line 1477, in <module>
    getattr(get_builder(name), type)()
  File "/home/ralf/sage/src/doc/common/builder.py", line 276, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/home/ralf/sage/src/doc/common/builder.py", line 487, in _wrapper
    x.get(99999)
  File "/home/ralf/sage/local/lib/python/multiprocessing/pool.py", line 554, in get
    raise self._value
OSError: [categorie] /home/ralf/sage/local/lib/python2.7/site-packages/sage/categories/category_with_axiom.py:docstring of sage.categories.category_with_axiom.CategoryWithAxiom.is_structure_category:7: WARNING: Literal block expected; none found.

make: *** [doc-html] Error 1

[sagetrac-git]

Changed commit from c06e2ef to 2b0164b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2b0164b

16340: trivial ReST fix

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b6342d1

Merge branch 'develop' into categories/full-subcategories-16340

[sagetrac-git]

Changed commit from 2b0164b to b6342d1

[nthiery]

Work Issues: find good names

[sagetrac-git]

Changed commit from 60aa128 to 950b039

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

950b039

16340: Merge branch 'develop = 6.4 beta4' into categories/full-subcategories-16340

[sagetrac-git]

Changed commit from 950b039 to b14ca6c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b14ca6c

16340: revert change, and add documentation thereabout: the category of permutation groups defines additional structure

[nthiery]

comment:56

For info: Simon is sitting with me in Orsay, and we will be banging
together on this ticket and follow ups in the next few days.

Expect some action :-) Finally!

Cheers,
Nicolas

[sagetrac-git]

Changed commit from b14ca6c to 43b25d4

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

43b25d4

16340: is_structure_category -> additional_structure, all_super_structure_categories -> structure, default for functorial construction categories

[sagetrac-git]

Changed commit from 43b25d4 to eb621c7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

eb621c7

Fixing some typos

[simon-king-jena]

comment:59

I went through all of the diff, fixed some typos, and I checked that with #10668 all tests pass. To be on the safe side, I will re-run certain tests with this branch, but it is close to a positive review.

[simon-king-jena]

Changed reviewer from Darij Grinberg, Travis Scrimshaw to Darij Grinberg, Travis Scrimshaw, Simon King

[simon-king-jena]

comment:60

Replying to @pjbruin:

Is it clear that the "structure category" terminology is the way to go? Personally I still don't like it very much (again, it pretends to be about categories but instead is about relations to their supercategories). I would prefer the proposals made by Nicolas in comment:9 and Simon in comment:10 to have an additional_structure() method that returns something meaningful about the additional structure, not just True or False.

This is not really addressed yet: There is additional_structure, but it returns self or None.

Anyway, I am still somewhat confident that I can make something out of the idea to use Gröbner bases in boolean polynomial rings to deal with deduction rules (à la Wedderburn Theorem) for axioms and structures. And then, it would be a matter of filling a dictionary with information about what structure corresponds to what operation.

[simon-king-jena]

comment:61

Replying to @tscrim:

Replying to @pjbruin:

It may be because I'm still misled by the terminology, but I'm afraid this only increases my confusion about what functorial construction categories are. In what sense do "topological" and "metric" have something to do with modelling codomains of a collection of functors? (Of course topological/metric spaces can be domains/codomains of functors, but I don't think this is what Nicolas meant in comment:49).

To me "topological" and "metric" are examples of "extra structure", in the sense that there are canonical functors (metric spaces) -> (topological spaces) -> (sets). In the current Sage implementation/parlance, I guess they would be regarded as examples of axioms.

This may not be the right way, but I think of these functional construction categories as additional data to some base category C in which every object of C has a natural way to construct this data that preserves the morphisms. For graded, make everything be in the 0-th graded part. For metric/topological, give it the discrete metric/topology.

Actually running with that example, an object in graded algebras would be the pair (A, deg), right? So if we consider the section of the forgetful function where deg(x) = 0 for all x in A, this would have algebras as a full subcategory of graded algebras, right? So I think we might need to be careful with how we are considering the base categories inside of the functorial construction category. On that, I reverse my position, functorial construction categories should not be structure categories because of the natural inclusion mentioned above (unless I'm wrong).

I am not very much confident about the functorial constructions either. I am (re-)reading the chapter on functorial constructions in the category primer right now.

Anyway, it seems to me that Nicolas has addressed the concerns expressed here (I was rereading all comments), the code is relatively clear (to me, the unclear parts concern things that existed before, like functorial constructions), and moreover all tests pass. So, if nobody objects, I am putting this to positive review, after reading the chapter in the primer...

[simon-king-jena]

comment:62

Hm. I did not find the category primer very helpful, as it only gives an example (cartesian product) on objects. But it does not tell what actually happens to the categories, and it does not tell how it is defined, nor how it is implemented. I somehow recall from reviewing it how it was implemented, but I would not easily be able to provide a mathematical definition.

Anyway. The new code that we are discussing here seems good to me.

[vbraun]

Changed branch from public/categories/full_subcategories-16340 to eb621c7

[nthiery]

Changed commit from eb621c7 to none

[nthiery]

comment:64

Yeah! Thanks everyone for the review!

[nathanncohen]

comment:65

O_o

Wasn't there a way to make all these classes inherit the additional_structure -> return None function ?..

Nathann

[simon-king-jena]

comment:66

Replying to @nathanncohen:

O_o

Wasn't there a way to make all these classes inherit the additional_structure -> return None function ?..

Probably not, if you talk about the case that return self is the default for categories that are not CategoryWithAxiom.

If you have a default (which here is chosen so that the test for a full subcategory will not give a false-positive answer by default), then you need to do something special for all cases that are special.

[nathanncohen]

comment:67

Yo !

Probably not, if you talk about the case that return self is the default for categories that are not CategoryWithAxiom.

If you have a default (which here is chosen so that the test for a full subcategory will not give a false-positive answer by default), then you need to do something special for all cases that are special.

Hmmmmm... Then perhaps only a flag when this infrastructure is initialized ? Doesn't matter much I guess, I it just unpleasant to see the same (empty) function being copy/pasted one thousand times.

Nathann

[simon-king-jena]

comment:68

Replying to @nathanncohen:

Hmmmmm... Then perhaps only a flag when this infrastructure is initialized ? Doesn't matter much I guess, I it just unpleasant to see the same (empty) function being copy/pasted one thousand times.

Or an attribute _adds_structure, and then define something like the following:

def additional_structure(self):
    if getattr(self._adds_structure, None):
        return self

In that way, the method additional_structure would be defined only in three places (default for categories, for categories with axiom, and for functorial constructions), and non-default behaviour could be requested more light-weight.

Nicolas, what do you think about it? To me, it sounds like a good idea.

[nathanncohen]

comment:69

Also, if I may say: the name "additional_structure" is like VERY vague. Perhaps this is the best you can do on the "mathematical side" of the feature, but it may be possible to give it a more informative name describing what exactly this parameter does, i.e. a more code-specific description.

But of course I have absolutely no idea of what I am talking about.

Nathann

[nthiery]

comment:70

Replying to @nathanncohen:

Wasn't there a way to make all these classes inherit the additional_structure -> return None function ?..

Yeah, I agree it's verbose looking. But I am actually quite happy that
the design allowed us to explicitly insert so few additional
information :-)

With this ticket, we are really adding a not so trivial mathematical
information to almost 260+ categories (what shall, or not, be
preserved by morphisms); thanks to the chosen defaults (which depend
on whether we have a category with axiom, a construction category, or
...) we had to special case only about 20 categories. For each of
them, there was a conscious design decision taken, some of which took
a bit of discussion; each such decision has to be documented and
tested. Hence we really want the doctests. In particular, having an
attribute instead of a method would not save anything.

Cheers,
Nicolas

[nthiery]

comment:71

Replying to @nathanncohen:

Also, if I may say: the name "additional_structure" is like VERY vague. Perhaps this is the best you can do on the "mathematical side" of the feature, but it may be possible to give it a more informative name describing what exactly this parameter does, i.e. a more code-specific description.

I am open to suggestions. This is completely local to categories and easy to change. That being said, since it's a method on categories, the context is rather well specified. And in this context, it's rather customary to say things like ``a ring is a set endowed with a structure of unital magma and unital additive magma satisfying the axioms xxx'':

sage: Rings().structure()
frozenset({Category of additive unital additive magmas,
           Category of additive magmas,
           Category of unital magmas,
           Category of magmas,
           Category of sets with partial maps,
           Category of sets})
sage: Rings().axioms()
frozenset({'AdditiveAssociative',
           'AdditiveCommutative',
           'AdditiveInverse',
           'AdditiveUnital',
           'Associative',
           'Distributive',
           'Unital'})

(btw: for that purpose, in the first example above, we might want to have a separate method that returns only the lowest categories, i.e. unital magmas and additive unital magmas).

Then, from "structure" to "additional structure", the leap is not too big.

Cheers,
Nicolas