Monday, January 21, 2013

Monoid action

Given a set $S$ of elements the monoid action on that set is defined by a collection of functions $S \to S$ that are closed under iteration and composition. Places form their own monoid actions on a set because there is a set of endofunctions that we can apply to a place using the zap function that is closed under composition and that includes the identity which doesn't effect that place at all.

Every single place on a set has $n^n$ transformations of the place where $n$ is the size of the place. The full transformation monoid on a set is defined by the operations on the top level place of the set and the trivial monoid is the set of transformations on the empty place.

It is often useful to use group actions on a set rather then monoid actions because the group actions partition the set into a set of orbits. This can be used to enumerate all the group actions on a set which is an invaluable technique in numerous combinatorial problems. We can use this to enumerate permutations, multiset permutations, permutations of a certain cycle type, equivalence relations, and many other combinatorial structures.

No comments:

Post a Comment