#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:
Authors: Nicolas M. Thiéry | Work issues: find good names
Report Upstream: N/A | Commit:
Branch: | 737a8f0c80a80040cb3c0308b1d2063f456662d0
public/categories/full_subcategories-16340| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Description changed by nthiery:
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"}
> }}}
>
> == Questions ==
>
> - Find good names for all the methods above
>
> - How to handle the case where the extra structure is forced by the
> context, and automatically preserved by morphisms? E.g. the trivial
> Euclidean structure on fields?
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?
--
--
Ticket URL: <http://trac.sagemath.org/ticket/16340#comment:25>
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.
