Return to Answer

This should be a comment to HW's answer but it is too long. I believe that the correct theorem is that a collection P of primes is the set of prime orders of the finite order elements of a finitely presented group iff there is an re set U, a computable function $f\colon U\to Primes$ and r.e. sets L,K contained in U such that $P=f(L-K)$. I don't know if such a set of primes must be a difference of r.e. sets (which is HW's) answer.

Here is the proof. Suppose first that we have a finitely presented group. Then U will be all pairs (u,p) where u is a word over the generators and their inverses and p is a prime, f is the projection to the second coordinate, L is all pairs (u,p) with $u^p=1$ in the group (r.e. by finiteness of the presentation) and K is all pairs (u,p) with u=1 (r.e. for the same reason). Clearly the prime orders of elements of the group is f(L-K).

Conversely, given U,L,K,f as above consider the group G with generators U subject to the relations $x^{f(x)}=1$ for x in L and $x=1$ for x in K. This group has an r.e. set of generators and an r.e. set of relators and hence by the argument of HW can be embedded in a finitely presented group with the same finite orders. Now G is a free product of infinite cyclic groups (one for each element of U not in K or L) and finite cyclic groups of order from f(L-K) (there may be repetitions because f is many to one).

Edit. I have learned from Computable images of differences of r.e. sets that the sets of the above form are precisely the $\Sigma^0_2$ sets of the arithmetic hierarchy and hence much broader than differences of re sets. In his comments to HW's answer François sketches how to construct the analogue of G above directly from a logical formula.

This should be a comment to HW's answer but it is too long. I believe that the correct theorem is that a collection P of primes is the set of prime orders of the finite order elements of a finitely presented group iff there is an re set U, a computable function $f\colon U\to Primes$ and r.e. sets L,K contained in U such that $P=f(L-K)$. I don't know if such a set of primes must be a difference of r.e. sets (which is HW's) answer.

Here is the proof. Suppose first that we have a finitely presented group. Then U will be all pairs (u,p) where u is a word over the generators and their inverses and p is a prime, f is the projection to the second coordinate, L is all pairs (u,p) with $u^p=1$ in the group (r.e. by finiteness of the presentation) and K is all pairs (u,p) with u=1 (r.e. for the same reason). Clearly the prime orders of elements of the group is f(L-K).

Conversely, given U,L,K,f as above consider the group G with generators U subject to the relations $x^{f(x)}=1$ for x in L and $x=1$ for x in K. This group has an r.e. set of generators and an r.e. set of relators and hence by the argument of HW can be embedded in a finitely presented group with the same finite orders. Now G is a free product of infinite cyclic groups (one for each element of U not in K or L) and finite cyclic groups of order from f(L-K) (there may be repetitions because f is many to one).

Edit. I have learned from Computable images of differences of r.e. sets that the sets of the above form are precisely the $\Sigma^0_2$ sets of the arithmetic hierarchy and hence much broader than differences of re sets. In his comments to HW's answer François sketches how to construct the analogue of G above directly from a logical formula.

This should be a comment to HW's answer but it is too long. I believe that the correct theorem is that a collection P of primes is the set of prime orders of the finite order elements of a finitely presented group iff there is an re set U, a computable function $f\colon U\to Primes$ and r.e. sets L,K contained in U such that $P=f(L-K)$. I don't know if such a set of primes must be a difference of r.e. sets (which is HW's) answer.

Here is the proof. Suppose first that we have a finitely presented group. Then U will be all pairs (u,p) where u is a word over the generators and their inverses and p is a prime, f is the projection to the second coordinate, L is all pairs (u,p) with $u^p=1$ in the group (r.e. by finiteness of the presentation) and K is all pairs (u,p) with u=1 (r.e. for the same reason). Clearly the prime orders of elements of the group is f(L-K).

Conversely, given U,L,K,f as above consider the group G with generators U subject to the relations $x^{f(x)}=1$ for x in L and $x=1$ for x in K. This group has an r.e. set of generators and an r.e. set of relators and hence by the argument of HW can be embedded in a finitely presented group with the same finite orders. Now G is a free product of infinite cyclic groups (one for each element of U not in K or L) and finite cyclic groups of order from f(L-K) (there may be repetitions because f is many to one).

This should be a comment to HW's answer but it is too long. I believe that the correct theorem is that a collection P of primes is the set of prime orders of the finite order elements of a finitely presented group iff there is an re set U, a computable function $f\colon U\to Primes$ and r.e. sets L,K contained in U such that $P=f(L-K)$. I don't know if such a set of primes must be a difference of r.e. sets (which is HW's) answer.

Here is the proof. Suppose first that we have a finitely presented group. Then U will be all pairs (u,p) where u is a word over the generators and their inverses and p is a prime, f is the projection to the second coordinate, L is all pairs (u,p) with $u^p=1$ in the group (r.e. by finiteness of the presentation) and K is all pairs (u,p) with u=1 (r.e. for the same reason). Clearly the prime orders of elements of the group is f(L-K).

Conversely, given U,L,K,f as above consider the group G with generators U subject to the relations $x^{f(x)}=1$ for x in L and $x=1$ for x in K. This group has an r.e. set of generators and an r.e. set of relators and hence by the argument of HW can be embedded in a finitely presented group with the same finite orders. Now G is a free product of infinite cyclic groups (one for each element of U not in K or L) and finite cyclic groups of order from f(L-K) (there may be repetitions because f is many to one).

Edit. I have learned from Computable images of differences of r.e. sets that the sets of the above form are precisely the $\Sigma^0_2$ sets of the arithmetic hierarchy and hence much broader than differences of re sets. In his comments to HW's answer François sketches how to construct the analogue of G above directly from a logical formula.

This should be a comment to HW's answer but it is too long. I believe that the correct theorem is that a collection P of primes is the set of prime orders of the finite order elements of a finitely presented group iff there is an re set U, a computable function $f\colon U\to Primes$ and r.e. sets L,K contained in U such that $P=f(L-K)$. I don't know if such a set of primes must be a difference of r.e. sets (which is HW's) answer.

Here is the proof. Suppose first that we have a finitely presented group. Then U will be all pairs (u,p) where u is a word over the generators and their inverses, f is the projection to the second coordinate, L is all pairs (u,p) with $u^p=1$ in the group (r.e. by finiteness of the presentation) and K is all pairs (u,p) with u=1 (r.e. for the same reason). Clearly the prime orders of elements of the group is f(L-K).

Conversely, given U,L,K,f as above consider the group G with generators U subject to the relations $x^{f(x)}=1$ for x in L and $x=1$ for x in K. This group has an r.e. set of generators and an r.e. set of relators and hence by the argument of HW can be embedded in a finitely presented group with the same finite orders. Now G is a free product of infinite cyclic groups (one for each element of U not in K or L) and finite cyclic groups of order from f(L-K) (there may be repetitions because f is many to one).

This should be a comment to HW's answer but it is too long. I believe that the correct theorem is that a collection P of primes is the set of prime orders of the finite order elements of a finitely presented group iff there is an re set U, a computable function $f\colon U\to Primes$ and r.e. sets L,K contained in U such that $P=f(L-K)$. I don't know if such a set of primes must be a difference of r.e. sets (which is HW's) answer.

Here is the proof. Suppose first that we have a finitely presented group. Then U will be all pairs (u,p) where u is a word over the generators and their inverses and p is a prime, f is the projection to the second coordinate, L is all pairs (u,p) with $u^p=1$ in the group (r.e. by finiteness of the presentation) and K is all pairs (u,p) with u=1 (r.e. for the same reason). Clearly the prime orders of elements of the group is f(L-K).

Conversely, given U,L,K,f as above consider the group G with generators U subject to the relations $x^{f(x)}=1$ for x in L and $x=1$ for x in K. This group has an r.e. set of generators and an r.e. set of relators and hence by the argument of HW can be embedded in a finitely presented group with the same finite orders. Now G is a free product of infinite cyclic groups (one for each element of U not in K or L) and finite cyclic groups of order from f(L-K) (there may be repetitions because f is many to one).