2
$\begingroup$

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?

  • 0
    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.2012-10-19
  • 0
    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).2012-10-19
  • 0
    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.2012-10-19
  • 0
    @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."2012-10-19
  • 0
    @Baby: the two meanings of "undecidable" have different types. In computability, "decidability" is a property of a decision problem (http://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.)2012-10-19
  • 0
    OTOH, the problem of deciding if a finitely presented group is trivial, given the presentation *is* a decision problem and non-trivial :-)2012-10-19
  • 0
    Further to Mariano's comment, you should know that if $\mathcal{P}=\langle X; \mathbf{r}\rangle$ is a finite presentation for the trivial group then one can apply Tietze transformations to this presentation to get the trivial group. There is a long-standing open problem which asks if you take a *balanced* finite presentation for the trivial group (balanced means $|X|=|\mathbf{r}|$) then is there a sequence of Nielsen transformations which takes $\mathcal{P}$ and turns it into the trivial presentation $\langle x_1, \ldots, x_{|X|}; r_1, \ldots, r_{|X|}\rangle$. (cont.)2012-10-19
  • 0
    (cont.) Note that Neilsen transformations are the Tietze transformations which do not add or remove any generators. This is called the Andrews-Curtis conjecture.2012-10-19
  • 0
    Thanks to Anon and Qiaochu for the illuminating comments.2012-11-08

0 Answers 0