Suppose $S_R$ - is the set of all total recursive bijections on $\mathbb{N}$. It is not hard to see that this set forms a group with respect to composition, and that $|S_R| = \aleph_0$. Is $S_R$ finitely generated?
The group $S_R$ contains the group $S_\infty$ (the group of finitely based bijections) as its subgroup, which is infinitely generated. However, there exists $S_\infty < H \leq S_R$, such that $H$ is finitely generated. The $H$ can be described as $\langle (01), f \rangle$, where $f$ is defined by formula:
$$f(x) = \begin{cases} 0 & \quad x = 0 \\ 2 & \quad x = 1 \\ x + 2 & \quad x \geq 2 \text{ and is even} \\ x - 2 & \quad x \geq 2 \text{ and is odd} \end{cases}$$
Indeed, $\forall x = 2n+1$ $(0x)=(01)f^{n}$ and $\forall x = 2n$ $(0x)=(01)f^{-n}$. Hovever, this does not give us the answer to the question as $H$ is most likely a proper subgroup of $S_R$ (though, i do not know for sure).
from Hot Weekly Questions - Mathematics Stack Exchange
Yanior Weg
Post a Comment