Maps between finite sets

This module implements parents modeling the set of all maps between two finite sets. At the user level, any such parent should be constructed using the factory class FiniteSetMaps which properly selects which of its subclasses to use.

AUTHORS:

  • Florent Hivert

class sage.sets.finite_set_maps.FiniteSetEndoMaps_N(n, action, category=None)

Bases: sage.sets.finite_set_maps.FiniteSetMaps_MN

The sets of all maps from \(\{1, 2, \dots, n\}\) to itself

Users should use the factory class FiniteSetMaps to create instances of this class.

INPUT:

  • n – an integer.

  • category – the category in which the sets of maps is constructed. It must be a sub-category of Monoids().Finite() and EnumeratedSets().Finite() which is the default value.

Element

alias of sage.sets.finite_set_map_cy.FiniteSetEndoMap_N

an_element()

Returns a map in self

EXAMPLES:

sage: M = FiniteSetMaps(4)
sage: M.an_element()
[3, 2, 1, 0]
one()

EXAMPLES:

sage: M = FiniteSetMaps(4)
sage: M.one()
[0, 1, 2, 3]
class sage.sets.finite_set_maps.FiniteSetEndoMaps_Set(domain, action, category=None)

Bases: sage.sets.finite_set_maps.FiniteSetMaps_Set, sage.sets.finite_set_maps.FiniteSetEndoMaps_N

The sets of all maps from a set to itself

Users should use the factory class FiniteSetMaps to create instances of this class.

INPUT:

  • domain – an object in the category FiniteSets().

  • category – the category in which the sets of maps is constructed. It must be a sub-category of Monoids().Finite() and EnumeratedSets().Finite() which is the default value.

Element

alias of sage.sets.finite_set_map_cy.FiniteSetEndoMap_Set

class sage.sets.finite_set_maps.FiniteSetMaps

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

Maps between finite sets

Constructs the set of all maps between two sets. The sets can be given using any of the three following ways:

  1. an object in the category Sets().

  2. a finite iterable. In this case, an object of the class FiniteEnumeratedSet is constructed from the iterable.

  3. an integer n designing the set \(\{0, 1, \dots, n-1\}\). In this case an object of the class IntegerRange is constructed.

INPUT:

  • domain – a set, finite iterable, or integer.

  • codomain – a set, finite iterable, integer, or None (default). In this last case, the maps are endo-maps of the domain.

  • action – "left" (default) or "right". The side where the maps act on the domain. This is used in particular to define the meaning of the product (composition) of two maps.

  • category – the category in which the sets of maps is constructed. By default, this is FiniteMonoids() if the domain and codomain coincide, and FiniteEnumeratedSets() otherwise.

OUTPUT:

an instance of a subclass of FiniteSetMaps modeling the set of all maps between domain and codomain.

EXAMPLES:

We construct the set M of all maps from \(\{a,b\}\) to \(\{3,4,5\}\):

sage: M = FiniteSetMaps(["a", "b"], [3, 4, 5]); M
Maps from {'a', 'b'} to {3, 4, 5}
sage: M.cardinality()
9
sage: M.domain()
{'a', 'b'}
sage: M.codomain()
{3, 4, 5}
sage: for f in M: print(f)
map: a -> 3, b -> 3
map: a -> 3, b -> 4
map: a -> 3, b -> 5
map: a -> 4, b -> 3
map: a -> 4, b -> 4
map: a -> 4, b -> 5
map: a -> 5, b -> 3
map: a -> 5, b -> 4
map: a -> 5, b -> 5

Elements can be constructed from functions and dictionaries:

sage: M(lambda c: ord(c)-94)
map: a -> 3, b -> 4

sage: M.from_dict({'a':3, 'b':5})
map: a -> 3, b -> 5

If the domain is equal to the codomain, then maps can be composed:

sage: M = FiniteSetMaps([1, 2, 3])
sage: f = M.from_dict({1:2, 2:1, 3:3}); f
map: 1 -> 2, 2 -> 1, 3 -> 3
sage: g = M.from_dict({1:2, 2:3, 3:1}); g
map: 1 -> 2, 2 -> 3, 3 -> 1

sage: f * g
map: 1 -> 1, 2 -> 3, 3 -> 2

This makes \(M\) into a monoid:

sage: M.category()
Category of finite enumerated monoids
sage: M.one()
map: 1 -> 1, 2 -> 2, 3 -> 3

By default, composition is from right to left, which corresponds to an action on the left. If one specifies action to right, then the composition is from left to right:

sage: M = FiniteSetMaps([1, 2, 3], action = 'right')
sage: f = M.from_dict({1:2, 2:1, 3:3})
sage: g = M.from_dict({1:2, 2:3, 3:1})
sage: f * g
map: 1 -> 3, 2 -> 2, 3 -> 1

If the domains and codomains are both of the form \(\{0,\dots\}\), then one can use the shortcut:

sage: M = FiniteSetMaps(2,3); M
Maps from {0, 1} to {0, 1, 2}
sage: M.cardinality()
9

For a compact notation, the elements are then printed as lists \([f(i), i=0,\dots]\):

sage: list(M)
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
cardinality()

The cardinality of self

EXAMPLES:

sage: FiniteSetMaps(4, 3).cardinality()
81
class sage.sets.finite_set_maps.FiniteSetMaps_MN(m, n, category=None)

Bases: sage.sets.finite_set_maps.FiniteSetMaps

The set of all maps from \(\{1, 2, \dots, m\}\) to \(\{1, 2, \dots, n\}\).

Users should use the factory class FiniteSetMaps to create instances of this class.

INPUT:

  • m, n – integers

  • category – the category in which the sets of maps is constructed. It must be a sub-category of EnumeratedSets().Finite() which is the default value.

Element

alias of sage.sets.finite_set_map_cy.FiniteSetMap_MN

an_element()

Returns a map in self

EXAMPLES:

sage: M = FiniteSetMaps(4, 2)
sage: M.an_element()
[0, 0, 0, 0]

sage: M = FiniteSetMaps(0, 0)
sage: M.an_element()
[]

An exception EmptySetError is raised if this set is empty, that is if the codomain is empty and the domain is not.

sage: M = FiniteSetMaps(4, 0) sage: M.cardinality() 0 sage: M.an_element() Traceback (most recent call last): … EmptySetError

codomain()

The codomain of self

EXAMPLES:

sage: FiniteSetMaps(3,2).codomain()
{0, 1}
domain()

The domain of self

EXAMPLES:

sage: FiniteSetMaps(3,2).domain()
{0, 1, 2}
class sage.sets.finite_set_maps.FiniteSetMaps_Set(domain, codomain, category=None)

Bases: sage.sets.finite_set_maps.FiniteSetMaps_MN

The sets of all maps between two sets

Users should use the factory class FiniteSetMaps to create instances of this class.

INPUT:

  • domain – an object in the category FiniteSets().

  • codomain – an object in the category FiniteSets().

  • category – the category in which the sets of maps is constructed. It must be a sub-category of EnumeratedSets().Finite() which is the default value.

Element

alias of sage.sets.finite_set_map_cy.FiniteSetMap_Set

codomain()

The codomain of self

EXAMPLES:

sage: FiniteSetMaps(["a", "b"], [3, 4, 5]).codomain()
{3, 4, 5}
domain()

The domain of self

EXAMPLES:

sage: FiniteSetMaps(["a", "b"], [3, 4, 5]).domain()
{'a', 'b'}
from_dict(d)

Create a map from a dictionary

EXAMPLES:

sage: M = FiniteSetMaps(["a", "b"], [3, 4, 5])
sage: M.from_dict({"a": 4, "b": 3})
map: a -> 4, b -> 3