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?

  • $\begingroup$ You could write $\{ f \circ g \mid f,g \in F \}$. $\endgroup$ May 15 '19 at 16:28
  • $\begingroup$ I forgot to mention that I'm looking for a general notation. My example was to simplify the example permutation set but the cardinality of $F$ is undefined and may be arbitrarily large. $\endgroup$
    – Shiri
    May 15 '19 at 16:32
  • $\begingroup$ So you don't allow $a \circ a \circ a$ in your set? $\endgroup$ May 15 '19 at 16:38
  • $\begingroup$ @JairTaylor My mistake I was initially thinking of a fixed sample size of $|F|$ but yes I do allow $a \circ a \circ a$ $\endgroup$
    – Shiri
    May 17 '19 at 10:44

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.

  • $\begingroup$ It's even a monoid, since we have the identity arrow. Oh, my. It's a category. $\endgroup$ May 15 '19 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.