Does there exist an abelian group with recursively enumerable presentation and insoluble word problem?

My gut says "of course not!". However, my mind keeps saying "but...doesn't $\mathbb{R}$ have insoluble word problem? Wasn't that what Turing's original paper on computability basically did? And this makes sense, because the reals are uncountable so do not have a recursively enumerable presentation." (I should say that my mind is unwilling to commit to these claims.)

Basically, I have no idea. "Clearly" there exists no such group, but I know that whenever the word "clearly" is used there is something that someone is trying to hide...

  • $\begingroup$ Clearly the answer is no if the group is finitely generated, as we can always present two words in lexycographic order (commutativity) and then decide whether they're the same or not. The question (for me) is whether we can do the same with infinitely generated abelian group, but then we could perhaps (I'm getting into deep waters here) well-order the generators set (Ok, AC is necessary here) and we'd get something similar as the f.g. case. $\endgroup$ – Timbuc Jan 22 '15 at 10:21
  • $\begingroup$ @Timbuc I am not sure that the obvious "ordering" argument would work, because it may be that the ordering would need to be compatible with the group operation for this argument to work. But I don't know. Maybe it does. Maybe it is all obvious. My head hurts. $\endgroup$ – user1729 Jan 22 '15 at 10:26
  • 3
    $\begingroup$ All the definitions of the "word problem" that I have ever seen apply only to finitely generated groups, so I literally have no idea what you are talking about! $\endgroup$ – Derek Holt Jan 22 '15 at 10:43
  • 2
    $\begingroup$ @Hanno The group that you defined is either equal to the trivial group or to an infinite cyclic group, and in either case the word problem is solvable. The fact that we don't know which is not relevant to this question. It is a easy theorem that finitely generated abelian groups have solvable word problem. (The same is true for f.g. nilpotent groups, polycyclic groups, but not for f.g. solvable groups.) $\endgroup$ – Derek Holt Jan 22 '15 at 12:34
  • 1
    $\begingroup$ @DerekHolt: sigh Sure, somehow I thought that the fact that we cannot decide which of the two cases holds would cause trouble. Thanks for clarifying! $\endgroup$ – Hanno Jan 24 '15 at 8:30

The question is unclear, since as Derek Holt mentioned, "solvable word problem" has not been defined. If you have a presentation with a sequence of generators, you can ask two questions:

1) whether this group endowed with this generating family has a solvable word problem

2) whether this group is isomorphic to a computable group (i.e. is finite or isomorphic to $\mathbf{N}$ endowed with a computable law; this also means that it admits a generating family (maybe not the initial one) for which the word problem is solvable.

For instance, as a variation of Ferov's answer: let $K\subset\mathbf{N}$ be a recursively enumerable, non-recursive set.

a) Consider the group $\langle x_1,x_2,\dots\mid x_k=1 \forall k\in K\rangle$

then the word problem is not solvable with respect to this generating family. But of course this group is free abelian of countable rank, hence has solvable word problem with respect to a better choice of generating family!

b) If instead we consider, the group $$\langle x_1,x_2,\dots\mid x_j^j=1 \forall j\in\mathbf{N},\;x_k=1\forall k\in K\rangle,$$ then it is isomorphic to $A_K=\bigoplus_{k\in\mathbf{N}-K}\mathbf{Z}/k\mathbf{Z}$. Now assume that $K$ contains all non-primes: then if $A_K$ were computable, we could enumerate all the orders of torsion elements of $A_K$, which is exactly $\mathbf{N}-K$, a contradiction.


In the finitely generated case the answer is NO as pointed out by @Timbuc in the comments. In the infinitely generated case I believe that the answer is YES by the following construction.

Let $K \subseteq \mathbb{N}$ be a recursively enumerable non-recursive set and consider a countable abelian group given by the following presentation (commutators omitted): $$ \langle x_1, x_2,\dots \| x_k^k = 1 \mbox{ whenever } k \in K\rangle. $$ If we could solve word problem in this group then we could decide the set $K$ which would be a contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.