We can find examples of sets $X$ for which there exists a group $G$ (with |G| > 1) under function composition which is a subset of $X^X$ but not a subset of the group $Sym(X)$. The catch is that the identity of $G$ may not be the identity function, i.e. identity of $Sym(X)$. One such example is as follows:
Let $H$ be a group with identity element $e$. Take $X = H \times H$ and $G = \{(x, y) \mapsto (ax, e) : a \in H\}$ with the map $(x, y) \mapsto (x, e)$ as the identity of $G$. Clearly $G$ is a group.
I have two questions now:
- Are there other such examples?
- Can we classify the sets $X$ for which such groups $G$ exist?
Edit: This is inspired from problem $1.4$ in Algebra by I. Martin Isaacs
You gave a special case of the "only" example: let $X$ be any set and $X = X' \cup Y$ a decomposition of $X$ into disjoint, non-empty subsets. Pick a subgroup $K\leq \mathop{\mathrm{Sym}}(X')$, a function $a:Y\to X'$, and a subgroup $H\leq \mathop{\mathrm{Sym}}(a(Y))$ Then $$\{f:X\to X\mid f|_{X'}\in K \text{ and, for some $h\in H$, } f|_Y = ha \text{ and } f|_{a(Y)} = h\}$$ is a group.
To see why there are no other examples, suppose $G\subseteq X^X$ is a group under function composition. Set $X' = e(X)$ and $Y = X - X'$ for $e$ the identity element of $G$. The equation $e = e\cdot e$, shows that $e(x) = x$ for all $x\in X'$. Define $a:Y\to X'$ by $a = e|_{Y}$. Using $g^{-1}$ to denote group-theoretic inverse for $g\in G$ (i.e., not inverse image), the identity $g^{-1}(g(x)) = g(g^{-1}(x)) = e(x) = x$ for $x\in X'$ shows that $g|_{X'}\in \mathop{\mathrm{Sym}}(X')$. Further, the identity $g(x) = e(g(x))$ for $x\in X$ shows that $g(X)\subseteq X'$. The same identity restricted to $Y$ shows that $g(Y) \subseteq a(Y)$. The subgroup $K\leq \mathop{\mathrm{Sym}}(X')$ is the image of the group homomorphism $G\to \mathrm{Sym}(X'):g\mapsto g|_{X'}$.
It remains to construct the subgroup $H\leq \mathop{\mathrm{Sym}}(a(Y))$, which we realize as the image of a homomorphism $\phi:G\to \mathop{\mathrm{Sym}}(a(Y))$. For $g\in G$, define $\phi(g): a(Y)\to a(Y)$ to be the permutation sending $a(y)$ to $g(y)$ for $y\in Y$ – this is well-defined because $g(y) = g(y')$ if and only if $e(y) = g^{-1}(g(y)) = g^{-1}(g(y')) = e(y')$.