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

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 close merge delete

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

( 2022-01-26 15:18:02 +0200 )edit

Sort by » oldest newest most voted

(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 = M.one()
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 = M.one()
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:
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.

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

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