#16340: Infrastructure for modelling full subcategories
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: categories | Resolution:
Keywords: full | Merged in:
subcategories, homset | Reviewers: Darij Grinberg,
Authors: Nicolas M. Thiéry | Travis Scrimshaw
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/categories/full_subcategories-16340|
d4c7a88563a397291b6cd5ddadb8f574cc1eedb5
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Old description:
> 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?
New description:
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?
--
Comment (by tscrim):
Replying to [comment:30 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).
--
Ticket URL: <http://trac.sagemath.org/ticket/16340#comment:31>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
