Notation for permutations of function composition

63 Views Asked by At

Given a set of functions $F$ of which all are functions in $X \to X$, where certain functions, say $a, b \in F$ can be composed together: $a(b(x)) = (a \circ b)(x)$. What is the notation for the set of all possible permutations of compositions of functions in $F$?

For example, say $F = \{a, b\}$ where $a, b : X \to X$, all the possible permutations of compositions of functions in $F$ are:

$(a \circ a)(x)$

$(a \circ b)(x)$

$(b \circ a)(x)$

$(b \circ b)(x)$

How would the set of the above be expressed in terms of $F$ in general? Should I not be expressing these functions as a set?

1

There are 1 best solutions below

1
On

Note, you haven't provided all possible compositions, since there's also $aba$ and $abaaabbbaba$. Confusingly, the mathematical literature calls these "words".

You could use the Kleene star notation (in your case, $F^*$ ) to describe all possible words you can make, and interpret the words as compositions.

By the way, since function composition is associative, this structure forms a semigroup.