Monoids#

class sage.categories.monoids.Monoids(base_category)[source]#

Bases: CategoryWithAxiom_singleton

The category of (multiplicative) monoids.

A monoid is a unital semigroup, that is a set endowed with a multiplicative binary operation \(*\) which is associative and admits a unit (see Wikipedia article Monoid).

EXAMPLES:

Sage

sage: Monoids()
Category of monoids
sage: Monoids().super_categories()
[Category of semigroups, Category of unital magmas]
sage: Monoids().all_super_categories()
[Category of monoids,
 Category of semigroups,
 Category of unital magmas, Category of magmas,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]

sage: Monoids().axioms()
frozenset({'Associative', 'Unital'})
sage: Semigroups().Unital()
Category of monoids

sage: Monoids().example()
An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd')

Python

>>> from sage.all import *
>>> Monoids()
Category of monoids
>>> Monoids().super_categories()
[Category of semigroups, Category of unital magmas]
>>> Monoids().all_super_categories()
[Category of monoids,
 Category of semigroups,
 Category of unital magmas, Category of magmas,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]

>>> Monoids().axioms()
frozenset({'Associative', 'Unital'})
>>> Semigroups().Unital()
Category of monoids

>>> Monoids().example()
An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd')

class Algebras(category, *args)[source]#

Bases: AlgebrasCategory

class ElementMethods[source]#

Bases: object

is_central()[source]#

Return whether the element self is central.

EXAMPLES:

Sage

sage: SG4 = SymmetricGroupAlgebra(ZZ,4)                             # needs sage.groups sage.modules
sage: SG4(1).is_central()                                           # needs sage.groups sage.modules
True
sage: SG4(Permutation([1,3,2,4])).is_central()                      # needs sage.groups sage.modules
False

sage: A = GroupAlgebras(QQ).example(); A                            # needs sage.groups sage.modules
Algebra of Dihedral group of order 8
 as a permutation group over Rational Field
sage: sum(A.basis()).is_central()                                   # needs sage.groups sage.modules
True

Python

>>> from sage.all import *
>>> SG4 = SymmetricGroupAlgebra(ZZ,Integer(4))                             # needs sage.groups sage.modules
>>> SG4(Integer(1)).is_central()                                           # needs sage.groups sage.modules
True
>>> SG4(Permutation([Integer(1),Integer(3),Integer(2),Integer(4)])).is_central()                      # needs sage.groups sage.modules
False

>>> A = GroupAlgebras(QQ).example(); A                            # needs sage.groups sage.modules
Algebra of Dihedral group of order 8
 as a permutation group over Rational Field
>>> sum(A.basis()).is_central()                                   # needs sage.groups sage.modules
True

class ParentMethods[source]#

Bases: object

algebra_generators()[source]#

Return generators for this algebra.

For a monoid algebra, the algebra generators are built from the monoid generators if available and from the semigroup generators otherwise.

See also

EXAMPLES:

Sage

sage: M = Monoids().example(); M
An example of a monoid:
the free monoid generated by ('a', 'b', 'c', 'd')
sage: M.monoid_generators()
Finite family {'a': 'a', 'b': 'b', 'c': 'c', 'd': 'd'}
sage: M.algebra(ZZ).algebra_generators()                            # needs sage.modules
Finite family {'a': B['a'], 'b': B['b'], 'c': B['c'], 'd': B['d']}

sage: Z12 = Monoids().Finite().example(); Z12
An example of a finite multiplicative monoid:
the integers modulo 12
sage: Z12.monoid_generators()
Traceback (most recent call last):
...
AttributeError: 'IntegerModMonoid_with_category' object
has no attribute 'monoid_generators'...
sage: Z12.semigroup_generators()
Family (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
sage: Z12.algebra(QQ).algebra_generators()                          # needs sage.modules
Family (B[0], B[1], B[2], B[3], B[4], B[5], B[6], B[7], B[8], B[9], B[10], B[11])


sage: A10 = AlternatingGroup(10)                                    # needs sage.groups
sage: GroupAlgebras(QQ).example(A10).algebra_generators()           # needs sage.groups sage.modules
Family ((1,2,3,4,5,6,7,8,9), (8,9,10))

sage: A = DihedralGroup(3).algebra(QQ); A                           # needs sage.groups sage.modules
Algebra of Dihedral group of order 6 as a permutation group
 over Rational Field
sage: A.algebra_generators()                                        # needs sage.groups sage.modules
Family ((1,2,3), (1,3))

Python

>>> from sage.all import *
>>> M = Monoids().example(); M
An example of a monoid:
the free monoid generated by ('a', 'b', 'c', 'd')
>>> M.monoid_generators()
Finite family {'a': 'a', 'b': 'b', 'c': 'c', 'd': 'd'}
>>> M.algebra(ZZ).algebra_generators()                            # needs sage.modules
Finite family {'a': B['a'], 'b': B['b'], 'c': B['c'], 'd': B['d']}

>>> Z12 = Monoids().Finite().example(); Z12
An example of a finite multiplicative monoid:
the integers modulo 12
>>> Z12.monoid_generators()
Traceback (most recent call last):
...
AttributeError: 'IntegerModMonoid_with_category' object
has no attribute 'monoid_generators'...
>>> Z12.semigroup_generators()
Family (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
>>> Z12.algebra(QQ).algebra_generators()                          # needs sage.modules
Family (B[0], B[1], B[2], B[3], B[4], B[5], B[6], B[7], B[8], B[9], B[10], B[11])


>>> A10 = AlternatingGroup(Integer(10))                                    # needs sage.groups
>>> GroupAlgebras(QQ).example(A10).algebra_generators()           # needs sage.groups sage.modules
Family ((1,2,3,4,5,6,7,8,9), (8,9,10))

>>> A = DihedralGroup(Integer(3)).algebra(QQ); A                           # needs sage.groups sage.modules
Algebra of Dihedral group of order 6 as a permutation group
 over Rational Field
>>> A.algebra_generators()                                        # needs sage.groups sage.modules
Family ((1,2,3), (1,3))

one_basis()[source]#

Return the unit of the monoid, which indexes the unit of this algebra, as per AlgebrasWithBasis.ParentMethods.one_basis().

EXAMPLES:

Sage

sage: # needs sage.modules
sage: A = Monoids().example().algebra(ZZ)
sage: A.one_basis()
''
sage: A.one()
B['']
sage: A(3)
3*B['']

Python

>>> from sage.all import *
>>> # needs sage.modules
>>> A = Monoids().example().algebra(ZZ)
>>> A.one_basis()
''
>>> A.one()
B['']
>>> A(Integer(3))
3*B['']

extra_super_categories()[source]#

The algebra of a monoid is a bialgebra and a monoid.

EXAMPLES:

Sage

sage: C = Monoids().Algebras(QQ)
sage: C.extra_super_categories()
[Category of bialgebras over Rational Field,
 Category of monoids]
sage: Monoids().Algebras(QQ).super_categories()
[Category of bialgebras with basis over Rational Field,
 Category of semigroup algebras over Rational Field,
 Category of unital magma algebras over Rational Field]

Python

>>> from sage.all import *
>>> C = Monoids().Algebras(QQ)
>>> C.extra_super_categories()
[Category of bialgebras over Rational Field,
 Category of monoids]
>>> Monoids().Algebras(QQ).super_categories()
[Category of bialgebras with basis over Rational Field,
 Category of semigroup algebras over Rational Field,
 Category of unital magma algebras over Rational Field]

class CartesianProducts(category, *args)[source]#

Bases: CartesianProductsCategory

The category of monoids constructed as Cartesian products of monoids.

This construction gives the direct product of monoids. See Wikipedia article Direct_product for more information.

class ElementMethods[source]#

Bases: object

multiplicative_order()[source]#

Return the multiplicative order of this element.

EXAMPLES:

Sage

sage: # needs sage.groups sage.modules
sage: G1 = SymmetricGroup(3)
sage: G2 = SL(2, 3)
sage: G = cartesian_product([G1, G2])
sage: G((G1.gen(0), G2.gen(1))).multiplicative_order()
12

Python

>>> from sage.all import *
>>> # needs sage.groups sage.modules
>>> G1 = SymmetricGroup(Integer(3))
>>> G2 = SL(Integer(2), Integer(3))
>>> G = cartesian_product([G1, G2])
>>> G((G1.gen(Integer(0)), G2.gen(Integer(1)))).multiplicative_order()
12

class ParentMethods[source]#

Bases: object

monoid_generators()[source]#

Return the generators of self.

EXAMPLES:

Sage

sage: # needs sage.combinat sage.groups
sage: M = Monoids.free([1, 2, 3])
sage: N = Monoids.free(['a', 'b'])
sage: C = cartesian_product([M, N])
sage: C.monoid_generators()
Family ((F[1], 1), (F[2], 1), (F[3], 1),
        (1, F['a']), (1, F['b']))

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.groups
>>> M = Monoids.free([Integer(1), Integer(2), Integer(3)])
>>> N = Monoids.free(['a', 'b'])
>>> C = cartesian_product([M, N])
>>> C.monoid_generators()
Family ((F[1], 1), (F[2], 1), (F[3], 1),
        (1, F['a']), (1, F['b']))

An example with an infinitely generated group (a better output is needed):

Sage

sage: N = Monoids.free(ZZ)                                          # needs sage.combinat
sage: C = cartesian_product([M, N])                                 # needs sage.combinat sage.groups
sage: C.monoid_generators()                                         # needs sage.combinat sage.groups
Lazy family (gen(i))_{i in The Cartesian product of (...)}

Python

>>> from sage.all import *
>>> N = Monoids.free(ZZ)                                          # needs sage.combinat
>>> C = cartesian_product([M, N])                                 # needs sage.combinat sage.groups
>>> C.monoid_generators()                                         # needs sage.combinat sage.groups
Lazy family (gen(i))_{i in The Cartesian product of (...)}

extra_super_categories()[source]#

A Cartesian product of monoids is endowed with a natural group structure.

EXAMPLES:

Sage

sage: C = Monoids().CartesianProducts()
sage: C.extra_super_categories()
[Category of monoids]
sage: sorted(C.super_categories(), key=str)
[Category of Cartesian products of semigroups,
 Category of Cartesian products of unital magmas,
 Category of monoids]

Python

>>> from sage.all import *
>>> C = Monoids().CartesianProducts()
>>> C.extra_super_categories()
[Category of monoids]
>>> sorted(C.super_categories(), key=str)
[Category of Cartesian products of semigroups,
 Category of Cartesian products of unital magmas,
 Category of monoids]

class Commutative(base_category)[source]#

Bases: CategoryWithAxiom_singleton

Category of commutative (abelian) monoids.

A monoid \(M\) is commutative if \(xy = yx\) for all \(x,y \in M\).

static free(index_set=None, names=None, **kwds)[source]#

Return a free abelian monoid on \(n\) generators or with the generators indexed by a set \(I\).

A free monoid is constructed by specifying either:

the number of generators and/or the names of the generators, or
the indexing set for the generators.

INPUT:

index_set – (optional) an index set for the generators; if an integer, then this represents \(\{0, 1, \ldots, n-1\}\)
names – a string or list/tuple/iterable of strings (default: 'x'); the generator names or name prefix

EXAMPLES:

Sage

sage: Monoids.Commutative.free(index_set=ZZ)                            # needs sage.combinat
Free abelian monoid indexed by Integer Ring
sage: Monoids().Commutative().free(ZZ)                                  # needs sage.combinat
Free abelian monoid indexed by Integer Ring
sage: F.<x,y,z> = Monoids().Commutative().free(); F                     # needs sage.combinat
Free abelian monoid indexed by {'x', 'y', 'z'}

Python

>>> from sage.all import *
>>> Monoids.Commutative.free(index_set=ZZ)                            # needs sage.combinat
Free abelian monoid indexed by Integer Ring
>>> Monoids().Commutative().free(ZZ)                                  # needs sage.combinat
Free abelian monoid indexed by Integer Ring
>>> F = Monoids().Commutative().free(names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3); F                     # needs sage.combinat
Free abelian monoid indexed by {'x', 'y', 'z'}

class ElementMethods[source]#

Bases: object

inverse()[source]#

Return the multiplicative inverse of self.

This is an alias for inversion, which can also be invoked by ~x for an element x.

Nota Bene: Element classes should implement __invert__ only.

EXAMPLES:

Sage

sage: AA(sqrt(~2)).inverse()                                            # needs sage.rings.number_field sage.symbolic
1.414213562373095?

Python

>>> from sage.all import *
>>> AA(sqrt(~Integer(2))).inverse()                                            # needs sage.rings.number_field sage.symbolic
1.414213562373095?

is_one()[source]#

Return whether self is the one of the monoid.

The default implementation is to compare with self.one().

powers(n)[source]#

Return the list \([x^0, x^1, \ldots, x^{n-1}]\).

EXAMPLES:

Sage

sage: A = Matrix([[1, 1], [-1, 0]])                                     # needs sage.modules
sage: A.powers(6)                                                       # needs sage.modules
[
[1 0]  [ 1  1]  [ 0  1]  [-1  0]  [-1 -1]  [ 0 -1]
[0 1], [-1  0], [-1 -1], [ 0 -1], [ 1  0], [ 1  1]
]

Python

>>> from sage.all import *
>>> A = Matrix([[Integer(1), Integer(1)], [-Integer(1), Integer(0)]])                                     # needs sage.modules
>>> A.powers(Integer(6))                                                       # needs sage.modules
[
[1 0]  [ 1  1]  [ 0  1]  [-1  0]  [-1 -1]  [ 0 -1]
[0 1], [-1  0], [-1 -1], [ 0 -1], [ 1  0], [ 1  1]
]

Finite[source]#: alias of FiniteMonoids

Inverse[source]#: alias of Groups

class ParentMethods[source]#

Bases: object

prod(args)[source]#

n-ary product of elements of self.

INPUT:

args – a list (or iterable) of elements of self

Returns the product of the elements in args, as an element of self.

EXAMPLES:

Sage

sage: S = Monoids().example()
sage: S.prod([S('a'), S('b')])
'ab'

Python

>>> from sage.all import *
>>> S = Monoids().example()
>>> S.prod([S('a'), S('b')])
'ab'

semigroup_generators()[source]#

Return the generators of self as a semigroup.

The generators of a monoid \(M\) as a semigroup are the generators of \(M\) as a monoid and the unit.

EXAMPLES:

Sage

sage: M = Monoids().free([1,2,3])                                       # needs sage.combinat
sage: M.semigroup_generators()                                          # needs sage.combinat
Family (1, F[1], F[2], F[3])

Python

>>> from sage.all import *
>>> M = Monoids().free([Integer(1),Integer(2),Integer(3)])                                       # needs sage.combinat
>>> M.semigroup_generators()                                          # needs sage.combinat
Family (1, F[1], F[2], F[3])

submonoid(generators, category=None)[source]#

Return the multiplicative submonoid generated by generators.

INPUT:

generators – a finite family of elements of self, or a list, iterable, … that can be converted into one (see Family).
category – a category

This is a shorthand for Semigroups.ParentMethods.subsemigroup() that specifies that this is a submonoid, and in particular that the unit is self.one().

EXAMPLES:

Sage

sage: R = IntegerModRing(15)
sage: M = R.submonoid([R(3), R(5)]); M                                  # needs sage.combinat
A submonoid of (Ring of integers modulo 15) with 2 generators
sage: M.list()                                                          # needs sage.combinat
[1, 3, 5, 9, 0, 10, 12, 6]

Python

>>> from sage.all import *
>>> R = IntegerModRing(Integer(15))
>>> M = R.submonoid([R(Integer(3)), R(Integer(5))]); M                                  # needs sage.combinat
A submonoid of (Ring of integers modulo 15) with 2 generators
>>> M.list()                                                          # needs sage.combinat
[1, 3, 5, 9, 0, 10, 12, 6]

Not the presence of the unit, unlike in:

Sage

sage: S = R.subsemigroup([R(3), R(5)]); S                               # needs sage.combinat
A subsemigroup of (Ring of integers modulo 15) with 2 generators
sage: S.list()                                                          # needs sage.combinat
[3, 5, 9, 0, 10, 12, 6]

Python

>>> from sage.all import *
>>> S = R.subsemigroup([R(Integer(3)), R(Integer(5))]); S                               # needs sage.combinat
A subsemigroup of (Ring of integers modulo 15) with 2 generators
>>> S.list()                                                          # needs sage.combinat
[3, 5, 9, 0, 10, 12, 6]

This method is really a shorthand for subsemigroup:

Sage

sage: M2 = R.subsemigroup([R(3), R(5)], one=R.one())                    # needs sage.combinat
sage: M2 is M                                                           # needs sage.combinat
True

Python

>>> from sage.all import *
>>> M2 = R.subsemigroup([R(Integer(3)), R(Integer(5))], one=R.one())                    # needs sage.combinat
>>> M2 is M                                                           # needs sage.combinat
True

class Subquotients(category, *args)[source]#

Bases: SubquotientsCategory

class ParentMethods[source]#

Bases: object

one()[source]#

Returns the multiplicative unit of this monoid, obtained by retracting that of the ambient monoid.

EXAMPLES:

Sage

sage: S = Monoids().Subquotients().example() # todo: not implemented
sage: S.one()                                # todo: not implemented

Python

>>> from sage.all import *
>>> S = Monoids().Subquotients().example() # todo: not implemented
>>> S.one()                                # todo: not implemented

class WithRealizations(category, *args)[source]#

Bases: WithRealizationsCategory

class ParentMethods[source]#

Bases: object

one()[source]#

Return the unit of this monoid.

This default implementation returns the unit of the realization of self given by a_realization().

EXAMPLES:

Sage

sage: A = Sets().WithRealizations().example(); A                    # needs sage.modules
The subset algebra of {1, 2, 3} over Rational Field
sage: A.one.__module__                                              # needs sage.modules
'sage.categories.monoids'
sage: A.one()                                                       # needs sage.modules
F[{}]

Python

>>> from sage.all import *
>>> A = Sets().WithRealizations().example(); A                    # needs sage.modules
The subset algebra of {1, 2, 3} over Rational Field
>>> A.one.__module__                                              # needs sage.modules
'sage.categories.monoids'
>>> A.one()                                                       # needs sage.modules
F[{}]

static free(index_set=None, names=None, **kwds)[source]#

Return a free monoid on \(n\) generators or with the generators indexed by a set \(I\).

A free monoid is constructed by specifying either:

the number of generators and/or the names of the generators
the indexing set for the generators

INPUT:

index_set – (optional) an index set for the generators; if an integer, then this represents \(\{0, 1, \ldots, n-1\}\)
names – a string or list/tuple/iterable of strings (default: 'x'); the generator names or name prefix

EXAMPLES:

Sage

sage: Monoids.free(index_set=ZZ)                                            # needs sage.combinat
Free monoid indexed by Integer Ring
sage: Monoids().free(ZZ)                                                    # needs sage.combinat
Free monoid indexed by Integer Ring
sage: F.<x,y,z> = Monoids().free(); F                                       # needs sage.combinat
Free monoid indexed by {'x', 'y', 'z'}

Python

>>> from sage.all import *
>>> Monoids.free(index_set=ZZ)                                            # needs sage.combinat
Free monoid indexed by Integer Ring
>>> Monoids().free(ZZ)                                                    # needs sage.combinat
Free monoid indexed by Integer Ring
>>> F = Monoids().free(names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3); F                                       # needs sage.combinat
Free monoid indexed by {'x', 'y', 'z'}