monoids of injections and surjections

Question

Let $X$ be an infinite set, and let $I(X)$ and $S(X)$ denote the monoids of injective and surjective maps from $X$ to itself, respectively. How do $I(X)$ and $S(X)$ relate algebraically? Is there any reason to suspect that they may be isomorphic aside from optimism?

Answer 1

$ \newcommand{\tuple}[1]{\left\langle#1\right\rangle} \newcommand{idX}{\operatorname{id}_X} % $The monoids $$\tuple{I(X),\circ,\idX} \text{ and }\tuple{S(X),\circ,\idX}$$ are not isomorphic and neither are $$\tuple{I(X),\circ,\idX} \text{ and }\tuple{S(X),\bullet,\idX},$$ where $f\bullet g = x \mapsto g(f(x))$ is the inverted composition (sometimes denoted by a semicolon like $f{;}g$).

To simplify notation, fix some set $X$, so that $I = I(X)$ and $S = S(X)$, and let assume that there exists isomorphism $\Phi : I \to S$ between them.

Let $B = B(X)$ be the set of all the bijections $X \to X$. Moreover, let \begin{align} B_I &= \{f \in I \mid \exists g \in I.\ g\circ f = \idX \land f\circ g = \idX\} \\ B_S &= \{f \in S \mid \exists g \in S.\ g\circ f = \idX \land f\circ g = \idX\} \end{align}

Surely elements of $B$ have inverses, so $B \subset B_S \subset S$ and $B \subset B_I \subset I$, but we also have that each element of $B_S$ and $B_I$ is a bijection, so $B_I = B = B_S$. Please note that $B$ is a group, so we have four $G$-sets:

• left action for $I$, that is, $\lambda_I : B \times I \to I$,
• right action for $I$, that is, $\rho_I : I \times B \to I$,
• left action for $S$, that is, $\lambda_S : B \times S \to S$,
• right action for $S$, that is, $\rho_S : S \times B \to S$.

Observe that, $$\Phi(\idX) = \idX,$$ so $f\circ g = \idX$ implies that $\Phi(f)\circ\Phi(g) = \idX$, hence $\Phi(B) = B$, which means that $\Phi|_B$ is an automorphism of $B$. That also means that $\Phi(I \setminus B) = S \setminus B$. Now $\Phi$ doesn't have to be an isomorphism between the above $G$-sets, but it does preserve stabilizers, that is, set (there are only two symbols, because we know from context whether $f \in I$ or $f \in S$).

\begin{align} B_{\lambda}(f) &= \{g \in B \mid g \circ f = f\} \\ B_{\rho}(f) &= \{g \in B \mid f \circ g = f\} \end{align} then \begin{align} \Phi(B_\lambda(f)) &= \{\Phi(g) \in B \mid g \circ f = f\} \\ &= \{g \in B \mid \Phi^{-1}(g) \circ f = f\} \\ &= \{g \in B \mid g \circ \Phi(f) = \Phi(f)\} \\ &= B_\lambda(\Phi(f)) \end{align} and for any $g \in B_\lambda(f)$ we have $\Phi(g) \in B_\lambda(\Phi(f))$. Similarly for $B_\rho$.

Now, observe that stabilizers for the above defined $G$-sets have specific properties:

• for any $f \in I$ we have $B_\lambda(f) = \{\idX\}$,
• there exist $f \in I\setminus B$ such that $B_\rho(f) = \{\idX\}$, let's call them lonely,
• there exist $f \in I\setminus B$ such that $|B_\rho(f)| \geq 2$.
• for any $f \in S\setminus B$ we have $|B_\lambda(f)| \geq 2$,
• for any $f \in S$ we have $B_\rho(f) = \{\idX\}$.

This implies that there is no isomorphism between $\tuple{I,\circ,\idX}$ and $\tuple{S,\circ,\idX}$, because for any $f \in I \setminus B$ we would have $\Phi(f) \in S \setminus B$ and $\Phi(B_\lambda(f)) = B_\lambda(\Phi(f))$ which is a contradiction with $$|\Phi(B_\lambda(f))| = |B_\lambda(f)| = 1 < 2 \leq |B_\lambda(\Phi(f))|.$$

Similarly for $\tuple{I,\circ,\idX}$ and $\tuple{S,\bullet,\idX}$, if you would take any lonely $f \in I \setminus B$, then $\Phi(f) \in S \setminus B$, but $$|\Phi(B_\rho(f))| = |B_\rho(f)| = 1 < 2 \leq |B_\rho(\Phi(f))|$$ (the composition order is changed for $\tuple{S,\bullet,\idX}$, hence the interpretatino of $\lambda$ and $\rho$ switches too), so there cannot be any isomorphism between them.

I hope this helps $\ddot\smile$