monoids of injections and surjections 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?
 A: $
\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$
