This question is about an issue left unresolved by Chad
Groft's excellent
question and
John Stillwell's excellent
answer of
it. Since I find the possibility of an affirmative answer
so tantalizing, I would like to pursue it further here.
For background, Rice's Theorem
asserts essentially that no nontrivial question about computably enumerable sets is decidable. If We is the set enumerated by program e, then the theorem states:
Rice's Theorem. If A is a collection of computably
enumerable sets and { e |
We ∈ A } is decidable, then either A is
empty or A contains all computably enumerable sets.
In short, one can decide
essentially nothing about a program e, if the answer is to
depend only on what the program computes rather than how it
computes it.
The question here is about the extent to which a similar
phenomenon holds for finitely presented groups, using the
analogy between programs and finite group presentations:
- a program e is like a finite group presentation p
- the set We enumerated by e is like the group
⟨p⟩ presented by p.
According to this analogy, the analogue of Rice's theorem
would state that any decidable collection of finitely
presented groups (closed under isomorphism) should be either trivial or everything.
John Stillwell pointed out in answer to Chad Groft's
question that this is not true, because from a presentation
p we can easily find a presentation of the abelianization of
⟨p⟩, by insisting that all generators commute,
and many nontrivial questions are decidable about finitely
presented abelian groups. Indeed, since the theory of
abelian groups is a decidable theory, there will be many
interesting questions about finitely presented abelian
groups that are decidable from their presentations.
My question is whether this is the only obstacle.
Question. Does Rice's theorem hold for finitely
presented groups modulo abelianization?
In other words, if
A is a set of finitely presented groups (closed under
isomorphism) and the corresponding set of presentations { p | ⟨p⟩ ∈ A } is
decidable, then does A completely reduce to a question
about the abelianizations of the groups, in the sense that there is a set B of abelian groups such that G ∈ A iff Ab(G) ∈ B?
Of course, in this case B consists exactly of the abelian groups in A. The question is equivalently asking whether A respects the equivalence of groups having isomorphic abelianizations. In other words, must it be that G ∈ A iff Ab(G) ∈ A?
The question is asking whether every decidable set of finitely presented groups amounts actually
to a decidable set of abelian groups, extended to all
finitely presented groups just by saturating with respect to abelianization.
In particular, the set A should contain either none or all perfect groups.
An affirmative answer would seem to provide a thorough
explanation of the pervasive undecidability phenomenon in
group presentations. But perhaps this may simply be too much to hope for…
In any event, I suppose that there is an equivalence relation on finite group presentations, saying that p ≡ q just in case ⟨p⟩ and ⟨q⟩ have the same answer with repsect to any decidable question about finitely presented groups. The question above asks whether this equivalence relation is just Ab(⟨p⟩) = Ab(⟨q⟩). If this turns out not to be true, then what can be said about ≡?
Best Answer
The question "Is there a nonzero homomorphism from your group to $A_5$?" is decidable. (Just write down all ways of sending the generators of your group to $A_5$, and see whether they satisfy the required relations.) The same is true with $A_5$ replaced by any finite group. I don't see how to reduce this to questions about the abelianization.