Return to Answer

Notation:

If $n\in \mathbb{N}$, then we denote by $\pi(n)$ the set of all non-trivial factors of $n$, including $n$ but excluding $1$. Call a set $X \subseteq \mathbb{N}$ factor-complete if it is closed under taking non-trivial factors. That is, $n\in X \Rightarrow \pi(n) \subseteq X$. Now we can state a strengthened answer to the main question of this post:

Complete characterisation:

Technical result:

Answer to main question:

Sets which can be realised up to one-one equivalence: Given any $\Sigma_{2}^{0}$ set $A$, the set $A_{prime}$ is one-one equivalent to $A$, and can be realised as the set of orders of torsion elements of some finitely presented group $G$.

Proof of technical result: Let $\{a \in \mathbb{N}\ | \ (\exists m)(\forall n) (\phi(a,m,n)=1)\}$ be the description for the factor-complete $\Sigma_{2}^{0}$ set $A$, where $\phi: \mathbb{N}^3 \to \mathbb{N}$ is our computable function. Let $p_{1}, p_{2}, \ldots$ be the standard indexing of the primes ordered by size. Then we construct a countably generated recursive presentation as follows: Take the infinite set of symbols $x_{1}, x_{2}, \ldots$; this is our generating set. For any fixed $i>1$, add the relation $x_{p_{i}}^{i}=1$. Then, start successively computing $\phi(i,1,1), \phi(i,1,2), \phi(i,1,3), \ldots$ increasing the last variable by $1$ each time. If at some point $\phi(i,1,n)\neq 1$ then stop, add the relations $x_{p_{i}}=1$, $x_{p_{i}^{2}}^{i}=1$, and start successively computing $\phi(i,2,1), \phi(i,2,2), \phi(i,2,3), \ldots$. If again some $\phi(i,2,n)\neq 1$, then stop, add the relations $x_{p_{i}^{2}}=1$, $x_{p_{i}^{3}}^{i}=1$, and start computing $\phi(i,3,1),\phi(i,3,2), \ldots$. By interleaving this process for all $i \in \mathbb{N}$, we get a countably generated recursive presentation which we denote by $Q_{\phi}$. Notice that:

So we end up with the group $F_{\infty}*_{a \in A}(*_{j \in \pi(a)}C_{j})$

Notation:

If $n\in \mathbb{N}$, then we denote by $\pi(n)$ the set of all non-trivial factors of $n$, including $n$ but excluding $1$. Call a set $X \subseteq \mathbb{N}$ factor-complete if it is closed under taking non-trivial factors. That is, $n\in X \Rightarrow \pi(n) \subseteq X$. Now we can state a strengthened answer to the main question of this post:

Complete characterisation:

Technical result:

Answer to main question:

Sets which can be realised up to one-one equivalence:

Given any $\Sigma_{2}^{0}$ set $A$, the set $A_{prime}$ is one-one equivalent to $A$, and can be realised as the set of orders of torsion elements of some finitely presented group $G$.

Proof of technical result:

Let $\{a \in \mathbb{N}\ | \ (\exists m)(\forall n) (\phi(a,m,n)=1)\}$ be the description for the factor-complete $\Sigma_{2}^{0}$ set $A$, where $\phi: \mathbb{N}^3 \to \mathbb{N}$ is our computable function. Let $p_{1}, p_{2}, \ldots$ be the standard indexing of the primes ordered by size. Then we construct a countably generated recursive presentation as follows: Take the infinite set of symbols $x_{1}, x_{2}, \ldots$; this is our generating set. For any fixed $i>1$, add the relation $x_{p_{i}}^{i}=1$. Then, start successively computing $\phi(i,1,1), \phi(i,1,2), \phi(i,1,3), \ldots$ increasing the last variable by $1$ each time. If at some point $\phi(i,1,n)\neq 1$ then stop, add the relations $x_{p_{i}}=1$, $x_{p_{i}^{2}}^{i}=1$, and start successively computing $\phi(i,2,1), \phi(i,2,2), \phi(i,2,3), \ldots$. If again some $\phi(i,2,n)\neq 1$, then stop, add the relations $x_{p_{i}^{2}}=1$, $x_{p_{i}^{3}}^{i}=1$, and start computing $\phi(i,3,1),\phi(i,3,2), \ldots$. By interleaving this process for all $i \in \mathbb{N}$, we get a countably generated recursive presentation which we denote by $Q_{\phi}$. Notice that:

So we end up with the group $ gp(Q_{\phi}) \cong F_{\infty}$ $* _ {a \in A} ( * _ {j \in \pi(a)} C_{j})$

That $2\Rightarrow 1$ is immediate; torsion-orders are closed under taking factors, and have a $\Sigma_{2}^{0}$ description (see the proof of theorem 3.5 in arXiv:1107.1489v2). That $1 \Rightarrow 2$ can be seen from the following result, which is proved by a generalisation of an argument provided by Francois Dorais in an earlier post on this thread:

That $1\Rightarrow 2$ is immediate; torsion-orders are closed under taking factors, and have a $\Sigma_{2}^{0}$ description (see the proof of theorem 3.5 in arXiv:1107.1489v2). That $2 \Rightarrow 1$ can be seen from the following result, which is proved by a generalisation of an argument provided by Francois Dorais in an earlier post on this thread: