#16340 closed enhancement (fixed)
Infrastructure for modelling full subcategories
Reported by:  nthiery  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  categories  Keywords:  full subcategories, homset 
Cc:  sagecombinat, hivert, SimonKing, darij, nbruin, pbruin, vbraun  Merged in:  
Authors:  Nicolas M. Thiéry  Reviewers:  Darij Grinberg, Travis Scrimshaw, Simon King 
Report Upstream:  N/A  Work issues:  
Branch:  eb621c7 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
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 Amorphism is a Bmorphism (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?
Change History (71)
comment:1 Changed 9 years ago by
comment:2 followup: 5 Changed 9 years ago by
Ideally, for every piece of algebraic structure there should be both a full and a fully structureaware 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 moduleswithbasis with basispreserving 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!
comment:3 followup: 6 Changed 9 years ago by
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.
comment:4 Changed 9 years ago by
Branch:  → u/nthiery/categories/fullsubcategories16340 

comment:5 Changed 9 years ago by
Commit:  → 2f2d09bec3a2e77021670d996abe2dd399fc63ec 

Replying to darij:
Ideally, for every piece of algebraic structure there should be both a full and a fully structureaware 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 moduleswithbasis with basispreserving 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/overabaseringcategory15801' of trac.sagemath.org:sage into public/categories/overabaseringcategory15801

281f539  Added back in import statement as per comment.

96c631f  Merge branch 'develop' into categories/axioms10963

b1a2aed  Trac 10963: two typo fixes to let the pdf documentation compile

c16f18b  Merge branch 'public/ticket/10963docdistributive' of trac.sagemath.org:sage into categories/axioms10963

dcb11d8  Merge branch 'categories/axioms10963' into categories/over_a_base_category15801

15658bd  Trac 15801: fixed merge with #12630

2f2d09b  16340: infrastructure for modelling full subcategories

comment:6 Changed 9 years ago by
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?
comment:7 Changed 9 years ago by
Status:  new → needs_review 

Summary:  Model full subcategories → Infrastructure for modelling full subcategories 
comment:8 followup: 9 Changed 9 years ago by
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()
?)
comment:9 followup: 10 Changed 9 years ago by
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.
comment:10 followup: 11 Changed 9 years ago by
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 inoperator.contains
,operator.mul
,operator.and
, or a parent/element method such asan_element
), andmethod
is an abstract parent/element method that has to be implemented forop
(i.e.,__contains__
,_mul_
, or_an_element
)
comment:11 Changed 9 years ago by
Replying to SimonKing:
Or, even more informative: Return a pair
(op, method)
, such that
op
is the operator (either as inoperator.contains
,operator.mul
,operator.and
, or a parent/element method such asan_element
), andmethod
is an abstract parent/element method that has to be implemented forop
(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.
comment:12 Changed 9 years ago by
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".
comment:13 Changed 9 years ago by
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
comment:14 Changed 9 years ago by
Commit:  2f2d09bec3a2e77021670d996abe2dd399fc63ec → c06e2ef9e1bbff273cbc766f8a08289aba0d5605 

Branch pushed to git repo; I updated commit sha1. New commits:
c06e2ef  16340: added full_super_categories method, a test, and some doc

comment:15 Changed 9 years ago by
Status:  needs_review → needs_work 

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/sitepackages/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: *** [dochtml] Error 1
comment:16 Changed 9 years ago by
Commit:  c06e2ef9e1bbff273cbc766f8a08289aba0d5605 → 2b0164b43255201a19ef02f2a31446698c0cb0dc 

Branch pushed to git repo; I updated commit sha1. New commits:
2b0164b  16340: trivial ReST fix

comment:17 Changed 9 years ago by
Commit:  2b0164b43255201a19ef02f2a31446698c0cb0dc → b6342d163e834c2295478186dcfed1df52a487d9 

Branch pushed to git repo; I updated commit sha1. New commits:
b6342d1  Merge branch 'develop' into categories/fullsubcategories16340

comment:18 Changed 9 years ago by
Status:  needs_work → needs_review 

Work issues:  → find good names 
comment:19 Changed 9 years ago by
Status:  needs_review → needs_work 

There are some failing doctests, see patchbot report.
comment:20 Changed 9 years ago by
Branch:  u/nthiery/categories/fullsubcategories16340 → public/categories/full_subcategories16340 

Commit:  b6342d163e834c2295478186dcfed1df52a487d9 → edb29e60b336e99834a0dc551597e39b42a89540 
Status:  needs_work → needs_review 
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/fullsubcategories16340' of trac.sagemath.org:sage into public/categories/full_subcategories16340

edb29e6  Fixed trivial doctest failures.

comment:21 Changed 9 years ago by
Milestone:  sage6.3 → sage6.4 

comment:22 followup: 23 Changed 8 years ago by
Commit:  edb29e60b336e99834a0dc551597e39b42a89540 → 8bc456c9e67f2dbcbb1255f104d47a38ebacfa5d 

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/fullsubcategories16340

99a8eb1  Merge branch 'public/categories/full_subcategories16340' of trac.sagemath.org:sage into categories/fullsubcategories16340

8bc456c  Merge branch 'master=6.3' into categories/fullsubcategories16340

comment:23 Changed 8 years ago by
Simon, could you review this ticket since we need it for other applications? Thanks!
comment:24 Changed 8 years ago by
Commit:  8bc456c9e67f2dbcbb1255f104d47a38ebacfa5d → 737a8f0c80a80040cb3c0308b1d2063f456662d0 

Branch pushed to git repo; I updated commit sha1. New commits:
737a8f0  16340: improved warnings about the current limitation of the model

comment:25 Changed 8 years ago by
Description:  modified (diff) 

comment:26 Changed 8 years ago by
I put here for the record a summary of a private discussion by email.
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.
comment:27 Changed 8 years ago by
Commit:  737a8f0c80a80040cb3c0308b1d2063f456662d0 → 282ac4e1c6959c363a78331989f37e160a96121f 

Branch pushed to git repo; I updated commit sha1. New commits:
282ac4e  16340: fixed typos reported by Darij

comment:28 Changed 8 years ago by
Commit:  282ac4e1c6959c363a78331989f37e160a96121f → d4c7a88563a397291b6cd5ddadb8f574cc1eedb5 

comment:29 followups: 30 33 Changed 8 years ago by
Reviewers:  → Darij Grinberg, Travis Scrimshaw 

Work issues:  find good names 
I made some other categories into nonstructure 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 doublecheck 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.
comment:30 followups: 31 60 Changed 8 years ago by
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.
comment:31 followup: 32 Changed 8 years ago by
Description:  modified (diff) 

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).
comment:32 followup: 34 Changed 8 years ago by
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 beFalse
or do we allowTrue
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 havehas_additional_structure
, and then we could extend this toadditional_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
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.CategoryWithStructure
: proposed new class. Specifies an additional structure on objects that must be preserved by morphisms, and defines a usually nonfull 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.
comment:33 followup: 35 Changed 8 years ago by
Replying to tscrim:
I made some other categories into nonstructure 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 doublecheck to make sure I didn't miss any others and I'd appreciate if someone else could do the same.
Thanks!
Cheers,
Nicolas
comment:34 followup: 36 Changed 8 years ago by
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 beFalse
or do we allowTrue
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 havehas_additional_structure
, and then we could extend this toadditional_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
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.CategoryWithStructure
: proposed new class. Specifies an additional structure on objects that must be preserved by morphisms, and defines a usually nonfull 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 ofRngs
) 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
comment:35 followup: 37 Changed 8 years ago by
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 doublecheck to make sure I didn't miss any others and I'd appreciate if someone else could do the same.
Thanks!
Thanks for doublechecking my doublecheck.
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)?
comment:36 followups: 38 45 Changed 8 years ago by
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 beFalse
or do we allowTrue
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 havehas_additional_structure
, and then we could extend this toadditional_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
CategoryWithAxiom
: like the existing class, but morerestrictive. Specifies an additional axiom to be satisfied by the objects, and defines the full subcategory objects satisfying this axiom. For example, commutativity for groups.
CategoryWithStructure
: proposed new class. Specifies anadditional structure on objects that must be preserved by morphisms, and defines a usually nonfull 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 ofRngs
) 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 notRngs().Unital()
: all the structure is defined in the super categoriesRngs()
andSemigroups().Unital()
.
This actually strengthens my conviction that "structure category" is not a welldefined 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.
comment:37 followup: 39 Changed 8 years ago by
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,JTrivial, ...).
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
comment:38 followups: 40 41 Changed 8 years ago by
Replying to pbruin:
This actually strengthens my conviction that "structure category" is not a welldefined 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 asRngs() & Semigroups().Unital()
, in which case it is just a join of categories without new structure, _or_ asRngs().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 turnRngs().Unital()
into a join of larger categories). In fact,Semigroups().Unital()
(=Monoids()
) is not a structure category either; it is the join ofMagmas().Unital()
andSemigroups()
.
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
comment:39 followup: 43 Changed 8 years ago by
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,JTrivial, ...).
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. Soall_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()
returnC
by default, with the possibility to override it to returnNone
, or, in the future, something more meaningful thanC
.
However with doing things this way, how is it different than explicitly specifying the full subcategories (well, in reverse)?
comment:40 followups: 44 46 Changed 8 years ago by
Replying to nthiery:
Replying to pbruin:
This actually strengthens my conviction that "structure category" is not a welldefined 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 aC
morphism. And it coincides with the intuition we have of it: doesC
define some additional structure (typically an operation) that has to be preserved byC
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 asRngs() & Semigroups().Unital()
, in which case it is just a join of categories without new structure, _or_ asRngs().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 turnRngs().Unital()
into a join of larger categories). In fact,Semigroups().Unital()
(=Monoids()
) is not a structure category either; it is the join ofMagmas().Unital()
andSemigroups()
.I don't see why
Rngs().Unital()
should suggest it's a structure category.A.Unital()
is never a structure category unlessA
is the category definingUnital
. That isA=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 nondeveloper 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?
comment:41 followups: 42 49 Changed 8 years ago by
(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.
comment:42 Changed 8 years ago by
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...
comment:43 Changed 8 years ago by
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()
returnC
by default, with the possibility to override it to returnNone
, or, in the future, something more meaningful thanC
.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
comment:44 Changed 8 years ago by
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 nondeveloper 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
comment:45 Changed 8 years ago by
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 havehas_additional_structure
, and then we could extend this toadditional_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 theUnital()
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
comment:46 Changed 8 years ago by
Replying to pbruin:
OK, but what I meant is that this notion depends on what supercategories of
C
have been defined, not just onC
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 defineUnital()
relative to a more specific category, which in an extreme case could beRngs()
. In that caseRings() = Rngs().Unital()
would have been a structure category, while being mathematically exactly the same as the actualRings()
.
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
comment:47 Changed 8 years ago by
Commit:  d4c7a88563a397291b6cd5ddadb8f574cc1eedb5 → 60aa128d42ee140fb268423a924fd0e80aab7329 

Branch pushed to git repo; I updated commit sha1. New commits:
1e4418f  Merge branch 'develop' into categories/fullsubcategories16340

708cc41  Merge branch 'public/categories/full_subcategories16340' of trac.sagemath.org:sage into categories/fullsubcategories16340

29a6c67  16340: reverted change to CoxeterGroups.is_structure_category() + explanations in the doc

60aa128  16340: fixed typos

comment:48 followup: 51 Changed 8 years ago by
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
comment:49 Changed 8 years ago by
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
comment:50 followup: 52 Changed 8 years ago by
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 withrealizations, but the two I'd like to add, topological and metric, have additional structure).
comment:51 Changed 8 years ago by
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 thanfull_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 returnC
orNone
?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 ifC
is the category defining the axiomA
.
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.
comment:52 followup: 53 Changed 8 years ago by
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 withrealizations, 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.
comment:53 followup: 61 Changed 8 years ago by
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 0th 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).
comment:54 Changed 8 years ago by
Commit:  60aa128d42ee140fb268423a924fd0e80aab7329 → 950b039af76007dafaf4302c2cfcadf24dd1bb9a 

Branch pushed to git repo; I updated commit sha1. New commits:
950b039  16340: Merge branch 'develop = 6.4 beta4' into categories/fullsubcategories16340

comment:55 Changed 8 years ago by
Commit:  950b039af76007dafaf4302c2cfcadf24dd1bb9a → b14ca6ce79a846103a8afd325b926663a8e3f12a 

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

comment:56 Changed 8 years ago by
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
comment:57 Changed 8 years ago by
Commit:  b14ca6ce79a846103a8afd325b926663a8e3f12a → 43b25d4a399641154d18b9d4c0ba80cf7ac3f2d9 

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

comment:58 Changed 8 years ago by
Commit:  43b25d4a399641154d18b9d4c0ba80cf7ac3f2d9 → eb621c7beacb797f43fd41c9156edc453e80a902 

Branch pushed to git repo; I updated commit sha1. New commits:
eb621c7  Fixing some typos

comment:59 Changed 8 years ago by
Reviewers:  Darij Grinberg, Travis Scrimshaw → Darij Grinberg, Travis Scrimshaw, Simon King 

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 rerun certain tests with this branch, but it is close to a positive review.
comment:60 Changed 8 years ago by
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.
comment:61 Changed 8 years ago by
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 ofC
has a natural way to construct this data that preserves the morphisms. For graded, make everything be in the 0th 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 wheredeg(x) = 0
for allx
inA
, 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...
comment:62 Changed 8 years ago by
Status:  needs_review → positive_review 

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.
comment:63 Changed 8 years ago by
Branch:  public/categories/full_subcategories16340 → eb621c7beacb797f43fd41c9156edc453e80a902 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:64 Changed 8 years ago by
Commit:  eb621c7beacb797f43fd41c9156edc453e80a902 

Yeah! Thanks everyone for the review!
comment:65 followups: 66 70 Changed 8 years ago by
O_o
Wasn't there a way to make all these classes inherit the additional_structure
> return None
function ?..
Nathann
comment:66 followup: 67 Changed 8 years ago by
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 falsepositive answer by default), then you need to do something special for all cases that are special.
comment:67 followup: 68 Changed 8 years ago by
Yo !
Probably not, if you talk about the case that
return self
is the default for categories that are notCategoryWithAxiom
.If you have a default (which here is chosen so that the test for a full subcategory will not give a falsepositive 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
comment:68 Changed 8 years ago by
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 nondefault behaviour could be requested more lightweight.
Nicolas, what do you think?
What do you think about it,
comment:69 followup: 71 Changed 8 years ago by
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 codespecific description.
But of course I have absolutely no idea of what I am talking about.
Nathann
comment:70 Changed 8 years ago by
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
comment:71 Changed 8 years ago by
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 codespecific 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
Suggestions anyone before I start implementing this?
Cheers,