Is $S_R$ finitely generated?

Solution 1:

I initially only answered the question whether $H\neq S_R$, where I just confirm I negative answer, and said I think $\mathrm{Sym}_{\mathrm{Rec}}(\mathbf{N})$ is known not to be finitely generated. I've added a proof of this fact as an edit, below.

Your group is easier to describe using $\mathbf{Z}$ than $\mathbf{N}$ (using a recursive bijection between the two). Namely, under this isomorphism it corresponds to $H_1=\langle S_\infty(\mathbf{Z}),f_0\rangle$, and by $f_0$ defined by $f_0(n)=n+1$ for $n\neq 0,-1$, $f(0)=0$, $f(-1)=1$ (infinite cycle with fixed point). This group can be defined "implicitly", namely as the group of permutations of $\mathbf{Z}$ that eventually coincide with a translation. It's also more simply described as $\langle S_\infty(\mathbf{Z}),f_1\rangle$, with $f_1(n)=n+1$.

It's quite clear that $H_1$ is not the whole group of recursive permutations of $\mathbf{Z}$. Indeed, your $f$, viewed as permutation of $\mathbf{Z}$ (fixing negative integers), is not in $H_1$.

(Also there's a unique homomorphism $H_1\to\mathbf{Z}$ mapping $f_1$ to $1$, while $\mathrm{Sym}_{\mathrm{Rec}}(\mathbf{Z})$ can be shown t be a perfect group. Indeed it was proved by C. Kent (1962, link at AMS site) that $\mathrm{Sym}_{\mathrm{Rec}}(\mathbf{Z})$ has only 4 normal subgroups (similarly as in the Onofri/Schreier-Ulam theorem): the whole, the trivial subgroup, the finitary subgroup, and the subgroup of index 2 therein).

Edit: It took me a few hours to reconstitute the argument of infinite generation, which was enough for a grumpy user to downvote.

Lemma There is no computable map $f:\mathbf{N}^2\to \mathbf{N}$ such that $n\mapsto f(n,-)=:f_n$ is a surjection of $\mathbf{N}$ onto $S_R$.

Proof: assume so. Let $u(n,m)=u_n(m)$ be the supremum of $f_n$ on $[0,m]$. So $(m,n)\mapsto u(m,n)$ is computable. Let $u$ be a computable increasing function such that $u\gg u_n$ for all $n$ (it exists by an easy diagonal argument, namely $u=\sum \mathbf{1}_{[n,\infty[}u_n)$). Let $q$ be the permutation exchanging $n$ and $2u(n)$ for every odd $n$, and fixing other elements. Then it is computable, and cannot be among the $f_n$.

Corollary $S_R$ is not finitely generated.

Proof: otherwise, it's generated by some finite subset $S$. Then using the surjective map $p:F_S\to S_R$ and using a computable bijection $q:\mathbf{N}\to F_S$ we get the map $(n,m)\mapsto q(n)m$ which is computable and contradicts the lemma.