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 ​http://trac.sagemath.org/ticket/10668#comment:16
• The terminology is subject to #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?

[nthiery]

Suggestions anyone before I start implementing this?

Cheers,

[darij]

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]

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]

Replying to darij:

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]

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?

[pbruin]

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]

Replying to pbruin:

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.

[SimonKing]

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]

Replying to SimonKing:

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]

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]

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

[git]

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

​c06e2ef

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

[rws]

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

[git]

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

​2b0164b

16340: trivial ReST fix

[git]

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

​b6342d1

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

[chapoton]

There are some failing doctests, see patchbot report.

[tscrim]

I've fixed the trivial doctest failures in category.py. I get the same warning messages about the stack size using develop and I don't see any additional memory usage without this branch (so I'd say we can ignore those). I don't get any of the other failures.

---

New commits:

​93273a7	Merge branch 'u/nthiery/categories/full-subcategories-16340' of trac.sagemath.org:sage into public/categories/full_subcategories-16340
​edb29e6	Fixed trivial doctest failures.

[git]

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

​eaa56bc	16340: super_structure_categories -> all_structure_super_categories
​afc9724	Merge branch 'develop' into categories/full-subcategories-16340
​99a8eb1	Merge branch 'public/categories/full_subcategories-16340' of trac.sagemath.org:sage into categories/full-subcategories-16340
​8bc456c	Merge branch 'master=6.3' into categories/full-subcategories-16340

[aschilling]

Simon, could you review this ticket since we need it for other applications? Thanks!

[git]

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

​737a8f0

16340: improved warnings about the current limitation of the model

[nthiery]

I put here for the record a summary of a private discussion by e-mail.

Darij:

I don't see any better names than "full" and "structure" subcategory. In my opinion, these are clear and don't conflict with common usage. While I am still not very keen on the name "subcategory" itself, we can keep the "full" and "structure" adjectives even if we change it.

Travis:

This is the big thing that we needed. I can do the rest of the review at this point I think. However thanks for looking things over and giving us your notes.

Darij:

<pointing to the limitation now explicitly mentioned in the description of the ticket>

Nicolas:

I believe that this limitation could be raised, though at this point I don't quite know what's the best approach. I also don't see a critical need (it's already a good progress). So, as long as it's properly documented (I just reworked that piece of the documentation; now it's up to you guys to judge), I think that's fine for now.

[git]

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

​282ac4e

16340: fixed typos reported by Darij

[git]

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

​e5f210c	Merge branch 'public/categories/full_subcategories-16340' of trac.sagemath.org:sage into public/categories/full_subcategories-16340
​d4c7a88	Specified more categories as not being structure categories.

[tscrim]

I made some other categories into non-structure categories. This made me wonder if we actually want the default category be a structure category. Yet I don't think we have enough data currently to answer this right now. I'm going to double-check to make sure I didn't miss any others and I'd appreciate if someone else could do the same. Otherwise I think we're okay to positive review it.

Darij, I've added you as a reviewer since you did look over the code and give suggestions.

[pbruin]

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.

[tscrim]

Replying to pbruin:

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).

It's more of there has been no better alternative proposed. If we move away from the terminology "structure category", then I feel like we loose the ability to name methods like all_structure_super_categories. However I do understand your objection.

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.

Currently the default is that new subcategories are structure categories (so they are not full subcategories). If we were to go with returning pairs (op, method), then the question becomes do we want the default to be False or do we allow True to remain the default and have it be when we can't adequately define the structure?

Actually, that made me have a thought. How about instead of is_structure_category we have has_additional_structure, and then we could extend this to additional_structure (on a followup ticket).

[pbruin]

Hi Travis,

Replying to pbruin:

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).

It's more of there has been no better alternative proposed. If we move away from the terminology "structure category", then I feel like we loose the ability to name methods like all_structure_super_categories. However I do understand your objection.

After looking at the code, I actually have the feeling that this all_structure_super_categories() method is a somewhat unnatural solution to the question of determining whether one category is a full subcategory of another. At first sight it looks like a category should be able to simply declare if is it a full subcategory of its supercategories (for each supercategory individually, if necessary). Then is_full_subcategory(), given two categories, could check if there is a sequence of full subcategory inclusions between the two categories.

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.

Currently the default is that new subcategories are structure categories (so they are not full subcategories). If we were to go with returning pairs (op, method), then the question becomes do we want the default to be False or do we allow True to remain the default and have it be when we can't adequately define the structure?

Hmm, it doesn't sound very desirable to define a category where you can't define what its extra structure is...

Actually, that made me have a thought. How about instead of is_structure_category we have has_additional_structure, and then we could extend this to additional_structure (on a followup ticket).

This sounds good. We could go even further and formalise the notion of category with extra structure, so we would have

1. CategoryWithAxiom: like the existing class, but more restrictive. Specifies an additional axiom to be satisfied by the objects, and defines the full subcategory objects satisfying this axiom. For example, commutativity for groups.
2. CategoryWithStructure: proposed new class. Specifies an additional structure on objects that must be preserved by morphisms, and defines a usually non-full subcategory.

In certain cases something that is now called an axiom would become an extra structure. For example (thinking about the discussion on #16843) the Unital property for rings (as a subcategory of Rngs) would become a structure instead of an axiom, because morphisms are restricted by the requirement that they preserve the unit element.

[nthiery]

Replying to tscrim:

I made some other categories into non-structure categories.

Thanks. I double checked on this, and mostly agree up to one point: I think Coxeter Groups should be a structure category, the extra structure being the chosen set of simple generators.

This made me wonder if we actually want the default category be a structure category.

I believe this would be dangerous. Being accidently a structure category means that your homsets will miss some code that could be available. So just a missing feature. Whereas being accidently a non structure category can let your homset inherit from code that is not applicable which can lead to wrong code.

Besides, all the categories your changed should actually become CategoryWithAxioms? at some point, which will have precisely the desired effect.

So now one could wonder whether having a CategoryWithAxiom? be a non structure category is not a dangerous default. I believe it's ok, because for a category with axiom A.B, one only has to be careful about being a full subcategory or not if A is the category defining the axiom B. There are not soo many of them.

I'm going to double-check to make sure I didn't miss any others and I'd appreciate if someone else could do the same.

Thanks!

Cheers,

Nicolas

[nthiery]

Replying to pbruin:

At first sight it looks like a category should be able to simply declare if is it a full subcategory of its supercategories (for each supercategory individually, if necessary). Then is_full_subcategory(), given two categories, could check if there is a sequence of full subcategory inclusions between the two categories.

That was the original plan, but this means having to encode much more information. And it's quite more costly to compute.

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.

Currently the default is that new subcategories are structure categories (so they are not full subcategories). If we were to go with returning pairs (op, method), then the question becomes do we want the default to be False or do we allow True to remain the default and have it be when we can't adequately define the structure?

Hmm, it doesn't sound very desirable to define a category where you can't define what its extra structure is...

But this is imposing the category writer to do implement one more thing, when implementing a category is already a barrier. Being a full subcategory only adds extra features to homsets. In most cases, when implementing a category for the first time, one does not need this feature. So being able to just not have to worry about it is a definite plus.

Actually, that made me have a thought. How about instead of is_structure_category we have has_additional_structure, and then we could extend this to additional_structure (on a followup ticket).

Possibly so. What would be the names for all the related methods (like all_structure_categories)?

This sounds good. We could go even further and formalise the notion of category with extra structure, so we would have

1. CategoryWithAxiom: like the existing class, but more restrictive. Specifies an additional axiom to be satisfied by the objects, and defines the full subcategory objects satisfying this axiom. For example, commutativity for groups.
2. CategoryWithStructure: proposed new class. Specifies an additional structure on objects that must be preserved by morphisms, and defines a usually non-full subcategory.

In certain cases something that is now called an axiom would become an extra structure. For example (thinking about the discussion on #16843) the Unital property for rings (as a subcategory of Rngs) would become a structure instead of an axiom, because morphisms are restricted by the requirement that they preserve the unit element.

We want Unital to have all the other features of axioms like:

    sage: Rngs() & Semigroups().Unital()
    Category of Rings

So this would require a more complicated hierarchy of classes, especially since one would also need to take care of the over_base_ring variations. I am not sure this is worth it for just a single method.

By the way: Semigroups().Unital() is indeed a structure category. But not Rngs().Unital(): all the structure is defined in the super categories Rngs() and Semigroups().Unital().

Also: there is room for improvement in functorial constructions: in some cases, we could automatically deduce that the category is a structure category. I believe this is easier to implement by mean of methods than by inheriting from one class or the other (and past has proven that I can live with class surgery when needed).

Cheers,

Nicolas

[tscrim]

Replying to nthiery:

Thanks. I double checked on this, and mostly agree up to one point: I think Coxeter Groups should be a structure category, the extra structure being the chosen set of simple generators.

I don't think so. If we wanted the generators to be part of the structure (definition), that should be the category of Coxeter syetems as it is much more rigid than just the groups.

This made me wonder if we actually want the default category be a structure category.

I believe this would be dangerous. Being accidentally a structure category means that your homsets will miss some code that could be available. So just a missing feature. Whereas being accidentally a non structure category can let your homset inherit from code that is not applicable which can lead to wrong code.

I agree with this, although my thought is more about how many categories will we have are structure categories. As I stated, we need more data and I agree that having this default is the safe route.

Besides, all the categories your changed should actually become CategoryWithAxioms? at some point, which will have precisely the desired effect.

Probably.

So now one could wonder whether having a CategoryWithAxiom? be a non structure category is not a dangerous default. I believe it's ok, because for a category with axiom A.B, one only has to be careful about being a full subcategory or not if A is the category defining the axiom B. There are not soo many of them.

Most axioms that come to my mind adds extra structure, but we can see what happens as we add more axioms.

I'm going to double-check to make sure I didn't miss any others and I'd appreciate if someone else could do the same.

Thanks!

Thanks for double-checking my double-check.

Replying to nthiery:

Possibly so. What would be the names for all the related methods (like all_structure_categories)?

With this, we could keep the same names (although I believe the method your referring to is all_structure_super_categories).

Are we all in agreement that we should change is_structure_category to has_additional_structure and the current framework is a good enough to merge in (since it could be extended at a later date to carry additional info)?

[pbruin]

Hi Nicolas,

Replying to pbruin:

At first sight it looks like a category should be able to simply declare if is it a full subcategory of its supercategories (for each supercategory individually, if necessary). Then is_full_subcategory(), given two categories, could check if there is a sequence of full subcategory inclusions between the two categories.

That was the original plan, but this means having to encode much more information. And it's quite more costly to compute.

I don't see why this should necessarily be the case; we would just encode for each direct supercategory (of which there are usually just one or two) whether it is a full supercategory. This makes computing all full supercategories not any slower (and probably faster) than computing all supercategories, or presumably all "structure supercategories" for that matter.

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.

Currently the default is that new subcategories are structure categories (so they are not full subcategories). If we were to go with returning pairs (op, method), then the question becomes do we want the default to be False or do we allow True to remain the default and have it be when we can't adequately define the structure?

Hmm, it doesn't sound very desirable to define a category where you can't define what its extra structure is...

But this is imposing the category writer to do implement one more thing, when implementing a category is already a barrier. Being a full subcategory only adds extra features to homsets. In most cases, when implementing a category for the first time, one does not need this feature. So being able to just not have to worry about it is a definite plus.

It seems to me that the first thing one has to do when defining a category (and maybe the only essential thing!) should be to decide how to encode its mathematical meaning. The distinction between adding a new axiom to the objects (thereby creating a full subcategory) and adding a new type of structure (thereby creating a relationship that I was thinking of as "category refinement" in earlier discussions) is really fundamental in my opinion.

Actually, that made me have a thought. How about instead of is_structure_category we have has_additional_structure, and then we could extend this to additional_structure (on a followup ticket).

Possibly so. What would be the names for all the related methods (like all_structure_categories)?

This sounds good. We could go even further and formalise the notion of category with extra structure, so we would have

1. CategoryWithAxiom: like the existing class, but more

restrictive. Specifies an additional axiom to be satisfied by the objects, and defines the full subcategory objects satisfying this axiom. For example, commutativity for groups.

2. CategoryWithStructure: proposed new class. Specifies an

additional structure on objects that must be preserved by morphisms, and defines a usually non-full subcategory. In certain cases something that is now called an axiom would become an extra structure. For example (thinking about the discussion on #16843) the Unital property for rings (as a subcategory of Rngs) would become a structure instead of an axiom, because morphisms are restricted by the requirement that they preserve the unit element.

We want Unital to have all the other features of axioms like:

    sage: Rngs() & Semigroups().Unital()
    Category of Rings

Of course, this type of construction should stay the same.

So this would require a more complicated hierarchy of classes, especially since one would also need to take care of the over_base_ring variations. I am not sure this is worth it for just a single method.

On the contrary, I think it there is an essential distinction between just adding an axiom to the objects (hence creating a full subcategory) and adding "extra structure". (By the way, "over a base ring" is actually something that I am thinking of as another example of "extra structure".)

By the way: Semigroups().Unital() is indeed a structure category. But not Rngs().Unital(): all the structure is defined in the super categories Rngs() and Semigroups().Unital().

This actually strengthens my conviction that "structure category" is not a well-defined notion. Instead, I have the impression that the structure should be regarded as being attached to what is currently called the "axiom" rather than to the category.

In this example, it depends on how you define Rings(): either as Rngs() & Semigroups().Unital(), in which case it is just a join of categories without new structure, _or_ as Rngs().Unital(), in which it does have extra structure (at least at first sight; you have to know that the category code magically rearranges the construction to turn Rngs().Unital() into a join of larger categories). In fact, Semigroups().Unital() (= Monoids()) is not a structure category either; it is the join of Magmas().Unital() and Semigroups().

Also: there is room for improvement in functorial constructions: in some cases, we could automatically deduce that the category is a structure category.

I am wondering how you could possibly detect such a thing. In the case of the Unital() structure (correct me if this is somehow an exception), how do you know that this does not just mean the existence of a unit element in the objects, but also the requirement that morphisms preserve this element? This seems to me precisely the type of information that has to be specified by the person implementing the Unital() structure.

[nthiery]

Replying to tscrim:

I don't think so. If we wanted the generators to be part of the structure (definition), that should be the category of Coxeter syetems as it is much more rigid than just the groups.

Both concepts are useful, but it's far from clear for me that we want to maintain both categories Coxeter groups / coxeter systems. Given that:

• Our Coxeter groups all come endowed with a distinguished set of generators.

• It's easier to change a structure category to a non structure category than the converse (since it's adding features).

• With the current setting, we already have both concepts: e.g. when constructing a morphism between two coxeter groups, you can choose to construct it as a group morphism or as a Coxeter group morphism.

I agree with this, although my thought is more about how many categories will we have are structure categories. As I stated, we need more data and I agree that having this default is the safe route.

I agree that we need more data. My bet is that most categories will be either structure categories or categories with axioms.

Most axioms that come to my mind adds extra structure, but we can see what happens as we add more axioms.

Do they? So far, only one of the existing axioms (Unital and its additive variant) add extra structure. And the one I am thinking for the future don't add extra structure (about monoids: L,R,J-Trivial, ...).

With this, we could keep the same names (although I believe the method your referring to is all_structure_super_categories).

If we switch to has_additional_structure, it feels like we are not using structure as an adjective for qualifying a category anymore, but rather as a noun. So all_structure_super_categories does not really make sense. On the other hand, we could possibly name this method "structure":

sage: Rings().structure() [Category of unital magmas, Category of additive unital additive magmas]

We could actually get rid of "has_additional_structure" altogether, and instead have C.additional_structure() return C by default, with the possibility to override it to return None, or, in the future, something more meaningful than C.

Cheers,

Nicolas

[nthiery]

Replying to pbruin:

This actually strengthens my conviction that "structure category" is not a well-defined notion.

It's perfectly defined: C is a structure category if whenever A and B are in C and phi is a morphism between A and B for any strict super category of C, then phi is a C morphism. And it coincides with the intuition we have of it: does C define some additional structure (typically an operation) that has to be preserved by C-morphisms.

Instead, I have the impression that the structure should be regarded as being attached to what is currently called the "axiom" rather than to the category.

In this example, it depends on how you define Rings(): either as Rngs() & Semigroups().Unital(), in which case it is just a join of categories without new structure, _or_ as Rngs().Unital(), in which it does have extra structure (at least at first sight; you have to know that the category code magically rearranges the construction to turn Rngs().Unital() into a join of larger categories). In fact, Semigroups().Unital() (= Monoids()) is not a structure category either; it is the join of Magmas().Unital() and Semigroups().

I don't see why Rngs().Unital() should suggest it's a structure category. A.Unital() is never a structure category unless A is the category defining Unital. That is A=Magmas().

I don't see why this should necessarily be the case; we would just encode for each direct supercategory (of which there are usually just one or two) whether it is a full supercategory.

Well, I tried, and the code stunk with duplication, urging me to do it differently :-) Feel free to try for yourself. In particular, it becomes painful for categories with axioms or functorial construction categories where the super categories are computed automatically for you.

This makes computing all full supercategories not any slower (and probably faster) than computing all supercategories,

Yup.

or presumably all "structure supercategories" for that matter.

Possibly so. There are few structure supercategories so that's rather cheap too.

I'll answer the rest tomorrow.

Cheers,

Nicolas

[tscrim]

Replying to nthiery:

Both concepts are useful, but it's far from clear for me that we want to maintain both categories Coxeter groups / coxeter systems. Given that:

• Our Coxeter groups all come endowed with a distinguished set of generators.

• It's easier to change a structure category to a non structure category than the converse (since it's adding features).

• With the current setting, we already have both concepts: e.g. when constructing a morphism between two coxeter groups, you can choose to construct it as a group morphism or as a Coxeter group morphism.

After looking over the category, I agree with you that it is modeling a Coxeter system. However I think we should expand the documentation at the beginning of the category to emphasize this (and I'd almost say we should rename the category to reflect this).

Do they? So far, only one of the existing axioms (Unital and its additive variant) add extra structure. And the one I am thinking for the future don't add extra structure (about monoids: L,R,J-Trivial, ...).

I was thinking associative and inverse add structure (to the morphism), but they don't, they just guarantee properties about the elements (and the axioms are preserved under the morphisms). I was also thinking of things like "grading", "topogolical", and "metric" but they aren't axioms (they are/would be functorial constructions). So perhaps axiom categories could not be structure categories by default...more data is probably needed.

Actually that brings up another question, should (regressive) functorial constructions be structure categories by default? Or again do you think more data needed?

If we switch to has_additional_structure, it feels like we are not using structure as an adjective for qualifying a category anymore, but rather as a noun. So all_structure_super_categories does not really make sense. On the other hand, we could possibly name this method "structure":

sage: Rings().structure() [Category of unital magmas, Category of additive unital additive magmas]

We could actually get rid of "has_additional_structure" altogether, and instead have C.additional_structure() return C by default, with the possibility to override it to return None, or, in the future, something more meaningful than C.

However with doing things this way, how is it different than explicitly specifying the full subcategories (well, in reverse)?

[pbruin]

Replying to nthiery:

Replying to pbruin:

This actually strengthens my conviction that "structure category" is not a well-defined notion.

It's perfectly defined: C is a structure category if whenever A and B are in C and phi is a morphism between A and B for any strict super category of C, then phi is a C morphism. And it coincides with the intuition we have of it: does C define some additional structure (typically an operation) that has to be preserved by C-morphisms.

OK, but what I meant is that this notion depends on what supercategories of C have been defined, not just on C itself.

In this example, it depends on how you define Rings(): either as Rngs() & Semigroups().Unital(), in which case it is just a join of categories without new structure, _or_ as Rngs().Unital(), in which it does have extra structure (at least at first sight; you have to know that the category code magically rearranges the construction to turn Rngs().Unital() into a join of larger categories). In fact, Semigroups().Unital() (= Monoids()) is not a structure category either; it is the join of Magmas().Unital() and Semigroups().

I don't see why Rngs().Unital() should suggest it's a structure category. A.Unital() is never a structure category unless A is the category defining Unital. That is A=Magmas().

Certainly, but this relies on the the implementation choice of defining Magmas().Unital(). I admit this may be a slightly silly example, but I could imagine a different scenario where the person implementing these categories did not think anyone would need unital magmas, and hence chose to define Unital() relative to a more specific category, which in an extreme case could be Rngs(). In that case Rings() = Rngs().Unital() would have been a structure category, while being mathematically exactly the same as the actual Rings().

I don't see why this should necessarily be the case; we would just encode for each direct supercategory (of which there are usually just one or two) whether it is a full supercategory.

Well, I tried, and the code stunk with duplication, urging me to do it differently :-) Feel free to try for yourself.

I wish I had the time, but given that I don't, the best I can do is to just add my perspective as a non-developer but potential user of the category framework...

This makes computing all full supercategories not any slower (and probably faster) than computing all supercategories,

Yup.

or presumably all "structure supercategories" for that matter.

Possibly so. There are few structure supercategories so that's rather cheap too.

But to find them I assume one needs to traverse all supercategories and pick out the ones that are structure supercategories, so the time would still depend on the number of all supercategories, or am I mistaken?

[pbruin]

(cut out of previous comment since this is somewhat off topic)

Replying to nthiery:

In particular, it becomes painful for categories with axioms or functorial construction categories where the super categories are computed automatically for you.

What is a functorial construction category? From the documentation it appears that the idea is that one first defines a construction in some "abstract" sense, and only then decides in which category it takes its values, or even to construct a completely new category for this. I realise that the code doesn't have to follow mathematical definitions exactly, but this seems to be quite the opposite of the usual pattern of doing things, where defining a function, functor or natural transformation presupposes that a domain and codomain have been fixed. In general this is essential because the function (etc.) that one defines, and its properties, depend on these choices. I am somewhat worried that the Sage implementation might rely (maybe just in subtle ways) on the intuition behind the cases where this advance choice of domain and codomain doesn't matter so much.

[tscrim]

Replying to pbruin:

What is a functorial construction category? From the documentation it appears that the idea is that one first defines a construction in some "abstract" sense, and only then decides in which category it takes its values, or even to construct a completely new category for this. I realise that the code doesn't have to follow mathematical definitions exactly, but this seems to be quite the opposite of the usual pattern of doing things, where defining a function, functor or natural transformation presupposes that a domain and codomain have been fixed. In general this is essential because the function (etc.) that one defines, and its properties, depend on these choices. I am somewhat worried that the Sage implementation might rely (maybe just in subtle ways) on the intuition behind the cases where this advance choice of domain and codomain doesn't matter so much.

The examples are graded modules/algebras and WithRealizations. From those examples, I would say the categories that are actually used have a fixed (co)domain. I also think this is similar to morphisms, which also makes the assumption of a fixed (co)domain, but perhaps things are different in this case? I'm not sure I understand your concern here...

[nthiery]

Replying to tscrim:

After looking over the category, I agree with you that it is modeling a Coxeter system. However I think we should expand the documentation at the beginning of the category to emphasize this

+1, definitely (in a separate ticket of course)

(and I'd almost say we should rename the category to reflect this).

Possibly so; but then one has to do the same for Weyl groups, and WeylSystems? does not look so compelling. In any cases, things will become easier when this will have been axiomatized, so that in theory there would be a single entry point (CoxeterGroups?), with axioms Crystalographic, ...

So perhaps axiom categories could not be structure categories by default...more data is probably needed.

That felt like a reasonable default which is why I implemented this way; especially since anyway the only case where there can be additional structure for the axiom category is within the category defining the axiom.

Actually that brings up another question, should (regressive) functorial constructions be structure categories by default? Or again do you think more data needed?

At this point I'd be uncomfortable with it, since e.g. Graded is one such construction. So I guess it's best done construction by construction until we have more data. But it may well be that things should be as for axiom categories: except within the category defining the construction, there is no additional structure.

In fact, maybe the correct default would be to have, A.B().has_additional_structure() return True if and only if A is the category defining the axiom/regressive construction B.

We could actually get rid of "has_additional_structure" altogether, and instead have C.additional_structure() return C by default, with the possibility to override it to return None, or, in the future, something more meaningful than C.

However with doing things this way, how is it different than explicitly specifying the full subcategories (well, in reverse)?

Well, first it's more concise (just return None or self) and involves less duplication.

Also, it gives more information to the system: there are cases where a category defines no additional structure even though it's not a full subcategory of any of its direct super categories. Think of some full subcategory of Magmas() & AdditiveMagmas(). Granted, you could have full_super_categories return a join, but this would deviate from everywhere else (a category never has a join as super category), and thus probably be a source of problems.

Cheers,

Nicolas

[nthiery]

Hi Peter,

Sorry, still running behind. I'll just answer some easy points now.

Replying to pbruin:

I wish I had the time, but given that I don't, the best I can do is to just add my perspective as a non-developer but potential user of the category framework...

I know, and appreciate this. I guess I am just expressing the frustration when some things appear clearly after having manipulated the code for a while, yet are hard to convey convincingly.

But to find them I assume one needs to traverse all supercategories and pick out the ones that are structure supercategories, so the time would still depend on the number of all supercategories, or am I mistaken?

Yes and no: this is obtained by taking the union of the structures of the direct super categories, and cached. So yes, this can trigger a calculation for all the super categories if such information has never been computed before higher above in the category hierarchy. But otherwise, the cost is just that of the union, and that's essentially linear in the number of structure super categories.

Cheers,

Nicolas

[nthiery]

Dear Peter,

Replying to pbruin:

It seems to me that the first thing one has to do when defining a category (and maybe the only essential thing!) should be to decide how to encode its mathematical meaning. The distinction between adding a new axiom to the objects (thereby creating a full subcategory) and adding a new type of structure (thereby creating a relationship that I was thinking of as "category refinement" in earlier discussions) is really fundamental in my opinion.

I agree that clarifying what additional structure, if any, a category defines can be a fundamental guideline for the design. Now, from what I have seen in practice, new category writers usually start with plain structure categories, and they do intuitively the right thing (which typically shows up in the documentation: a XXX is a YYY endowed with an operation zzz).

Worst case, if XXX does not actually define new structure, the default behavior remains safe. They just won't get some feature that they most likely don't need anyway. Remember that the doc of "is_full_subcategory" specifies:

            A positive answer is guaranteed to be mathematically
            correct. A negative answer may mean that Sage has not been
            taught enough information to derive this information. See
            :meth:`full_super_categories` for a discussion.

Things are also safe when implementing an existing axiom or construction in a category where it was not yet there.

The above guideline becomes important when implementing new axioms, new constructions, or deciding which it should be; but there we can assume that the developer has gained enough experience.

Actually, that made me have a thought. How about instead of is_structure_category we have has_additional_structure, and then we could extend this to additional_structure (on a followup ticket).

On the contrary, I think it there is an essential distinction between just adding an axiom to the objects (hence creating a full subcategory) and adding "extra structure".

My point is that the two concepts of axioms and of categories adding structure are rather orthogonal.

Axioms are relevant when a bunch of categories have something to say about that axiom. An axiom by itself may or may not add structure. And there are non structure categories that need not be axioms.

Whether a given category is a structure category or not is the matter of a single method, and it's not worth the complexity of duplicating the category class hierarchy just for this.

(By the way, "over a base ring" is actually something that I am thinking of as another example of "extra structure".)

Here, it's really the category Modules that adds the structure. The class "Category_over_base_ring" is just a technical gadget to handle the base ring parameter that the categories over base rings takes. E.g. Algebras.FiniteDimensional is a category over a base ring which does not add structure, whereas Modules does.

Also: there is room for improvement in functorial constructions: in some cases, we could automatically deduce that the category is a structure category.

I am wondering how you could possibly detect such a thing. In the case of the Unital() structure (correct me if this is somehow an exception), how do you know that this does not just mean the existence of a unit element in the objects, but also the requirement that morphisms preserve this element? This seems to me precisely the type of information that has to be specified by the person implementing the Unital() structure.

Yes, this need to be specified explicitly by the person *defining* a new axiom. But if it's just about implementing an existing axiom for some category where it was not yet there, then the answer is clear: there is no new structure.

As we discussed with Travis, I believe something similar should hold for functorial constructions categories, at least in the covariant case, but I need to think more about it.

Cheers,

Nicolas

[nthiery]

Replying to pbruin:

OK, but what I meant is that this notion depends on what supercategories of C have been defined, not just on C itself.

Certainly, but this relies on the the implementation choice of defining Magmas().Unital(). I admit this may be a slightly silly example, but I could imagine a different scenario where the person implementing these categories did not think anyone would need unital magmas, and hence chose to define Unital() relative to a more specific category, which in an extreme case could be Rngs(). In that case Rings() = Rngs().Unital() would have been a structure category, while being mathematically exactly the same as the actual Rings().

Fair enough: this is indeed not something purely about the abstract (lattice of) mathematical categories, but about whatever subset has been actually modeled in Sage. It's not so bad though, since this does not depend on how the categories have been implemented (e.g. through axioms or not); just on which categories are implemented or not.

In the above scenario, Rings would at first be a structure category; and then, when the definition of the Unital axioms gets lifted up to some higher category like Magmas, Sage would learn that the structure actually comes from some higher category. That's fine given the specs about negative answers for "X.is_full_super_category(Y)".

In general, when adding new categories and "moving structure up", one indeed needs to update the "additional structure" methods of the lower categories accordingly. Though if one forgets to do it, it should just cause a lack of new feature, rather than bugs. So we are on the safe side.

Cheers,

Nicolas

[git]

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

​1e4418f	Merge branch 'develop' into categories/full-subcategories-16340
​708cc41	Merge branch 'public/categories/full_subcategories-16340' of trac.sagemath.org:sage into categories/full-subcategories-16340
​29a6c67	16340: reverted change to CoxeterGroups.is_structure_category() + explanations in the doc
​60aa128	16340: fixed typos

[nthiery]

Hi,

I just fixed some small typos, and reverted the change to CoxeterGroups.is_structure_category() as we discussed.

Time for a checkpoint on the current status.

Permutation groups

Looking back at Travis change, I would want to also revert the change to PermutationGroups(), to let it be a structure category. Indeed, permutation groups come with a distinguished action, and Wikipedia states that this action should be preserved by isomorphisms:

​http://en.wikipedia.org/wiki/Permutation_group#Permutation_isomorphic_groups

Do you agree?

additional_structure w.r.t. full_super_categories

As discussed above, I believe that having the developer implement additional_structure rather than full_super_categories is more concise and involves less duplication. And also gives more information (which category define additional structure) which could be further refined (e.g. "Magmas()" defines "*"), if deemed useful in later iterations.

Is this acceptable for everyone?

additional_structure w.r.t is_structure_category

Do we have a consensus that the "additional_structure / structure" language is better than "is_structure_category / all_structure_super_categories"? And that for now we can specify that C.additional_structure() shall return C or None?

If yes, I can implement this change shortly.

Default for axioms

Currently, axiom categories define no additional structure by default. To be 100% foolproof even when defining new axioms, one could change that so an axiom category C().A() would by default define additional structure if and only if C is the category defining the axiom A.

It would be a relatively small change. The cost is that all but two of our current axioms would need to have an "additional_structure" method. I also need to check whether it's easy to detect if C is the category defining A.

Something similar could probably be done for functorial constructions, but we need more data and thinking to do it right and the current default is safe in the mean time.

Anything else?

Cheers,

Nicolas

[nthiery]

Replying to pbruin:

What is a functorial construction category?

Coming back to this side discussion ...

That's a good question. The documentation is certainly terse and could take some love. I haven't spent on it the two weeks of hard work I put on axioms!

From the documentation it appears that the idea is that one first defines a construction in some "abstract" sense, and only then decides in which category it takes its values, or even to construct a completely new category for this. I realise that the code doesn't have to follow mathematical definitions exactly, but this seems to be quite the opposite of the usual pattern of doing things, where defining a function, functor or natural transformation presupposes that a domain and codomain have been fixed. In general this is essential because the function (etc.) that one defines, and its properties, depend on these choices. I am somewhat worried that the Sage implementation might rely (maybe just in subtle ways) on the intuition behind the cases where this advance choice of domain and codomain doesn't matter so much.

Maybe the doc is misleading. But the starting point is really the functorial construction, that is the collection (F_C)_C of related functors (e.g. the collection of algebra functors: `groups->group algebras, monoids->monoid algebras, finite groups->finite groups algebras`, ...).

Then, the functorial construction category C.F() is meant to model the codomain of the functor F_C, which is well defined.

Of course the model might be incomplete. Categories in Sage are an approximation of the ideal mathematical categories; not all of them nor features thereof are implemented in Sage.

One possible source of confusion is that the functors F_C might not actually be modeled as a standalone objects in Sage. But that's just because we did not really need them at this point. In our example, we just need it was sufficient for now to have the construction implemented as G -> G.algebra(QQ). In general, at this point, the central feature really resides in the categories.

Another source of confusion is that some of the uses of the mechanism for "functorial construction categories" go beyond functorial constructions. E.g. for subobjects, quotients, ... there is not really a collection of functors behind the scene. Still the mechanism remains valid. It would be nice to come up with a better name and definition that would cover all cases. That's now #16991.

Cheers,

Nicolas

[tscrim]

I agree with reverting PermtutationGroup along with a warning or note about (iso)morphisms (although like Coxeter groups, it is not currently enforced AFAIK).

I don't have a strong opinion on what the method are named and the proposed interface is fine with me.

I'm okay with the default for axioms not being structure categories. However I'd rather have fuctorial construction categories being structure categories by default (I believe currently we only have two, graded and with-realizations, but the two I'd like to add, topological and metric, have additional structure).

[pbruin]

Replying to nthiery:

Time for a checkpoint on the current status.

Permutation groups

Looking back at Travis change, I would want to also revert the change to PermutationGroups(), to let it be a structure category. Indeed, permutation groups come with a distinguished action, and Wikipedia states that this action should be preserved by isomorphisms:

​http://en.wikipedia.org/wiki/Permutation_group#Permutation_isomorphic_groups

Do you agree?

Yes, the set that is acted upon does seem to qualify as extra structure.

additional_structure w.r.t. full_super_categories

As discussed above, I believe that having the developer implement additional_structure rather than full_super_categories is more concise and involves less duplication. And also gives more information (which category define additional structure) which could be further refined (e.g. "Magmas()" defines "*"), if deemed useful in later iterations.

Is this acceptable for everyone?

That sounds good to me.

additional_structure w.r.t is_structure_category

Do we have a consensus that the "additional_structure / structure" language is better than "is_structure_category / all_structure_super_categories"? And that for now we can specify that C.additional_structure() shall return C or None?

If yes, I can implement this change shortly.

I am in favour of this change.

Default for axioms

Currently, axiom categories define no additional structure by default. To be 100% foolproof even when defining new axioms, one could change that so an axiom category C().A() would by default define additional structure if and only if C is the category defining the axiom A.

I am not in favour of this, because it would conflate the notions of "axiom" and "extra structure" (which from my perspective are quite different) even more.

[pbruin]

Replying to tscrim:

I'm okay with the default for axioms not being structure categories. However I'd rather have fuctorial construction categories being structure categories by default (I believe currently we only have two, graded and with-realizations, but the two I'd like to add, topological and metric, have additional structure).

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.

[tscrim]

Replying to pbruin:

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).

[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

[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]

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

[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

[git]

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

​eb621c7

Fixing some typos

[SimonKing]

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.

[SimonKing]

Replying to pbruin:

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.

[SimonKing]

Replying to tscrim:

Replying to pbruin:

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...

[SimonKing]

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.

[nthiery]

Yeah! Thanks everyone for the review!

[ncohen]

O_o

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

Nathann

[SimonKing]

Replying to ncohen:

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.

[ncohen]

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

[SimonKing]

Replying to ncohen:

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?

What do you think about it,

[ncohen]

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]

Replying to ncohen:

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]

Replying to ncohen:

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