Ask Your Question

submonoids of the monoid of all maps from one set to itself.

asked 2022-01-25 17:54:06 +0200

Dmitry2321 gravatar image

Sorry for my bad english.

I have all maps from {1,2,3} to {1,2,3}. So I have 27 maps. And it is monoid, with * as superposition and e as map (1->1,2->2,3->3).

  1. M = FiniteSetMaps([1, 2, 3])
  2. print(M.category())
  3. print(M.an_element())
  4. print(M.cardinality())

Output: Category of finite enumerated monoids; map: 1 -> 4, 2 -> 2, 4 -> 1; 27 How can I list all submonoids of that monoid ? (I know there are 699)

edit retag flag offensive close merge delete


Btw, where did you get number 699? Do you have similar counts for sets of size 4 and up?

Max Alekseyev gravatar imageMax Alekseyev ( 2022-01-26 15:18:02 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2022-01-26 01:02:23 +0200

Max Alekseyev gravatar image

updated 2022-01-26 03:39:02 +0200

(Sub)monoids seem to be quite poorly implemented. Not only a method for generating all submonoids is missing, their elements can hardly be compared. For example:

M = FiniteSetMaps([1, 2, 3])
e =
M1 = M.subsemigroup([M[0],M[1]], one=e, category=Monoids().Finite().Subobjects())
M2 = M.subsemigroup([M[1],M[0]], one=e, category=Monoids().Finite().Subobjects())

Here we create two submonoids with the same generators (given in different order). However, while both M1[0] and M2[0] are essentially e, comparisons like M1[0] == M2[0] and M2(M1[0]) == M2[0] give False. I was able to detect their equality only via conversion to strings.

So, unless there is a better alternative, here is a code that goes over all subsets of elements of M, creates submonoids generated by them, and stores them as sets of strings (for comparison purposes).

M = FiniteSetMaps([1, 2, 3])
e =
result = set()
for S in Subsets( set(M.list()) - {e} ):
    submonoid = M.subsemigroup(S, one=e, category=Monoids().Finite().Subobjects())
    submonoid_set = frozenset( map(str, submonoid.list()) )       # as a frozen set
    if submonoid_set not in result:
        result.add( submonoid_set )
        print(len(result),':\t', submonoid.list() )  # print each newly seen submonoid

Notice that it may take a few hours/days to complete executions. However, getting 699 submonoids takes just a couple of minutes. If that's the number, you can break execution after reaching it.

edit flag offensive delete link more


Many thanks. I got the idea. I was afraid that I missed "a method for generating all submonoids" in Sage documentation. Thanks again. I got an answer to my question

Dmitry2321 gravatar imageDmitry2321 ( 2022-01-26 10:38:12 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2022-01-25 16:34:35 +0200

Seen: 29 times

Last updated: Jan 26