Coverage for local/lib/python2.7/site-packages/sage/categories/sets_cat.py : 62%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
r""" Sets """ #***************************************************************************** # Copyright (C) 2005 David Kohel <kohel@maths.usyd.edu> # William Stein <wstein@math.ucsd.edu> # 2008 Teresa Gomez-Diaz (CNRS) <Teresa.Gomez-Diaz@univ-mlv.fr> # 2008-2014 Nicolas M. Thiery <nthiery at users.sf.net> # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ #****************************************************************************** from __future__ import print_function, absolute_import from six.moves import range
from sage.misc.cachefunc import cached_method from sage.misc.sage_unittest import TestSuite from sage.misc.abstract_method import abstract_method from sage.misc.lazy_attribute import lazy_attribute from sage.misc.lazy_import import lazy_import, LazyImport from sage.misc.lazy_format import LazyFormat from sage.misc.superseded import deprecated_function_alias from sage.categories.category import Category from sage.categories.category_singleton import Category_singleton # Do not use sage.categories.all here to avoid initialization loop from sage.categories.morphism import SetMorphism from sage.categories.sets_with_partial_maps import SetsWithPartialMaps from sage.categories.subquotients import SubquotientsCategory from sage.categories.quotients import QuotientsCategory from sage.categories.subobjects import SubobjectsCategory from sage.categories.isomorphic_objects import IsomorphicObjectsCategory from sage.categories.algebra_functor import AlgebrasCategory from sage.categories.cartesian_product import CartesianProductsCategory, CartesianProductFunctor from sage.categories.realizations import RealizationsCategory, Category_realization_of_parent from sage.categories.with_realizations import WithRealizationsCategory from sage.categories.category_with_axiom import CategoryWithAxiom lazy_import('sage.sets.cartesian_product', 'CartesianProduct')
def print_compare(x, y): """ Helper method used in :meth:`Sets.ParentMethods._test_elements_eq_symmetric`, :meth:`Sets.ParentMethods._test_elements_eq_tranisitive`.
INPUT:
- ``x`` -- an element
- ``y`` -- an element
EXAMPLES::
sage: from sage.categories.sets_cat import print_compare sage: print_compare(1,2) 1 != 2 sage: print_compare(1,1) 1 == 1
""" else:
class EmptySetError(ValueError): """ Exception raised when some operation can't be performed on the empty set.
EXAMPLES::
sage: def first_element(st): ....: if not st: raise EmptySetError("no elements") ....: else: return st[0] sage: first_element(Set((1,2,3))) 1 sage: first_element(Set([])) Traceback (most recent call last): ... EmptySetError: no elements """ pass
class Sets(Category_singleton): r""" The category of sets.
The base category for collections of elements with = (equality).
This is also the category whose objects are all parents.
EXAMPLES::
sage: Sets() Category of sets sage: Sets().super_categories() [Category of sets with partial maps] sage: Sets().all_super_categories() [Category of sets, Category of sets with partial maps, Category of objects]
Let us consider an example of set::
sage: P = Sets().example("inherits") sage: P Set of prime numbers
See ``P??`` for the code.
P is in the category of sets::
sage: P.category() Category of sets
and therefore gets its methods from the following classes::
sage: for cl in P.__class__.mro(): print(cl) <class 'sage.categories.examples.sets_cat.PrimeNumbers_Inherits_with_category'> <class 'sage.categories.examples.sets_cat.PrimeNumbers_Inherits'> <class 'sage.categories.examples.sets_cat.PrimeNumbers_Abstract'> <class 'sage.structure.unique_representation.UniqueRepresentation'> <class 'sage.structure.unique_representation.CachedRepresentation'> <type 'sage.misc.fast_methods.WithEqualityById'> <type 'sage.structure.parent.Parent'> <type 'sage.structure.category_object.CategoryObject'> <type 'sage.structure.sage_object.SageObject'> <class 'sage.categories.sets_cat.Sets.parent_class'> <class 'sage.categories.sets_with_partial_maps.SetsWithPartialMaps.parent_class'> <class 'sage.categories.objects.Objects.parent_class'> <... 'object'>
We run some generic checks on P::
sage: TestSuite(P).run(verbose=True) running ._test_an_element() . . . pass running ._test_cardinality() . . . pass running ._test_category() . . . pass running ._test_elements() . . . Running the test suite of self.an_element() running ._test_category() . . . pass running ._test_eq() . . . pass running ._test_new() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_pickling() . . . pass pass running ._test_elements_eq_reflexive() . . . pass running ._test_elements_eq_symmetric() . . . pass running ._test_elements_eq_transitive() . . . pass running ._test_elements_neq() . . . pass running ._test_eq() . . . pass running ._test_new() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_pickling() . . . pass running ._test_some_elements() . . . pass
Now, we manipulate some elements of P::
sage: P.an_element() 47 sage: x = P(3) sage: x.parent() Set of prime numbers sage: x in P, 4 in P (True, False) sage: x.is_prime() True
They get their methods from the following classes::
sage: for cl in x.__class__.mro(): print(cl) <class 'sage.categories.examples.sets_cat.PrimeNumbers_Inherits_with_category.element_class'> <class 'sage.categories.examples.sets_cat.PrimeNumbers_Inherits.Element'> <type 'sage.rings.integer.IntegerWrapper'> <type 'sage.rings.integer.Integer'> <type 'sage.structure.element.EuclideanDomainElement'> <type 'sage.structure.element.PrincipalIdealDomainElement'> <type 'sage.structure.element.DedekindDomainElement'> <type 'sage.structure.element.IntegralDomainElement'> <type 'sage.structure.element.CommutativeRingElement'> <type 'sage.structure.element.RingElement'> <type 'sage.structure.element.ModuleElement'> <class 'sage.categories.examples.sets_cat.PrimeNumbers_Abstract.Element'> <type 'sage.structure.element.Element'> <type 'sage.structure.sage_object.SageObject'> <class 'sage.categories.sets_cat.Sets.element_class'> <class 'sage.categories.sets_with_partial_maps.SetsWithPartialMaps.element_class'> <class 'sage.categories.objects.Objects.element_class'> <... 'object'>
FIXME: Objects.element_class is not very meaningful ...
TESTS::
sage: TestSuite(Sets()).run()
"""
def super_categories(self): r""" We include SetsWithPartialMaps between Sets and Objects so that we can define morphisms between sets that are only partially defined. This is also to have the Homset constructor not complain that SetsWithPartialMaps is not a supercategory of Fields, for example.
EXAMPLES::
sage: Sets().super_categories() [Category of sets with partial maps] """
def _call_(self, X, enumerated_set=False): r""" Construct an object in this category from the data ``X``.
INPUT:
- ``X`` -- an object to be converted into a set
- ``enumerated_set`` -- if set to ``True`` and the input is either a Python tuple or a Python list then the output will be a finite enumerated set.
EXAMPLES::
sage: Sets()(ZZ) Integer Ring sage: Sets()([1, 2, 3]) {1, 2, 3}
sage: S = Sets()([1, 2, 3]); S.category() Category of finite sets sage: S = Sets()([1, 2, 3], enumerated_set=True); S.category() Category of facade finite enumerated sets
.. NOTE::
Using ``Sets()(A)`` used to implement some sort of forgetful functor into the ``Sets()`` category. This feature has been removed, because it was not consistent with the semantic of :meth:`Category.__call__`. Proper forgetful functors will eventually be implemented, with another syntax. """
def example(self, choice = None): """ Returns examples of objects of ``Sets()``, as per :meth:`Category.example() <sage.categories.category.Category.example>`.
EXAMPLES::
sage: Sets().example() Set of prime numbers (basic implementation)
sage: Sets().example("inherits") Set of prime numbers
sage: Sets().example("facade") Set of prime numbers (facade implementation)
sage: Sets().example("wrapper") Set of prime numbers (wrapper implementation) """ else: raise ValueError("Unkown choice")
class SubcategoryMethods:
def CartesianProducts(self): r""" Return the full subcategory of the objects of ``self`` constructed as Cartesian products.
.. SEEALSO::
- :class:`.cartesian_product.CartesianProductFunctor` - :class:`~.covariant_functorial_construction.RegressiveCovariantFunctorialConstruction`
EXAMPLES::
sage: Sets().CartesianProducts() Category of Cartesian products of sets sage: Semigroups().CartesianProducts() Category of Cartesian products of semigroups sage: EuclideanDomains().CartesianProducts() Category of Cartesian products of commutative rings """
@cached_method def Subquotients(self): r""" Return the full subcategory of the objects of ``self`` constructed as subquotients.
Given a concrete category ``self == As()`` (i.e. a subcategory of ``Sets()``), ``As().Subquotients()`` returns the category of objects of ``As()`` endowed with a distinguished description as subquotient of some other object of ``As()``.
EXAMPLES::
sage: Monoids().Subquotients() Category of subquotients of monoids
A parent `A` in ``As()`` is further in ``As().Subquotients()`` if there is a distinguished parent `B` in ``As()``, called the *ambient set*, a subobject `B'` of `B`, and a pair of maps:
.. MATH::
l: A \to B' \text{ and } r: B' \to A
called respectively the *lifting map* and *retract map* such that `r \circ l` is the identity of `A` and `r` is a morphism in ``As()``.
.. TODO:: Draw the typical commutative diagram.
It follows that, for each operation `op` of the category, we have some property like:
.. MATH::
op_A(e) = r(op_B(l(e))), \text{ for all } e\in A
This allows for implementing the operations on `A` from those on `B`.
The two most common use cases are:
- *homomorphic images* (or *quotients*), when `B'=B`, `r` is an homomorphism from `B` to `A` (typically a canonical quotient map), and `l` a section of it (not necessarily a homomorphism); see :meth:`Quotients`;
- *subobjects* (up to an isomorphism), when `l` is an embedding from `A` into `B`; in this case, `B'` is typically isomorphic to `A` through the inverse isomorphisms `r` and `l`; see :meth:`Subobjects`;
.. NOTE::
- The usual definition of "subquotient" (:wikipedia:`Subquotient`) does not involve the lifting map `l`. This map is required in Sage's context to make the definition constructive. It is only used in computations and does not affect their results. This is relatively harmless since the category is a concrete category (i.e., its objects are sets and its morphisms are set maps).
- In mathematics, especially in the context of quotients, the retract map `r` is often referred to as a *projection map* instead.
- Since `B'` is not specified explicitly, it is possible to abuse the framework with situations where `B'` is not quite a subobject and `r` not quite a morphism, as long as the lifting and retract maps can be used as above to compute all the operations in `A`. Use at your own risk!
Assumptions:
- For any category ``As()``, ``As().Subquotients()`` is a subcategory of ``As()``.
Example: a subquotient of a group is a group (e.g., a left or right quotient of a group by a non-normal subgroup is not in this category).
- This construction is covariant: if ``As()`` is a subcategory of ``Bs()``, then ``As().Subquotients()`` is a subcategory of ``Bs().Subquotients()``.
Example: if `A` is a subquotient of `B` in the category of groups, then it is also a subquotient of `B` in the category of monoids.
- If the user (or a program) calls ``As().Subquotients()``, then it is assumed that subquotients are well defined in this category. This is not checked, and probably never will be. Note that, if a category ``As()`` does not specify anything about its subquotients, then its subquotient category looks like this::
sage: EuclideanDomains().Subquotients() Join of Category of euclidean domains and Category of subquotients of monoids
Interface: the ambient set `B` of `A` is given by ``A.ambient()``. The subset `B'` needs not be specified, so the retract map is handled as a partial map from `B` to `A`.
The lifting and retract map are implemented respectively as methods ``A.lift(a)`` and ``A.retract(b)``. As a shorthand for the former, one can use alternatively ``a.lift()``::
sage: S = Semigroups().Subquotients().example(); S An example of a (sub)quotient semigroup: a quotient of the left zero semigroup sage: S.ambient() An example of a semigroup: the left zero semigroup sage: S(3).lift().parent() An example of a semigroup: the left zero semigroup sage: S(3) * S(1) == S.retract( S(3).lift() * S(1).lift() ) True
See ``S?`` for more.
.. TODO:: use a more interesting example, like `\ZZ/n\ZZ`.
.. SEEALSO::
- :meth:`Quotients`, :meth:`Subobjects`, :meth:`IsomorphicObjects` - :class:`.subquotients.SubquotientsCategory` - :class:`~.covariant_functorial_construction.RegressiveCovariantFunctorialConstruction`
TESTS::
sage: TestSuite(Sets().Subquotients()).run() """
@cached_method def Quotients(self): r""" Return the full subcategory of the objects of ``self`` constructed as quotients.
Given a concrete category ``As()`` (i.e. a subcategory of ``Sets()``), ``As().Quotients()`` returns the category of objects of ``As()`` endowed with a distinguished description as quotient (in fact homomorphic image) of some other object of ``As()``.
Implementing an object of ``As().Quotients()`` is done in the same way as for ``As().Subquotients()``; namely by providing an ambient space and a lift and a retract map. See :meth:`Subquotients` for detailed instructions.
.. SEEALSO::
- :meth:`Subquotients` for background - :class:`.quotients.QuotientsCategory` - :class:`~.covariant_functorial_construction.RegressiveCovariantFunctorialConstruction`
EXAMPLES::
sage: C = Semigroups().Quotients(); C Category of quotients of semigroups sage: C.super_categories() [Category of subquotients of semigroups, Category of quotients of sets] sage: C.all_super_categories() [Category of quotients of semigroups, Category of subquotients of semigroups, Category of semigroups, Category of subquotients of magmas, Category of magmas, Category of quotients of sets, Category of subquotients of sets, Category of sets, Category of sets with partial maps, Category of objects]
The caller is responsible for checking that the given category admits a well defined category of quotients::
sage: EuclideanDomains().Quotients() Join of Category of euclidean domains and Category of subquotients of monoids and Category of quotients of semigroups
TESTS::
sage: TestSuite(C).run() """
@cached_method def Subobjects(self): r""" Return the full subcategory of the objects of ``self`` constructed as subobjects.
Given a concrete category ``As()`` (i.e. a subcategory of ``Sets()``), ``As().Subobjects()`` returns the category of objects of ``As()`` endowed with a distinguished embedding into some other object of ``As()``.
Implementing an object of ``As().Subobjects()`` is done in the same way as for ``As().Subquotients()``; namely by providing an ambient space and a lift and a retract map. In the case of a trivial embedding, the two maps will typically be identity maps that just change the parent of their argument. See :meth:`Subquotients` for detailed instructions.
.. SEEALSO::
- :meth:`Subquotients` for background - :class:`.subobjects.SubobjectsCategory` - :class:`~.covariant_functorial_construction.RegressiveCovariantFunctorialConstruction`
EXAMPLES::
sage: C = Sets().Subobjects(); C Category of subobjects of sets
sage: C.super_categories() [Category of subquotients of sets]
sage: C.all_super_categories() [Category of subobjects of sets, Category of subquotients of sets, Category of sets, Category of sets with partial maps, Category of objects]
Unless something specific about subobjects is implemented for this category, one actually gets an optimized super category::
sage: C = Semigroups().Subobjects(); C Join of Category of subquotients of semigroups and Category of subobjects of sets
The caller is responsible for checking that the given category admits a well defined category of subobjects.
TESTS::
sage: Semigroups().Subobjects().is_subcategory(Semigroups().Subquotients()) True sage: TestSuite(C).run()
"""
@cached_method def IsomorphicObjects(self): r""" Return the full subcategory of the objects of ``self`` constructed by isomorphism.
Given a concrete category ``As()`` (i.e. a subcategory of ``Sets()``), ``As().IsomorphicObjects()`` returns the category of objects of ``As()`` endowed with a distinguished description as the image of some other object of ``As()`` by an isomorphism in this category.
See :meth:`Subquotients` for background.
EXAMPLES:
In the following example, `A` is defined as the image by `x\mapsto x^2` of the finite set `B = \{1,2,3\}`::
sage: A = FiniteEnumeratedSets().IsomorphicObjects().example(); A The image by some isomorphism of An example of a finite enumerated set: {1,2,3}
Since `B` is a finite enumerated set, so is `A`::
sage: A in FiniteEnumeratedSets() True sage: A.cardinality() 3 sage: A.list() [1, 4, 9]
The isomorphism from `B` to `A` is available as::
sage: A.retract(3) 9
and its inverse as::
sage: A.lift(9) 3
It often is natural to declare those morphisms as coercions so that one can do ``A(b)`` and ``B(a)`` to go back and forth between `A` and `B` (TODO: refer to a category example where the maps are declared as a coercion). This is not done by default. Indeed, in many cases one only wants to transport part of the structure of `B` to `A`. Assume for example, that one wants to construct the set of integers `B=ZZ`, endowed with ``max`` as addition, and ``+`` as multiplication instead of the usual ``+`` and ``*``. One can construct `A` as isomorphic to `B` as an infinite enumerated set. However `A` is *not* isomorphic to `B` as a ring; for example, for `a\in A` and `a\in B`, the expressions `a+A(b)` and `B(a)+b` give completely different results; hence we would not want the expression `a+b` to be implicitly resolved to any one of above two, as the coercion mechanism would do.
Coercions also cannot be used with facade parents (see :class:`Sets.Facade`) like in the example above.
We now look at a category of isomorphic objects::
sage: C = Sets().IsomorphicObjects(); C Category of isomorphic objects of sets
sage: C.super_categories() [Category of subobjects of sets, Category of quotients of sets]
sage: C.all_super_categories() [Category of isomorphic objects of sets, Category of subobjects of sets, Category of quotients of sets, Category of subquotients of sets, Category of sets, Category of sets with partial maps, Category of objects]
Unless something specific about isomorphic objects is implemented for this category, one actually get an optimized super category::
sage: C = Semigroups().IsomorphicObjects(); C Join of Category of quotients of semigroups and Category of isomorphic objects of sets
.. SEEALSO::
- :meth:`Subquotients` for background - :class:`.isomorphic_objects.IsomorphicObjectsCategory` - :class:`~.covariant_functorial_construction.RegressiveCovariantFunctorialConstruction`
TESTS::
sage: TestSuite(Sets().IsomorphicObjects()).run() """
@cached_method def Topological(self): """ Return the subcategory of the topological objects of ``self``.
TESTS::
sage: TestSuite(Sets().Topological()).run() """
@cached_method def Metric(self): """ Return the subcategory of the metric objects of ``self``.
TESTS::
sage: TestSuite(Sets().Metric()).run() """
@cached_method def Algebras(self, base_ring): """ Return the category of objects constructed as algebras of objects of ``self`` over ``base_ring``.
INPUT:
- ``base_ring`` -- a ring
See :meth:`Sets.ParentMethods.algebra` for the precise meaning in Sage of the *algebra of an object*.
EXAMPLES::
sage: Monoids().Algebras(QQ) Category of monoid algebras over Rational Field
sage: Groups().Algebras(QQ) Category of group algebras over Rational Field
sage: AdditiveMagmas().AdditiveAssociative().Algebras(QQ) Category of additive semigroup algebras over Rational Field
sage: Monoids().Algebras(Rings()) Category of monoid algebras over Category of rings
.. SEEALSO::
- :class:`.algebra_functor.AlgebrasCategory` - :class:`~.covariant_functorial_construction.CovariantFunctorialConstruction`
TESTS::
sage: TestSuite(Groups().Finite().Algebras(QQ)).run() """ and base_ring.is_subcategory(Rings()))
@cached_method def Finite(self): """ Return the full subcategory of the finite objects of ``self``.
EXAMPLES::
sage: Sets().Finite() Category of finite sets sage: Rings().Finite() Category of finite rings
TESTS::
sage: TestSuite(Sets().Finite()).run() sage: Rings().Finite.__module__ 'sage.categories.sets_cat' """
@cached_method def Infinite(self): """ Return the full subcategory of the infinite objects of ``self``.
EXAMPLES::
sage: Sets().Infinite() Category of infinite sets sage: Rings().Infinite() Category of infinite rings
TESTS::
sage: TestSuite(Sets().Infinite()).run() sage: Rings().Infinite.__module__ 'sage.categories.sets_cat' """
@cached_method def Enumerated(self): """ Return the full subcategory of the enumerated objects of ``self``.
An enumerated object can be iterated to get its elements.
EXAMPLES::
sage: Sets().Enumerated() Category of enumerated sets sage: Rings().Finite().Enumerated() Category of finite enumerated rings sage: Rings().Infinite().Enumerated() Category of infinite enumerated rings
TESTS::
sage: TestSuite(Sets().Enumerated()).run() sage: Rings().Enumerated.__module__ 'sage.categories.sets_cat' """
def Facade(self): r""" Return the full subcategory of the facade objects of ``self``.
.. _facade-sets:
.. RUBRIC:: What is a facade set?
Recall that, in Sage, :ref:`sets are modelled by *parents* <category-primer-parents-elements-categories>`, and their elements know which distinguished set they belong to. For example, the ring of integers `\ZZ` is modelled by the parent :obj:`ZZ`, and integers know that they belong to this set::
sage: ZZ Integer Ring sage: 42.parent() Integer Ring
Sometimes, it is convenient to represent the elements of a parent ``P`` by elements of some other parent. For example, the elements of the set of prime numbers are represented by plain integers::
sage: Primes() Set of all prime numbers: 2, 3, 5, 7, ... sage: p = Primes().an_element(); p 43 sage: p.parent() Integer Ring
In this case, ``P`` is called a *facade set*.
This feature is advertised through the category of `P`::
sage: Primes().category() Category of facade infinite enumerated sets sage: Sets().Facade() Category of facade sets
Typical use cases include modeling a subset of an existing parent::
sage: Set([4,6,9]) # random {4, 6, 9} sage: Sets().Facade().example() An example of facade set: the monoid of positive integers
or the union of several parents::
sage: Sets().Facade().example("union") An example of a facade set: the integers completed by +-infinity
or endowing an existing parent with more (or less!) structure::
sage: Posets().example("facade") An example of a facade poset: the positive integers ordered by divisibility
Let us investigate in detail a close variant of this last example: let `P` be set of divisors of `12` partially ordered by divisibility. There are two options for representing its elements:
1. as plain integers::
sage: P = Poset((divisors(12), attrcall("divides")), facade=True)
2. as integers, modified to be aware that their parent is `P`::
sage: Q = Poset((divisors(12), attrcall("divides")), facade=False)
The advantage of option 1. is that one needs not do conversions back and forth between `P` and `\ZZ`. The disadvantage is that this introduces an ambiguity when writing `2 < 3`: does this compare `2` and `3` w.r.t. the natural order on integers or w.r.t. divisibility?::
sage: 2 < 3 True
To raise this ambiguity, one needs to explicitly specify the underlying poset as in `2 <_P 3`::
sage: P = Posets().example("facade") sage: P.lt(2,3) False
On the other hand, with option 2. and once constructed, the elements know unambiguously how to compare themselves::
sage: Q(2) < Q(3) False sage: Q(2) < Q(6) True
Beware that ``P(2)`` is still the integer `2`. Therefore ``P(2) < P(3)`` still compares `2` and `3` as integers!::
sage: P(2) < P(3) True
In short `P` being a facade parent is one of the programmatic counterparts (with e.g. coercions) of the usual mathematical idiom: "for ease of notation, we identify an element of `P` with the corresponding integer". Too many identifications lead to confusion; the lack thereof leads to heavy, if not obfuscated, notations. Finding the right balance is an art, and even though there are common guidelines, it is ultimately up to the writer to choose which identifications to do. This is no different in code.
.. SEEALSO::
The following examples illustrate various ways to implement subsets like the set of prime numbers; look at their code for details::
sage: Sets().example("facade") Set of prime numbers (facade implementation) sage: Sets().example("inherits") Set of prime numbers sage: Sets().example("wrapper") Set of prime numbers (wrapper implementation)
.. RUBRIC:: Specifications
A parent which is a facade must either:
- call :meth:`Parent.__init__` using the ``facade`` parameter to specify a parent, or tuple thereof. - overload the method :meth:`~Sets.Facade.ParentMethods.facade_for`.
.. NOTE::
The concept of facade parents was originally introduced in the computer algebra system MuPAD.
TESTS:
Check that multiple categories initialisation works (:trac:`13801`)::
sage: class A(Parent): ....: def __init__(self): ....: Parent.__init__(self, category=(FiniteEnumeratedSets(),Monoids()), facade=True) sage: a = A()
sage: Posets().Facade() Category of facade posets sage: Posets().Facade().Finite() is Posets().Finite().Facade() True """
Facades = deprecated_function_alias(17073, Facade)
class ParentMethods: # TODO: simplify the _element_constructor_ definition logic # TODO: find a nicer mantra for conditionally defined methods @lazy_attribute def _element_constructor_(self): r""" TESTS::
sage: S = Sets().example() sage: S._element_constructor_(17) 17 sage: S(17) # indirect doctest 17
sage: A = FreeModule(QQ, 3) sage: A.element_class <type 'sage.modules.vector_rational_dense.Vector_rational_dense'> sage: A._element_constructor_ <bound method FreeModule_ambient_field_with_category._element_constructor_ of Vector space of dimension 3 over Rational Field>
sage: B = SymmetricGroup(3).algebra(ZZ) sage: B.element_class <...SymmetricGroupAlgebra_n_with_category.element_class'> sage: B._element_constructor_ <bound method SymmetricGroupAlgebra_n_with_category._element_constructor_ of Symmetric group algebra of order 3 over Integer Ring> """ else:
def _element_constructor_from_element_class(self, *args, **keywords): """ The default constructor for elements of this parent ``self``.
Among other things, it is called upon ``self(data)`` when the coercion model did not find a way to coerce ``data`` into this parent.
This default implementation for :meth:`_element_constructor_` calls the constructor of the element class, passing ``self`` as first argument.
EXAMPLES::
sage: S = Sets().example("inherits") sage: s = S._element_constructor_from_element_class(17); s 17 sage: type(s) <class 'sage.categories.examples.sets_cat.PrimeNumbers_Inherits_with_category.element_class'> """
def is_parent_of(self, element): """ Return whether ``self`` is the parent of ``element``.
INPUT:
- ``element`` -- any object
EXAMPLES::
sage: S = ZZ sage: S.is_parent_of(1) True sage: S.is_parent_of(2/1) False
This method differs from :meth:`__contains__` because it does not attempt any coercion::
sage: 2/1 in S, S.is_parent_of(2/1) (True, False) sage: int(1) in S, S.is_parent_of(int(1)) (True, False) """
@abstract_method def __contains__(self, x): """ Test whether the set ``self`` contains the object ``x``.
All parents in the category ``Sets()`` should implement this method.
EXAMPLES::
sage: P = Sets().example(); P Set of prime numbers (basic implementation) sage: 12 in P False sage: P(5) in P True """
@cached_method def an_element(self): r""" Return a (preferably typical) element of this parent.
This is used both for illustration and testing purposes. If the set ``self`` is empty, :meth:`an_element` should raise the exception :class:`EmptySetError`.
This default implementation calls :meth:`_an_element_` and caches the result. Any parent should implement either :meth:`an_element` or :meth:`_an_element_`.
EXAMPLES::
sage: CDF.an_element() 1.0*I sage: ZZ[['t']].an_element() t """ return self._an_element_()
def _test_an_element(self, **options): """ Run generic tests on the method :meth:`.an_element`.
See also: :class:`TestSuite`.
EXAMPLES::
sage: C = Sets().example() sage: C._test_an_element()
Let us now write a broken :meth:`.an_element` method::
sage: from sage.categories.examples.sets_cat import PrimeNumbers sage: class CCls(PrimeNumbers): ....: def an_element(self): ....: return 18 sage: CC = CCls() sage: CC._test_an_element() Traceback (most recent call last): ... AssertionError: self.an_element() is not in self
TESTS::
sage: FiniteEnumeratedSet([])._test_an_element() """ # tester.assertTrue(self.is_parent_of(an_element), "self is not the parent of self.an_element()") # tester.assertEqual(self(an_element), an_element, "element construction is not idempotent") else: # Allows self(an_element) to fails for facade parent. else:
def _test_elements(self, tester = None, **options): """ Run generic tests on element(s) of ``self``.
See also: :class:`TestSuite`.
EXAMPLES::
sage: C = Sets().example() sage: C._test_elements(verbose = True) <BLANKLINE> Running the test suite of self.an_element() running ._test_category() . . . pass running ._test_eq() . . . pass running ._test_new() . . . pass running ._test_nonzero_equal() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_pickling() . . . pass <BLANKLINE>
Debugging tip: in case of failure of this test, run instead::
sage: TestSuite(C.an_element()).run()
Let us now implement a parent whose elements cannot be pickled::
sage: from sage.categories.examples.sets_cat import PrimeNumbers sage: class Bla(SageObject): pass sage: class CCls(PrimeNumbers): ....: def an_element(self): ....: return Bla() sage: CC = CCls() sage: CC._test_elements() Failure in _test_pickling: ... PicklingError: Can't pickle <class '__main__.Bla'>: attribute lookup __main__.Bla failed ... The following tests failed: _test_pickling """ # TODO: add native support for nested test suites to TestSuite
# The intention is to raise an exception only if this is # run as a sub-testsuite of a larger testsuite. # Or do we want to run the test on some_elements? raise_on_failure = is_sub_testsuite)
def _test_elements_eq_reflexive(self, **options): """ Run generic tests on the equality of elements.
Test that ``==`` is reflexive.
See also: :class:`TestSuite`.
EXAMPLES::
sage: C = Sets().example() sage: C._test_elements_eq_reflexive()
We try a non-reflexive equality::
sage: P = Sets().example("wrapper") sage: P._test_elements_eq_reflexive() sage: eq = P.element_class.__eq__
sage: P.element_class.__eq__ = (lambda x, y: ....: False if eq(x, P(47)) and eq(y, P(47)) else eq(x, y)) sage: P._test_elements_eq_reflexive() Traceback (most recent call last): ... AssertionError: 47 != 47
We restore ``P.element_class`` in a proper state for further tests::
sage: P.element_class.__eq__ = eq
"""
def _test_elements_eq_symmetric(self, **options): """ Run generic tests on the equality of elements.
This tests that ``==`` is symmetric.
See also: :class:`TestSuite`.
EXAMPLES::
sage: C = Sets().example() sage: C._test_elements_eq_symmetric()
We test a non symmetric equality::
sage: P = Sets().example("wrapper") sage: P._test_elements_eq_symmetric() sage: eq = P.element_class.__eq__
sage: def non_sym_eq(x, y): ....: if not y in P: return False ....: elif eq(x, P(47)) and eq(y, P(53)): return True ....: else: return eq(x, y) sage: P.element_class.__eq__ = non_sym_eq sage: P._test_elements_eq_symmetric() Traceback (most recent call last): ... AssertionError: non symmetric equality: 47 == 53 but 53 != 47
We restore ``P.element_class`` in a proper state for further tests::
sage: P.element_class.__eq__ = eq
""" LazyFormat("non symmetric equality: %s but %s")%( print_compare(x, y), print_compare(y, x)))
def _test_elements_eq_transitive(self, **options): """ Run generic tests on the equality of elements.
Test that ``==`` is transitive.
See also: :class:`TestSuite`.
EXAMPLES::
sage: C = Sets().example() sage: C._test_elements_eq_transitive()
We test a non transitive equality::
sage: R = Zp(3) sage: Sets().ParentMethods._test_elements_eq_transitive.__func__(R,elements=[R(3,2),R(3,1),R(0)]) Traceback (most recent call last): ... AssertionError: non transitive equality: 3 + O(3^2) == O(3) and O(3) == 0 but 3 + O(3^2) != 0
""" else:
LazyFormat("non transitive equality:\n" "%s and %s but %s")%( print_compare(x, y), print_compare(y, z), print_compare(x, z)))
def _test_elements_neq(self, **options): """ Run generic tests on the equality of elements.
Test that ``==`` and ``!=`` are consistent.
See also: :class:`TestSuite`.
EXAMPLES::
sage: C = Sets().example() sage: C._test_elements_neq()
We try a broken inequality::
sage: P = Sets().example("wrapper") sage: P._test_elements_neq() sage: ne = P.element_class.__ne__ sage: eq = P.element_class.__eq__
sage: P.element_class.__ne__ = lambda x, y: False sage: P._test_elements_neq() Traceback (most recent call last): ... AssertionError: __eq__ and __ne__ inconsistency: 47 == 53 returns False but 47 != 53 returns False
sage: P.element_class.__ne__ = lambda x, y: not(x == y)
We restore ``P.element_class`` in a proper state for further tests::
sage: P.element_class.__ne__ = ne sage: P.element_class.__eq__ = eq """
LazyFormat("__eq__ and __ne__ inconsistency:\n" " %s == %s returns %s but %s != %s returns %s")%( x, y, (x == y), x, y, (x != y)))
def some_elements(self): """ Return a list (or iterable) of elements of ``self``.
This is typically used for running generic tests (see :class:`TestSuite`).
This default implementation calls :meth:`.an_element`.
EXAMPLES::
sage: S = Sets().example(); S Set of prime numbers (basic implementation) sage: S.an_element() 47 sage: S.some_elements() [47] sage: S = Set([]) sage: S.some_elements() []
This method should return an iterable, *not* an iterator. """
def _test_some_elements(self, **options): """ Run generic tests on the method :meth:`.some_elements`.
.. SEEALSO:: :class:`TestSuite`
EXAMPLES::
sage: C = Sets().example() sage: C._test_some_elements()
Let us now write a broken :meth:`.some_elements` method::
sage: from sage.categories.examples.sets_cat import * sage: class CCls(PrimeNumbers): ....: def some_elements(self): ....: return [self(17), 32] sage: CC = CCls() sage: CC._test_some_elements() Traceback (most recent call last): ... AssertionError: the object 32 in self.some_elements() is not in self """ # Todo: enable this once #tester.assertTrue(elements != iter(elements), # "self.some_elements() should return an iterable, not an iterator") "the object %s in self.some_elements() is not in self")%(x,))
#Note: the four methods 'cardinality', 'is_finite_, 'is_empty' and # 'random_element' might or might not be implemented in the parent # objects. Most of the time a default implementation will be provided by # a subcategory of Sets. We do not declare them as optional abstract # methods to not pollute the namespace.
# def cardinality(self) # def is_finite(self) # def is_empty(self) # def random_element(self):
def _test_cardinality(self, **options): r""" Run generic test on the method :meth:`.cardinality`.
EXAMPLES::
sage: C = Sets().example() sage: C._test_cardinality()
Let us now write a broken :meth:`cardinality` method::
sage: from sage.categories.examples.sets_cat import * sage: class CCls(PrimeNumbers): ....: def cardinality(self): ....: return int(5) sage: CC = CCls() sage: CC._test_cardinality() Traceback (most recent call last): ... AssertionError: the output of the method cardinality must either be a Sage integer or infinity. Not <... 'int'>. """ "the output of the method cardinality must either be a Sage integer or infinity. Not {}.".format(type(cardinality)))
# Functorial constructions
def construction(self): """ Return a pair ``(functor, parent)`` such that ``functor(parent)`` returns ``self``. If ``self`` does not have a functorial construction, return ``None``.
EXAMPLES::
sage: QQ.construction() (FractionField, Integer Ring) sage: f, R = QQ['x'].construction() sage: f Poly[x] sage: R Rational Field sage: f(R) Univariate Polynomial Ring in x over Rational Field """
CartesianProduct = CartesianProduct def cartesian_product(*parents, **kwargs): """ Return the Cartesian product of the parents.
INPUT:
- ``parents`` -- a list (or other iterable) of parents.
- ``category`` -- (default: ``None``) the category the Cartesian product belongs to. If ``None`` is passed, then :meth:`~sage.categories.covariant_functorial_construction.CovariantFactorialConstruction.category_from_parents` is used to determine the category.
- ``extra_category`` -- (default: ``None``) a category that is added to the Cartesian product in addition to the categories obtained from the parents.
- other keyword arguments will passed on to the class used for this Cartesian product (see also :class:`~sage.sets.cartesian_product.CartesianProduct`).
OUTPUT:
The Cartesian product.
EXAMPLES::
sage: C = AlgebrasWithBasis(QQ) sage: A = C.example(); A.rename("A") sage: A.cartesian_product(A,A) A (+) A (+) A sage: ZZ.cartesian_product(GF(2), FiniteEnumeratedSet([1,2,3])) The Cartesian product of (Integer Ring, Finite Field of size 2, {1, 2, 3})
sage: C = ZZ.cartesian_product(A); C The Cartesian product of (Integer Ring, A)
TESTS::
sage: type(C) <class 'sage.sets.cartesian_product.CartesianProduct_with_category'> sage: C.category() Join of Category of rings and ... and Category of Cartesian products of commutative additive groups
::
sage: cartesian_product([ZZ, ZZ], category=Sets()).category() Category of sets sage: cartesian_product([ZZ, ZZ]).category() Join of Category of Cartesian products of commutative rings and Category of Cartesian products of enumerated sets sage: cartesian_product([ZZ, ZZ], extra_category=Posets()).category() Join of Category of Cartesian products of commutative rings and Category of posets and Category of Cartesian products of enumerated sets """
category = tuple(category) + (extra_category,) else:
def algebra(self, base_ring, category=None, **kwds): """ Return the algebra of ``self`` over ``base_ring``.
INPUT:
- ``self`` -- a parent `S` - ``base_ring`` -- a ring `K` - ``category`` -- a super category of the category of `S`, or ``None``
This returns the space of formal linear combinations of elements of `G` with coefficients in `R`, endowed with whatever structure can be induced from that of `S`. See the documentation of :mod:`sage.categories.algebra_functor` for details.
EXAMPLES:
If `S` is a :class:`group <Groups>`, the result is its group algebra `KS`::
sage: S = DihedralGroup(4); S Dihedral group of order 8 as a permutation group sage: A = S.algebra(QQ); A Algebra of Dihedral group of order 8 as a permutation group over Rational Field sage: A.category() Category of finite group algebras over Rational Field sage: a = A.an_element(); a () + 4*(1,2,3,4) + 2*(1,4)(2,3)
This space is endowed with an algebra structure, obtained by extending by bilinearity the multiplication of `G` to a multiplication on `RG`::
sage: a * a 5*() + 8*(2,4) + 8*(1,2,3,4) + 8*(1,3) + 16*(1,3)(2,4) + 4*(1,4)(2,3)
If `S` is a :class:`monoid <Monoids>`, the result is its monoid algebra `KS`::
sage: S = Monoids().example(); S An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd') sage: A = S.algebra(QQ); A Algebra of An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd') over Rational Field sage: A.category() Category of monoid algebras over Rational Field
Similarly, we can construct algebras for additive magmas, monoids, and groups.
One may specify for which category one takes the algebra; here we build the algebra of the additive group `GF_3`::
sage: from sage.categories.additive_groups import AdditiveGroups sage: S = GF(7) sage: A = S.algebra(QQ, category=AdditiveGroups()); A Algebra of Finite Field of size 7 over Rational Field sage: A.category() Category of finite dimensional additive group algebras over Rational Field
sage: a = A(S(1)) sage: a 1 sage: 1 + a * a * a 0 + 3
Note that the ``category`` keyword needs to be fed with the structure on `S` to be used, not the induced structure on the result. """ """ `S = {}` is both an additive and a multiplicative semigroup. Constructing its algebra is ambiguous. Please use, e.g., S.algebra(QQ, category=Semigroups())""".format(self)) or category.is_subcategory(AdditiveGroups())): # Somewhat dirty hack to wrap non-atomic objects category=algebra_category, **kwds)
class ElementMethods: ## Should eventually contain the basic operations which are no math ## latex, hash, ... ##def equal(x,y): ##def =(x,y):
# Used by Element._test_category _dummy_attribute = None
def cartesian_product(*elements): """ Return the Cartesian product of its arguments, as an element of the Cartesian product of the parents of those elements.
EXAMPLES::
sage: C = AlgebrasWithBasis(QQ) sage: A = C.example() sage: (a,b,c) = A.algebra_generators() sage: a.cartesian_product(b, c) B[(0, word: a)] + B[(1, word: b)] + B[(2, word: c)]
FIXME: is this a policy that we want to enforce on all parents? """
class MorphismMethods: @abstract_method(optional=True) def __invert__(self): r""" Return the inverse morphism, or raise an error.
The error may either state that the morphism is not invertible, or that Sage cannot invert it.
EXAMPLES::
sage: i = End(QQ).identity(); i Identity endomorphism of Rational Field sage: i.__invert__() Identity endomorphism of Rational Field
This method is meant to be used with the Python inversion operator `~`::
sage: ~i Identity endomorphism of Rational Field
We now try to inverse a couple of morphisms defined by a matrix::
sage: H = End(QQ^2) sage: phi = H(matrix([[1,1],[0,1]])); phi Vector space morphism represented by the matrix: [1 1] [0 1] Domain: Vector space of dimension 2 over Rational Field Codomain: Vector space of dimension 2 over Rational Field sage: ~phi Vector space morphism represented by the matrix: [ 1 -1] [ 0 1] Domain: Vector space of dimension 2 over Rational Field Codomain: Vector space of dimension 2 over Rational Field
sage: phi = H(matrix([[1,1],[1,1]])) sage: ~phi Traceback (most recent call last): ... ZeroDivisionError: matrix morphism not invertible
.. NOTE::
This is an optional method. A default implementation raising ``NotImplementedError`` could be provided instead. """
def is_injective(self): r""" Return whether this map is injective.
EXAMPLES::
sage: f = ZZ.hom(GF(3)); f Natural morphism: From: Integer Ring To: Finite Field of size 3 sage: f.is_injective() False
Note that many maps do not implement this method::
sage: R.<x> = ZZ[] sage: f = R.hom([x]) sage: f.is_injective() Traceback (most recent call last): ... NotImplementedError
""" return True return False
Enumerated = LazyImport('sage.categories.enumerated_sets', 'EnumeratedSets', at_startup=True) Facade = LazyImport('sage.categories.facade_sets', 'FacadeSets') Finite = LazyImport('sage.categories.finite_sets', 'FiniteSets', at_startup=True) Topological = LazyImport('sage.categories.topological_spaces', 'TopologicalSpaces', 'Topological', at_startup=True) Metric = LazyImport('sage.categories.metric_spaces', 'MetricSpaces', 'Mertic', at_startup=True)
class Infinite(CategoryWithAxiom):
class ParentMethods:
def is_finite(self): """ Return whether this set is finite.
Since this set is infinite this always returns ``False``.
EXAMPLES::
sage: C = InfiniteEnumeratedSets().example() sage: C.is_finite() False
TESTS::
sage: from six import get_method_function as gmf sage: gmf(C.is_finite) is gmf(sage.categories.sets_cat.Sets.Infinite.ParentMethods.is_finite) True """
def is_empty(self): r""" Return whether this set is empty.
Since this set is infinite this always returns ``False``.
EXAMPLES::
sage: C = InfiniteEnumeratedSets().example() sage: C.is_empty() False """ return False
def cardinality(self): """ Count the elements of the enumerated set.
EXAMPLES::
sage: NN = InfiniteEnumeratedSets().example() sage: NN.cardinality() +Infinity """
class Subquotients(SubquotientsCategory): """ A category for subquotients of sets.
.. SEEALSO:: :meth:`Sets().Subquotients`
EXAMPLES::
sage: Sets().Subquotients() Category of subquotients of sets sage: Sets().Subquotients().all_super_categories() [Category of subquotients of sets, Category of sets, Category of sets with partial maps, Category of objects] """
class ParentMethods:
def _repr_(self): """ EXAMPLES::
sage: from sage.categories.examples.semigroups import IncompleteSubquotientSemigroup sage: S = IncompleteSubquotientSemigroup() sage: S._repr_() 'A subquotient of An example of a semigroup: the left zero semigroup' """
@abstract_method def ambient(self): """ Return the ambient space for ``self``.
EXAMPLES::
sage: Semigroups().Subquotients().example().ambient() An example of a semigroup: the left zero semigroup
.. SEEALSO::
:meth:`Sets.SubcategoryMethods.Subquotients` for the specifications and :meth:`.lift` and :meth:`.retract`. """
# Should lift and retract be declared as conversions to the coercion mechanism ? # Compatibility issue: in IntegerModRing, lift is a method returning the actual # lifting morphism:: # # sage: F = IntegerModRing(3) # sage: F.lift() # Set-theoretic ring morphism: # From: Ring of integers modulo 3 # To: Integer Ring # Defn: Choice of lifting map @abstract_method def lift(self, x): """ Lift `x` to the ambient space for ``self``.
INPUT:
- ``x`` -- an element of ``self``
EXAMPLES::
sage: S = Semigroups().Subquotients().example() sage: s = S.an_element() sage: s, s.parent() (42, An example of a (sub)quotient semigroup: a quotient of the left zero semigroup) sage: S.lift(s), S.lift(s).parent() (42, An example of a semigroup: the left zero semigroup) sage: s.lift(), s.lift().parent() (42, An example of a semigroup: the left zero semigroup)
.. SEEALSO::
:class:`Sets.SubcategoryMethods.Subquotients` for the specifications, :meth:`.ambient`, :meth:`.retract`, and also :meth:`Sets.Subquotients.ElementMethods.lift`. """
@abstract_method def retract(self, x): """ Retract ``x`` to ``self``.
INPUT:
- ``x`` -- an element of the ambient space for ``self``
.. SEEALSO::
:class:`Sets.SubcategoryMethods.Subquotients` for the specifications, :meth:`.ambient`, :meth:`.retract`, and also :meth:`Sets.Subquotients.ElementMethods.retract`.
EXAMPLES::
sage: S = Semigroups().Subquotients().example() sage: s = S.ambient().an_element() sage: s, s.parent() (42, An example of a semigroup: the left zero semigroup) sage: S.retract(s), S.retract(s).parent() (42, An example of a (sub)quotient semigroup: a quotient of the left zero semigroup) """
class ElementMethods:
def lift(self): """ Lift ``self`` to the ambient space for its parent.
EXAMPLES::
sage: S = Semigroups().Subquotients().example() sage: s = S.an_element() sage: s, s.parent() (42, An example of a (sub)quotient semigroup: a quotient of the left zero semigroup) sage: S.lift(s), S.lift(s).parent() (42, An example of a semigroup: the left zero semigroup) sage: s.lift(), s.lift().parent() (42, An example of a semigroup: the left zero semigroup) """
class Quotients(QuotientsCategory): """ A category for quotients of sets.
.. SEEALSO:: :meth:`Sets().Quotients`
EXAMPLES::
sage: Sets().Quotients() Category of quotients of sets sage: Sets().Quotients().all_super_categories() [Category of quotients of sets, Category of subquotients of sets, Category of sets, Category of sets with partial maps, Category of objects] """
class ParentMethods:
def _repr_(self): """ EXAMPLES::
sage: from sage.categories.examples.semigroups import IncompleteSubquotientSemigroup sage: S = IncompleteSubquotientSemigroup(category=Semigroups().Quotients()) sage: S._repr_() 'A quotient of An example of a semigroup: the left zero semigroup' """
def _an_element_(self): """ Return an element of ``self``, as per :meth:`Sets.ParentMethods.an_element`
EXAMPLES::
sage: S = FiniteEnumeratedSets().IsomorphicObjects().example() sage: S.an_element() # indirect doctest 1 """
class Subobjects(SubobjectsCategory): """ A category for subobjects of sets.
.. SEEALSO:: :meth:`Sets().Subobjects`
EXAMPLES::
sage: Sets().Subobjects() Category of subobjects of sets sage: Sets().Subobjects().all_super_categories() [Category of subobjects of sets, Category of subquotients of sets, Category of sets, Category of sets with partial maps, Category of objects] """
class ParentMethods:
def _repr_(self): """ EXAMPLES::
sage: from sage.categories.examples.semigroups import IncompleteSubquotientSemigroup sage: S = IncompleteSubquotientSemigroup(category = Semigroups().Subobjects()) sage: S._repr_() 'A subobject of An example of a semigroup: the left zero semigroup' """
class IsomorphicObjects(IsomorphicObjectsCategory): """ A category for isomorphic objects of sets.
EXAMPLES::
sage: Sets().IsomorphicObjects() Category of isomorphic objects of sets sage: Sets().IsomorphicObjects().all_super_categories() [Category of isomorphic objects of sets, Category of subobjects of sets, Category of quotients of sets, Category of subquotients of sets, Category of sets, Category of sets with partial maps, Category of objects] """
class ParentMethods:
def _repr_(self): """ EXAMPLES::
sage: S = FiniteEnumeratedSets().IsomorphicObjects().example() sage: S._repr_() 'The image by some isomorphism of An example of a finite enumerated set: {1,2,3}' """
class CartesianProducts(CartesianProductsCategory): """ EXAMPLES::
sage: C = Sets().CartesianProducts().example() sage: C The Cartesian product of (Set of prime numbers (basic implementation), An example of an infinite enumerated set: the non negative integers, An example of a finite enumerated set: {1,2,3}) sage: C.category() Category of Cartesian products of sets sage: C.categories() [Category of Cartesian products of sets, Category of sets, Category of sets with partial maps, Category of objects] sage: TestSuite(C).run() """
def extra_super_categories(self): """ A Cartesian product of sets is a set.
EXAMPLES::
sage: Sets().CartesianProducts().extra_super_categories() [Category of sets] sage: Sets().CartesianProducts().super_categories() [Category of sets] """
def example(self): """ EXAMPLES::
sage: Sets().CartesianProducts().example() The Cartesian product of (Set of prime numbers (basic implementation), An example of an infinite enumerated set: the non negative integers, An example of a finite enumerated set: {1,2,3}) """
class ParentMethods: def __iter__(self): r""" Return a lexicographic iterator for the elements of this Cartesian product.
EXAMPLES::
sage: for x,y in cartesian_product([Set([1,2]), Set(['a','b'])]): ....: print((x, y)) (1, 'a') (1, 'b') (2, 'a') (2, 'b')
sage: A = FiniteEnumeratedSets()(["a", "b"]) sage: B = FiniteEnumeratedSets().example(); B An example of a finite enumerated set: {1,2,3} sage: C = cartesian_product([A, B, A]); C The Cartesian product of ({'a', 'b'}, An example of a finite enumerated set: {1,2,3}, {'a', 'b'}) sage: C in FiniteEnumeratedSets() True sage: list(C) [('a', 1, 'a'), ('a', 1, 'b'), ('a', 2, 'a'), ('a', 2, 'b'), ('a', 3, 'a'), ('a', 3, 'b'), ('b', 1, 'a'), ('b', 1, 'b'), ('b', 2, 'a'), ('b', 2, 'b'), ('b', 3, 'a'), ('b', 3, 'b')] sage: C.__iter__.__module__ 'sage.categories.sets_cat'
sage: F22 = GF(2).cartesian_product(GF(2)) sage: list(F22) [(0, 0), (0, 1), (1, 0), (1, 1)]
sage: C = cartesian_product([Permutations(10)]*4) sage: it = iter(C) sage: next(it) ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) sage: next(it) ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 10, 9])
.. WARNING::
The elements are returned in lexicographic order, which gives a valid enumeration only if all factors, but possibly the first one, are finite. So the following one is fine::
sage: it = iter(cartesian_product([ZZ, GF(2)])) sage: [next(it) for _ in range(10)] [(0, 0), (0, 1), (1, 0), (1, 1), (-1, 0), (-1, 1), (2, 0), (2, 1), (-2, 0), (-2, 1)]
But this one is not::
sage: it = iter(cartesian_product([GF(2), ZZ])) sage: [next(it) for _ in range(10)] doctest:...: UserWarning: Sage is not able to determine whether the factors of this Cartesian product are finite. The lexicographic ordering might not go through all elements. [(0, 0), (0, 1), (0, -1), (0, 2), (0, -2), (0, 3), (0, -3), (0, 4), (0, -4), (0, 5)]
.. NOTE::
Here it would be faster to use :func:`itertools.product` for sets of small size. But the latter expands all factor in memory! So we can not reasonably use it in general.
ALGORITHM:
Recipe 19.9 in the Python Cookbook by Alex Martelli and David Ascher. """ "this Cartesian product are finite. The lexicographic " "ordering might not go through all elements.")
# visualize an odometer, with "wheels" displaying "digits"...: else:
@cached_method def an_element(self): """ EXAMPLES::
sage: C = Sets().CartesianProducts().example(); C The Cartesian product of (Set of prime numbers (basic implementation), An example of an infinite enumerated set: the non negative integers, An example of a finite enumerated set: {1,2,3}) sage: C.an_element() (47, 42, 1) """
def is_empty(self): r""" Return whether this set is empty.
EXAMPLES::
sage: S1 = FiniteEnumeratedSet([1,2,3]) sage: S2 = Set([]) sage: cartesian_product([S1,ZZ]).is_empty() False sage: cartesian_product([S1,S2,S1]).is_empty() True """
def is_finite(self): r""" Return whether this set is finite.
EXAMPLES::
sage: E = FiniteEnumeratedSet([1,2,3]) sage: C = cartesian_product([E, SymmetricGroup(4)]) sage: C.is_finite() True
sage: cartesian_product([ZZ,ZZ]).is_finite() False sage: cartesian_product([ZZ, Set(), ZZ]).is_finite() True """ # Note: some parent might not implement "is_empty". So we # carefully isolate this test. except (AttributeError, NotImplementedError): pass else:
def cardinality(self): r""" Return the cardinality of self.
EXAMPLES::
sage: E = FiniteEnumeratedSet([1,2,3]) sage: C = cartesian_product([E,SymmetricGroup(4)]) sage: C.cardinality() 72
sage: E = FiniteEnumeratedSet([]) sage: C = cartesian_product([E, ZZ, QQ]) sage: C.cardinality() 0
sage: C = cartesian_product([ZZ, QQ]) sage: C.cardinality() +Infinity
sage: cartesian_product([GF(5), Permutations(10)]).cardinality() 18144000 sage: cartesian_product([GF(71)]*20).cardinality() == 71**20 True """
# Note: some parent might not implement "is_empty". So we # carefully isolate this test. else:
def random_element(self, *args): r""" Return a random element of this Cartesian product.
The extra arguments are passed down to each of the factors of the Cartesian product.
EXAMPLES::
sage: C = cartesian_product([Permutations(10)]*5) sage: C.random_element() # random ([2, 9, 4, 7, 1, 8, 6, 10, 5, 3], [8, 6, 5, 7, 1, 4, 9, 3, 10, 2], [5, 10, 3, 8, 2, 9, 1, 4, 7, 6], [9, 6, 10, 3, 2, 1, 5, 8, 7, 4], [8, 5, 2, 9, 10, 3, 7, 1, 4, 6])
sage: C = cartesian_product([ZZ]*10) sage: c1 = C.random_element() sage: c1 # random (3, 1, 4, 1, 1, -3, 0, -4, -17, 2) sage: c2 = C.random_element(4,7) sage: c2 # random (6, 5, 6, 4, 5, 6, 6, 4, 5, 5) sage: all(4 <= i < 7 for i in c2) True """ c.random_element(*args) for c in self.cartesian_factors())
@abstract_method def _sets_keys(self): """ Return the indices of the Cartesian factors of ``self``.
EXAMPLES::
sage: cartesian_product([QQ, ZZ, ZZ])._sets_keys() {0, 1, 2} """
@abstract_method def cartesian_factors(self): """ Return the Cartesian factors of ``self``.
EXAMPLES::
sage: cartesian_product([QQ, ZZ, ZZ]).cartesian_factors() (Rational Field, Integer Ring, Integer Ring) """
@abstract_method def cartesian_projection(self, i): """ Return the natural projection onto the `i`-th Cartesian factor of ``self``.
INPUT:
- ``i`` -- the index of a Cartesian factor of ``self``
EXAMPLES::
sage: C = Sets().CartesianProducts().example(); C The Cartesian product of (Set of prime numbers (basic implementation), An example of an infinite enumerated set: the non negative integers, An example of a finite enumerated set: {1,2,3}) sage: x = C.an_element(); x (47, 42, 1) sage: pi = C.cartesian_projection(1) sage: pi(x) 42 """
@abstract_method def _cartesian_product_of_elements(self, elements): """ Return the Cartesian product of the given ``elements``.
This method should accept any iterable.
INPUT:
- ``elements`` -- an iterable (e.g. a tuple or a list) of elements of each Cartesian factor of ``self``
EXAMPLES::
sage: S1 = Sets().example() sage: S2 = InfiniteEnumeratedSets().example() sage: X = [S2, S1, S2] sage: C = cartesian_product(X) sage: C._cartesian_product_of_elements([S.an_element() for S in X]) (42, 47, 42) sage: C._cartesian_product_of_elements(S.an_element() for S in X) (42, 47, 42) """
class ElementMethods:
def cartesian_projection(self, i): """ Return the projection of ``self`` onto the `i`-th factor of the Cartesian product.
INPUT:
- ``i`` -- the index of a factor of the Cartesian product
EXAMPLES::
sage: F = CombinatorialFreeModule(ZZ, [4,5]); F.__custom_name = "F" sage: G = CombinatorialFreeModule(ZZ, [4,6]); G.__custom_name = "G" sage: S = cartesian_product([F, G]) sage: x = S.monomial((0,4)) + 2 * S.monomial((0,5)) + 3 * S.monomial((1,6)) sage: x.cartesian_projection(0) B[4] + 2*B[5] sage: x.cartesian_projection(1) 3*B[6] """
summand_projection = deprecated_function_alias(10963, cartesian_projection)
def cartesian_factors(self): """ Return the Cartesian factors of ``self``.
EXAMPLES::
sage: F = CombinatorialFreeModule(ZZ, [4,5]); F.__custom_name = "F" sage: G = CombinatorialFreeModule(ZZ, [4,6]); G.__custom_name = "G" sage: H = CombinatorialFreeModule(ZZ, [4,7]); H.__custom_name = "H" sage: S = cartesian_product([F, G, H]) sage: x = S.monomial((0,4)) + 2 * S.monomial((0,5)) + 3 * S.monomial((1,6)) + 4 * S.monomial((2,4)) + 5 * S.monomial((2,7)) sage: x.cartesian_factors() (B[4] + 2*B[5], 3*B[6], 4*B[4] + 5*B[7]) sage: [s.parent() for s in x.cartesian_factors()] [F, G, H] sage: S.zero().cartesian_factors() (0, 0, 0) sage: [s.parent() for s in S.zero().cartesian_factors()] [F, G, H] """ # TODO: optimize for i in self.parent()._sets_keys()) #return Family(self._sets.keys(), self.projection)
summand_split = deprecated_function_alias(10963, cartesian_factors)
class Algebras(AlgebrasCategory):
def extra_super_categories(self): """ EXAMPLES::
sage: Sets().Algebras(ZZ).super_categories() [Category of modules with basis over Integer Ring]
sage: Sets().Algebras(QQ).extra_super_categories() [Category of vector spaces with basis over Rational Field]
sage: Sets().example().algebra(ZZ).categories() [Category of set algebras over Integer Ring, Category of modules with basis over Integer Ring, ... Category of objects]
"""
class ParentMethods: def construction(self): r""" Return the functorial construction of ``self``.
EXAMPLES::
sage: A = GroupAlgebra(KleinFourGroup(), QQ) sage: A.construction() (GroupAlgebraFunctor, Rational Field) """
def _repr_(self): r""" Return the string representation of `self`.
EXAMPLES::
sage: A = Groups().example().algebra(QQ); A Algebra of General Linear Group of degree 4 over Rational Field over Rational Field sage: A._name = "foo" sage: A foo over Rational Field sage: A = KleinFourGroup().algebra(ZZ) sage: A Algebra of The Klein 4 group of order 4, as a permutation group over Integer Ring """ else: self.base_ring())
class WithRealizations(WithRealizationsCategory):
def extra_super_categories(self): """ A set with multiple realizations is a facade parent.
EXAMPLES::
sage: Sets().WithRealizations().extra_super_categories() [Category of facade sets] sage: Sets().WithRealizations().super_categories() [Category of facade sets] """
def example(self, base_ring = None, set = None): r""" Return an example of set with multiple realizations, as per :meth:`Category.example`.
EXAMPLES::
sage: Sets().WithRealizations().example() The subset algebra of {1, 2, 3} over Rational Field
sage: Sets().WithRealizations().example(ZZ, Set([1,2])) The subset algebra of {1, 2} over Integer Ring """
class ParentMethods:
def _test_with_realizations(self, **options): r""" Test that this parent with realizations is properly implemented.
INPUT:
- ``options`` -- any keyword arguments accepted by :meth:`_tester`
EXAMPLES::
sage: A = Sets().WithRealizations().example() sage: A._test_with_realizations()
See the documentation for :class:`TestSuite` for more information. """ # Could check that there are coerce maps between any two realizations
@lazy_attribute def _realizations(self): """ This lazily initializes the attribute ``_realizations`` the first time it is needed.
TESTS::
sage: class MyParent(Parent): ....: pass sage: P = MyParent(category = Sets().WithRealizations()) sage: P._realizations [] """
def _register_realization(self, realization): """ EXAMPLES::
sage: A = Sets().WithRealizations().example(QQ['x']); A The subset algebra of {1, 2, 3} over Univariate Polynomial Ring in x over Rational Field sage: class ANewRealizationOfA(CombinatorialFreeModule): ....: pass sage: category = A.Realizations() & Algebras(QQ[x]).WithBasis() sage: R = ANewRealizationOfA(A.base_ring(), A.F().basis().keys(), category = category) sage: R in A.realizations() # indirect doctest True
Note: the test above uses ``QQ[x]`` to not interfer with other tests. """
def inject_shorthands(self, shorthands=None, verbose=True): """ Import standard shorthands into the global namespace.
INPUT:
- ``shorthands`` -- a list (or iterable) of strings (default: ``self._shorthands``) or ``"all"`` (for ``self._shorthands_all``) - ``verbose`` -- boolean (default ``True``); whether to print the defined shorthands
EXAMPLES:
When computing with a set with multiple realizations, like :class:`SymmetricFunctions` or :class:`~sage.categories.examples.with_realizations.SubsetAlgebra`, it is convenient to define shorthands for the various realizations, but cumbersome to do it by hand::
sage: S = SymmetricFunctions(ZZ); S Symmetric Functions over Integer Ring sage: s = S.s(); s Symmetric Functions over Integer Ring in the Schur basis sage: e = S.e(); e Symmetric Functions over Integer Ring in the elementary basis
This method automatizes the process::
sage: S.inject_shorthands() Defining e as shorthand for Symmetric Functions over Integer Ring in the elementary basis Defining f as shorthand for Symmetric Functions over Integer Ring in the forgotten basis Defining h as shorthand for Symmetric Functions over Integer Ring in the homogeneous basis Defining m as shorthand for Symmetric Functions over Integer Ring in the monomial basis Defining p as shorthand for Symmetric Functions over Integer Ring in the powersum basis Defining s as shorthand for Symmetric Functions over Integer Ring in the Schur basis sage: s[1] + e[2] * p[1,1] + 2*h[3] + m[2,1] s[1] - 2*s[1, 1, 1] + s[1, 1, 1, 1] + s[2, 1] + 2*s[2, 1, 1] + s[2, 2] + 2*s[3] + s[3, 1]
sage: e Symmetric Functions over Integer Ring in the elementary basis sage: p Symmetric Functions over Integer Ring in the powersum basis sage: s Symmetric Functions over Integer Ring in the Schur basis
Sometimes, like for symmetric functions, one can request for all shorthands to be defined, including less common ones::
sage: S.inject_shorthands("all") Defining e as shorthand for Symmetric Functions over Integer Ring in the elementary basis Defining f as shorthand for Symmetric Functions over Integer Ring in the forgotten basis Defining h as shorthand for Symmetric Functions over Integer Ring in the homogeneous basis Defining ht as shorthand for Symmetric Functions over Integer Ring in the induced trivial character basis Defining m as shorthand for Symmetric Functions over Integer Ring in the monomial basis Defining o as shorthand for Symmetric Functions over Integer Ring in the orthogonal basis Defining p as shorthand for Symmetric Functions over Integer Ring in the powersum basis Defining s as shorthand for Symmetric Functions over Integer Ring in the Schur basis Defining sp as shorthand for Symmetric Functions over Integer Ring in the symplectic basis Defining st as shorthand for Symmetric Functions over Integer Ring in the irreducible symmetric group character basis Defining w as shorthand for Symmetric Functions over Integer Ring in the Witt basis
The messages can be silenced by setting ``verbose=False``::
sage: Q = QuasiSymmetricFunctions(ZZ) sage: Q.inject_shorthands(verbose=False)
sage: F[1,2,1] + 5*M[1,3] + F[2]^2 5*F[1, 1, 1, 1] - 5*F[1, 1, 2] - 3*F[1, 2, 1] + 6*F[1, 3] + 2*F[2, 2] + F[3, 1] + F[4]
sage: F Quasisymmetric functions over the Integer Ring in the Fundamental basis sage: M Quasisymmetric functions over the Integer Ring in the Monomial basis
One can also just import a subset of the shorthands::
sage: SQ = SymmetricFunctions(QQ) sage: SQ.inject_shorthands(['p', 's'], verbose=False) sage: p Symmetric Functions over Rational Field in the powersum basis sage: s Symmetric Functions over Rational Field in the Schur basis
Note that ``e`` is left unchanged::
sage: e Symmetric Functions over Integer Ring in the elementary basis
TESTS::
sage: e == S.e(), h == S.h(), m == S.m(), p == SQ.p(), s == SQ.s() (True, True, True, True, True) """ raise NotImplementedError("no shorthands defined for {}".format(self))
@abstract_method(optional=True) def a_realization(self): """ Return a realization of ``self``.
EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: A.a_realization() The subset algebra of {1, 2, 3} over Rational Field in the Fundamental basis """
def realizations(self): """ Return all the realizations of ``self`` that ``self`` is aware of.
EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: A.realizations() [The subset algebra of {1, 2, 3} over Rational Field in the Fundamental basis, The subset algebra of {1, 2, 3} over Rational Field in the In basis, The subset algebra of {1, 2, 3} over Rational Field in the Out basis]
.. NOTE::
Constructing a parent ``P`` in the category ``A.Realizations()`` automatically adds ``P`` to this list by calling ``A._register_realization(A)`` """
def facade_for(self): """ Return the parents ``self`` is a facade for, that is the realizations of ``self``
EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: A.facade_for() [The subset algebra of {1, 2, 3} over Rational Field in the Fundamental basis, The subset algebra of {1, 2, 3} over Rational Field in the In basis, The subset algebra of {1, 2, 3} over Rational Field in the Out basis]
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: f = A.F().an_element(); f F[{}] + 2*F[{1}] + 3*F[{2}] + F[{1, 2}] sage: i = A.In().an_element(); i In[{}] + 2*In[{1}] + 3*In[{2}] + In[{1, 2}] sage: o = A.Out().an_element(); o Out[{}] + 2*Out[{1}] + 3*Out[{2}] + Out[{1, 2}] sage: f in A, i in A, o in A (True, True, True) """
# Do we really want this feature? class Realizations(Category_realization_of_parent):
def super_categories(self): """ EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: A.Realizations().super_categories() [Category of realizations of sets] """
def _an_element_(self): """ Return an element of some realization of ``self``.
EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: A.an_element() # indirect doctest F[{}] + 2*F[{1}] + 3*F[{2}] + F[{1, 2}]
TESTS:
Check that we are consistent no matter which basis is created first::
sage: M = posets.BooleanLattice(4).moebius_algebra(QQ) sage: I = M.I() sage: M._an_element_() 2*E[0] + 2*E[1] + 3*E[2] """
# TODO: maybe this could be taken care of by Sets.Facade()? def __contains__(self, x): r""" Test whether ``x`` is in ``self``, that is if it is an element of some realization of ``self``.
EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: A.an_element() in A True sage: A.In().an_element() in A True sage: A.F().an_element() in A True sage: A.Out().an_element() in A True sage: 1 in A True sage: QQ['x'].an_element() in A False """ return any(x in realization for realization in self.realizations())
class Realizations(RealizationsCategory):
class ParentMethods:
def __init_extra__(self): """ Register ``self`` as a realization of ``self.realization_of``.
TESTS::
sage: A = Sets().WithRealizations().example() sage: A.realizations() # indirect doctest [The subset algebra of {1, 2, 3} over Rational Field in the Fundamental basis, The subset algebra of {1, 2, 3} over Rational Field in the In basis, The subset algebra of {1, 2, 3} over Rational Field in the Out basis] """
@cached_method def realization_of(self): """ Return the parent this is a realization of.
EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: In = A.In(); In The subset algebra of {1, 2, 3} over Rational Field in the In basis sage: In.realization_of() The subset algebra of {1, 2, 3} over Rational Field """
def _realization_name(self): """ Return the name of this realization.
In this default implementation, this is guessed from the name of its class.
EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: In = A.In(); In The subset algebra of {1, 2, 3} over Rational Field in the In basis sage: In._realization_name() 'In' """ # The __base__ gets rid of the with_category # The split adds support for nested classes
def _repr_(self): """ EXAMPLES::
sage: A = Sets().WithRealizations().example(); A The subset algebra of {1, 2, 3} over Rational Field sage: In = A.In(); In The subset algebra of {1, 2, 3} over Rational Field in the In basis
In the example above, :meth:`repr` was overriden by the category ``A.Realizations()``. We now add a new (fake) realization which is not in ``A.Realizations()`` to actually exercise this method::
sage: from sage.categories.realizations import Realizations sage: class Blah(Parent): ....: pass sage: P = Blah(category = Sets.WithRealizations.ParentMethods.Realizations(A)) sage: P # indirect doctest The subset algebra of {1, 2, 3} over Rational Field in the realization Blah """
# Moved from sage.categories.cartesian_product to avoid circular import errors cartesian_product = CartesianProductFunctor() |