#10667: Morphisms and Objects of Categories
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: nthiery
Type: enhancement | Status: new
Priority: major | Milestone:
Component: categories | Keywords: objects morphisms containment
Author: Simon King | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------+------------------------------------------------
Changes (by newvalueoldvalue):
* author: => Simon King
Comment:
Depends on #10496, #10659, #8611, #10467
I wont to get the patch finally off my plate. So, here it is, although it
isn't finished yet.
My patch provides the following:
{{{
sage: C = Rings()
sage: P.<x,y> = QQ[]
sage: f = P.hom(reversed(P.gens()))
sage: C.has_morphism(f)
True
sage: C.morphisms()
Class of morphisms in category of rings
sage: f in C.morphisms()
True
# Currently, a category is acknowledged as "small"
# iff it is a sub-category of FiniteEnumeratedSets()
sage: FiniteFields().morphisms()
Set of morphisms in category of finite fields
sage: f in FiniteFields().morphisms()
False
sage: P in C
True
sage: C.objects()
Class of objects in category of rings
sage: P in C.objects()
True
sage: FiniteFields().objects()
Set of objects in category of finite fields
}}}
Note that I interprete `Objects()` (the top-category in Sage) as the
"category of all classes", although this definition probably is not water-
proof:
{{{
sage: C.objects().category()
Category of objects
sage: FiniteFields().objects().category()
Category of sets
}}}
Some categories have a custom containment test, e.g., the category of
fields. The containment test of `C.objects()` automatically tests whether
`C` has a custom containment, and uses it if it is the case:
{{{
sage: PolynomialRing(QQ,[]).category()
Category of commutative rings
sage: PolynomialRing(QQ,[]) in Fields()
True
sage: PolynomialRing(QQ,[]) in Fields().objects()
True
}}}
The documentation for the new containers for objects and morphisms are
added to the Sage reference manual -- please have a look.
'''__`SageObject` versus `CategoryObject`__'''
`SageObject` and `CategoryObject` were almost identical. In particular,
`SageObject` provided a method `category()`, that by default returned the
"category of objects". In addition, the specifition says that `X` is an
object of `X.category()`, i.e., `X in X.category()`.
But that approach yields to quite unnatural constructions. For example,
`1.category()` used to be the "category of elements of Integer Ring",
whatever that means. Worse, one used to have
{{{
# Unpatched behaviour: Bug
sage: ZZ.hom([1]) in Rings().hom_category()
True
}}}
In other words, a ''ring homomorphism'' is considered a ''homset'' of the
category of rings - of course, it should just be an ''element'' of a
homset:
{{{
# With the patch:
sage: ZZ.hom([1]) in Rings().hom_category()
False
sage: ZZ.hom([1]) in ZZ.Hom(ZZ)
True
sage: ZZ.hom([1]) in Rings().morphisms()
True
}}}
Fixing that bug required to re-structure `SageObject` and
`CategoryObject`:
* I removed `category()` and `_test_category()` from `SageObject` and
moved it to `CategoryObject` (which directly inherits from `SageObject`
anyway).
* I made `Element` and `Map` inherit from `SageObject`, not from
`CategoryObject`, and removed the custom `category()` for `Element`. Of
course, `Parent` still inherits from `CategoryObject`.
Note that by this change, it is now impossible to define nonsense such as
`Hom(2,3)` (2 and 3 used to be objects in a category, so, there was a hom-
set!).
'''__Hom-categories__'''
'''Compare #10668''': This part of my patch is not finished, yet. I
suppose that eventually this ticket here will depend on #10668.
Just for now, I implemented what I described in my previous post.
Otherwise, many tests from the new test suites described below would fail.
'''__Test Suites__'''
The test suites of categories have been extended to test against the
specification of the new features. In particular, the containers for
morphisms and objects provide a test suite. The test suites for
`C.morphisms()` and `C.objects()` and `C.hom_category()` are added to the
test suite of `C`.
The patch adds a method `an_object()` to categories, that is used for
additional tests. The default is to return `example()`, but this is not
provided in all cases. The purpose of `an_object()` is narrower than that
of `example()`, which is supposed to provide a concise instructive (but
not necessarily very efficient) implementation. In contrast, `an_object()`
may return an object of a subcategory, if nothing else is available. The
test suite of `C.an_object()` becomes part of the test suite of `C`.
Similarly, I introduce a method `a_morphism`. By default, it takes the
output of `an_object()`, tries to create an automorphism by reverting the
list of generators, and if that fails then it returns the identity
automorphism. The latter sounds trivial, but actually I found several
cases where the identity automorphism was provided with the wrong
category. This led to the following bug fixes:
* In `sage.categories.homset.Hom`, there was an assymmetry between the
categories of the domain and the codomain. I suggest to choose the
''meet'' of both categories. However, note that there was a comment like
this:
{{{
To avoid creating superfluous categories, homsets are in the
homset category of the lowest category which currently says
something specific about its homsets.
}}}
which meant that the endomorphisms of the rational field used to belong
to the "Category of hom sets in Category of rings". I didn't observe any
problems changing it into the "Category of hom sets in Category of
quotient fields".
* Without the patch:
{{{
sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: G = MatrixGroup([MS([1,1,0,1])])
sage: H = MatrixGroup([MS([1,0,1,1])])
sage: phi = G.hom(H.gens())
sage: phi.category_for()
Category of groups
sage: H.category()
Category of finite groups
sage: G.category()
Category of finite groups
}}}
Hence, the morphism belongs to a category that is too broad. With the
patch:
{{{
sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: G = MatrixGroup([MS([1,1,0,1])])
sage: H = MatrixGroup([MS([1,0,1,1])])
sage: phi = G.hom(H.gens())
sage: phi.category_for()
Category of finite groups
}}}
In several cases I have not been able to find any proper use case in
Sage for a given category. In these cases, I have not been able to provide
`an_object()`, so that in these cases I have to skip some tests from the
test suites:
* `JoinCategory` (I guess it is impossible to construct a generic object
of the join of two arbitrary categories)
* `AbstractCategory` (Do I understand correctly that the abstract
category for the category of `ZZ`-modules would be the catogory of
modules? I.e., one abstracts the base ring away?)
* `Schemes`:
{{{
# Bug, not fixed in the patch
sage: Spec(QQ).category()
Category of sets
}}}
* `UniqueFactorizationDomains`
{{{
# Bug, not fixed in the patch
sage: ZZ in UniqueFactorizationDomains()
False
}}}
* `AlgebraModules`:
{{{
sage: QQ['x'] in Algebras(QQ)
True
# Bug?
sage: QQ['x']^3 in AlgebraModules(QQ['x'])
False
}}}
* `GSets` (Is there any G-set in Sage that knows that it is a G-set?)
* `DualObjectsCategory`
* `Sets().Subquotients()`
* `FiniteDimensional...`: Most categories whose name starts with
`FiniteDimensional` are not in use.
* `PartiallyOrderedMonoids`
* `MonoidAlgebras`
* `TensorProductsCategory`
* I added a minimal implementation of pointed sets:
{{{
sage: from sage.categories.examples.pointed_sets import PointedSet
sage: S = PointedSet([1,2,3],2)
sage: S
{1, 2, 3} -> 2
sage: S is loads(dumps(S))
True
sage: S == PointedSet([1,2,3],3)
False
}}}
* I fixed the category of partially ordered sets.
Without patch:
{{{
sage: from sage.combinat.posets.posets import Poset
sage: elms = [1,2,3,4,5,6,7]
sage: rels = [[1,2],[3,4],[4,5],[2,5]]
sage: Poset((elms, rels), cover_relations = True).category()
Category of sets
}}}
With the patch, we obtain `Category of partially ordered sets`.
* The category of matrix algebras has not been used. I added the obvious
example:
{{{
sage: MatrixSpace(QQ,2).category()
Category of matrix algebras over Rational Field
}}}
which used to be the category of algebras (not: matrix algebras).
'''__Groupoids__'''
Groupoids are considered as a category with a single object. However, this
object did not exist. The patch provides it, modeled as an empty set:
{{{
sage: G = SymmetricGroup(5)
sage: C = Groupoid(G)
sage: O = C.an_object(); O
Unique object of Groupoid with underlying set SymmetricGroup(5)
sage: len(O)
0
sage: O.an_element()
Traceback (most recent call last):
...
EmptySetError:
}}}
The elements of `G` correspond to morphisms of its groupoid. I suggest to
actually consider them as morphisms (which is stronger than saying they
''correspond to'' morphisms):
{{{
sage: G.an_element() in C.morphisms()
True
}}}
Note that this point of view is needed in order to have a functorial
approach towards actions, namely: If we want to view a group action of `G`
on a set `S` as a functor from the groupoid of `G` to the category
containing `S` as an object, then
1. we need that functors can map morphisms (see #8807), and
2. we need that group elements are considered as morphisms.
Actually, that was the starting point for my work on this ticket.
On the other hand, I do think that considering `G` as a homset of
`Groupoid(G)` is not a very clean solution. But I believe this could be
addressed on a different ticket, as this one is already too long.
'''__Need for Speed__'''
Of course, testing containment in a category `C` or in `C.objects()` or in
`C.morphisms()` should be as fast as possible. I did the following:
* I added a shortpath to `C.__contains__` and `C.objects().__contains__`
for the common case that the category of the argument is `C`.
* `C.objects()` and `C.morphisms()` are cached methods. By #8611, the
overhead is now pretty small anyway.
* Containment of an object `O` in a category `C` relies on testing
whether `O.category()` is a sub-category of `C`. This is cached, by #8611.
In addition, I remove the overhead entirely, by directly accessing the
cache.
* The containers for objects and morphisms are implemented in Cython. The
default containment test is copied from the category, in order to reduce
the overhead of calling a Python function. Therefore, `F in O` (where `O =
C.objects()`) is sometimes even a little quicker than `F in C`:
{{{
sage: F = GF(5)
sage: C = Rings()
sage: O = C.objects()
sage: F in O
True
sage: timeit('F in O',number=100000)
100000 loops, best of 3: 5.2 µs per loop
sage: timeit('F in C',number=100000)
100000 loops, best of 3: 5.38 µs per loop
}}}
Here are some timings. Their purpose is to show that `X in C` did not slow
down (in fact, there is a speed-up in one special case), and that `X in
C.objects()` has almost no overhead compared to `X in C`.
Setting:
{{{
sage: G = SymmetricGroup(5)
sage: P.<x,y> = QQ[]
sage: F = PolynomialRing(QQ,[])
sage: C1 = Rings()
sage: C2 = G.category()
sage: C3 = Fields()
}}}
Sanity tests:
{{{
# test that X in C.objects() is the same as X in C
# For C1:
sage: P in C1
True
sage: P in C1.objects()
True
sage: G in C1
False
sage: G in C1.objects()
False
sage: F in C1
True
sage: F in C1.objects()
True
# For C2, which is a join (that's a special case):
sage: P in C2
False
sage: P in C2.objects()
False
sage: G in C2
True
sage: G in C2.objects()
True
sage: F in C2
False
sage: F in C2.objects()
False
# For C3 (having a custom containment test):
sage: P in C3
False
sage: P in C3.objects()
False
sage: G in C3
False
sage: G in C3.objects()
False
sage: F in C3
True
sage: F in C3.objects()
True
}}}
Timings without the new patch (but with #10496, #10659, #8611 and #10467):
{{{
# containment in C1
sage: timeit('P in C1',number=100000)
100000 loops, best of 3: 11.1 µs per loop
sage: timeit('G in C1',number=100000)
100000 loops, best of 3: 4.32 µs per loop
sage: timeit('F in C1',number=100000)
100000 loops, best of 3: 11.9 µs per loop
# containment in C2
sage: timeit('P in C2',number=100000)
100000 loops, best of 3: 11.1 µs per loop
sage: timeit('G in C2',number=100000)
100000 loops, best of 3: 4.2 µs per loop
sage: timeit('F in C2',number=100000)
100000 loops, best of 3: 11.5 µs per loop
# containment in C3 (custom test for fields!)
sage: timeit('P in C3',number=100000)
100000 loops, best of 3: 16.1 µs per loop
sage: timeit('G in C3',number=100000)
100000 loops, best of 3: 20.5 µs per loop
sage: timeit('F in C3',number=100000)
100000 loops, best of 3: 17.9 µs per loop
}}}
Timings with the patch, including the new syntax `X in C.objects()`:
{{{
# containment in C1
sage: timeit('P in C1',number=100000)
100000 loops, best of 3: 9.29 µs per loop
sage: timeit('P in C1.objects()',number=100000)
100000 loops, best of 3: 9.85 µs per loop
sage: timeit('G in C1',number=100000)
100000 loops, best of 3: 1.91 µs per loop
sage: timeit('G in C1.objects()',number=100000)
100000 loops, best of 3: 2.45 µs per loop
sage: timeit('F in C1',number=100000)
100000 loops, best of 3: 9.51 µs per loop
sage: timeit('F in C1.objects()',number=100000)
100000 loops, best of 3: 10.2 µs per loop
# containment in C2
sage: timeit('P in C2',number=100000)
100000 loops, best of 3: 9.2 µs per loop
sage: timeit('P in C2.objects()',number=100000)
100000 loops, best of 3: 9.85 µs per loop
# using the shortpath, as G.category() is C2
sage: timeit('G in C2',number=100000)
100000 loops, best of 3: 836 ns per loop
sage: timeit('G in C2.objects()',number=100000)
100000 loops, best of 3: 1.52 µs per loop
sage: timeit('F in C2',number=100000)
100000 loops, best of 3: 9.52 µs per loop
sage: timeit('F in C2.objects()',number=100000)
100000 loops, best of 3: 10.3 µs per loop
# containment in C3 (custom test for fields!)
sage: timeit('P in C3',number=100000)
100000 loops, best of 3: 14 µs per loop
sage: timeit('P in C3.objects()',number=100000)
100000 loops, best of 3: 15.9 µs per loop
sage: timeit('G in C3',number=100000)
100000 loops, best of 3: 15.7 µs per loop
sage: timeit('G in C3.objects()',number=100000)
100000 loops, best of 3: 18.3 µs per loop
sage: timeit('F in C3',number=100000)
100000 loops, best of 3: 15.6 µs per loop
sage: timeit('F in C3.objects()',number=100000)
100000 loops, best of 3: 17.3 µs per loop
}}}
Or, directly testing containment in the class of objects:
{{{
sage: O1 = C1.objects()
sage: O2 = C2.objects()
sage: O3 = C3.objects()
sage: timeit('P in O1',number=100000)
100000 loops, best of 3: 8.88 µs per loop
sage: timeit('G in O1',number=100000)
100000 loops, best of 3: 1.56 µs per loop
sage: timeit('F in O1',number=100000)
100000 loops, best of 3: 9.31 µs per loop
sage: timeit('P in O2',number=100000)
100000 loops, best of 3: 8.94 µs per loop
sage: timeit('G in O2',number=100000)
100000 loops, best of 3: 704 ns per loop
sage: timeit('F in O2',number=100000)
100000 loops, best of 3: 9.29 µs per loop
sage: timeit('P in O3',number=100000)
100000 loops, best of 3: 14.9 µs per loop
sage: timeit('G in O3',number=100000)
100000 loops, best of 3: 17.1 µs per loop
sage: timeit('F in O3',number=100000)
100000 loops, best of 3: 16.5 µs per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10667#comment:4>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
