It is well known that the isomorphism problem for finitely presented groups is unsolvable. That is to say that if $G$ and $G'$are both fp- groups, then in general it is impossible to provide an algorithm that will determine whether or not they are the same. This remains true even if $G'$ is replaced with the trivial group. This raises two questions.

  1. Does there exist a group $G$ such that the isomorphism problem with the trivial group is undecidable? In other words, is their a group such that the triviality of $G$ is independent of ZFC?

2.Is there an explicit example of such a group (undecidable isomorphism problem with the trivial group) with the presentation written out explicitly?

Remarks and corrections

I realize that I have two notions of undecidability going through my head. Th first is whether or not their is a procedure (using Turing machines, for example) to answer the question. I suppose that this means asking whether or not the function that returns one if the group is trivial and zero if it is non-trivial is un-computable (for my example). In formulating the question I was think that I was using some (vague) correspondence or relationship between provability and computability. I do have further questions about the exact relationship and perhaps how to leverage the two notions against one another to obtain uncompuatbility and unprovability results. After all I think that their is some Howard-Curry correspondence, but I do not know if that helps me with my problem. Ultimately my question is:

1'. Does there exist an fp group $G$ such that within ZFC, the statements "$G$ is a trivial group" and "$G$ is not a trivial group" are independent of the axioms of ZFC.

2'. Is there an explicit example of such a group in (1') with generators and relation explicitly in the literature?

3' For both 1' and 2', where in the literature?

  • $\begingroup$ I don't understand what you mean by the isomorphism problem for a single group $G$ and the trivial group. $G$ is either trivial or it's not. $\endgroup$ – Qiaochu Yuan Oct 19 '12 at 5:20
  • $\begingroup$ Perhaps we should ask if there exists a (finite) group presentation for which it is impossible from standard axioms to prove whether or not $G$ is trivial (and if so, if we can know an explicit example of such a presentation). $\endgroup$ – anon Oct 19 '12 at 5:22
  • $\begingroup$ I would take a group presentation for which the triviality of the group is unprovable. In the mean time let me think about the types of edits to make to the question. $\endgroup$ – Baby Dragon Oct 19 '12 at 5:29
  • $\begingroup$ @Baby: you're (implicitly) confusing two meanings of the word "undecidable." In the context of the isomorphism problem, this means that there does not exist an algorithm which takes as input two presentations of two groups $G, G'$ and determines whether $G \cong G'$. This notion of decidability is distinct from decidability in the logical sense, which is the question of whether there exists a proof from the axioms of, say, ZFC of some proposition such as "this group presentation presents the trivial group." $\endgroup$ – Qiaochu Yuan Oct 19 '12 at 5:36
  • $\begingroup$ @Baby: the two meanings of "undecidable" have different types. In computability, "decidability" is a property of a decision problem (en.wikipedia.org/wiki/Decision_problem), whereas in logic, "decidability" is a property of a logical statement. "This group presentation presents the trivial group" is a logical statement but not a decision problem except in the trivial sense because it takes no input. As a decision problem, it's trivially decidable: the answer is either yes or no. (Note that I can prove that a decision problem is decidable without knowing how to decide it.) $\endgroup$ – Qiaochu Yuan Oct 19 '12 at 5:38

Your Answer

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

Browse other questions tagged or ask your own question.