When is a group isomorphic to the infinite cyclic group? I am learning algebra and I am a bit confused.
Let's say I have a finitely presented group $G$, can anyone tell me if it is possible to find out if $G\cong \mathbb{Z}$?
Thanks
 A: No. More strikingly: it is undecidable if a finitely presented group is the trivial group! These facts were proven (independently) by Adyan and Rabin in the 50s. The key idea is that of "Markov properties":

A property $\mathcal{P}$ of finitely presentable groups is a Markov property if:
  
  
*
  
*the property $\mathcal{P}$ is preserved under group isomorphism.
  
*there exists a finitely presentable group (a witness) $K_+$ with property $\mathcal{P}$.
  
*there exists a finitely presentable group $K_{-}$ which cannot be embedded as a subgroup in any finitely presentable group with property $\mathcal{P}$.
  

The theorem is as follows:

Theorem (Adyan-Rabin). If $\mathcal{P}$ is a Markov property then there does not exist an algorithm with input a finite presentation $G = \langle \mathbf{x} \mid \mathbf{r}\rangle$ and which decides whether or not the group $G$ defined by this presentation has property $\mathcal{P}$.

For a reference, see Lydon and Schupp, Combinatorial group theory, Section IV.4, p192. I tried to set this theorem, and some related results, in the "big picture" of group theory in this old answer.
So, for the examples I mentioned above:


*

*being infinite cyclic is a Markov property: it is preserved under isomorphism, and take $K_+=\langle a\mid-\rangle$ and $K_-=\langle a\mid a^2\rangle$.

*being trivial is a Markov property: it is preserved under isomorphism, and take $K_+=\langle a\mid a\rangle$ and $K_-=\langle a\mid a^2\rangle$.


Another example:


*

*being finite is a Markov property: it is preserved under isomorphism, and take $K_+=\langle a\mid a\rangle$ and $K_-=\langle a\mid -\rangle$.


Now, being infinite is not a Markov property (as every finite group embeds in an infinite group). However, this is still undecidable as it is the complement of a Markov property: Suppose I have an algorithm with input $\langle \mathbf{x}\mid\mathbf{r}\rangle$ and which tells me if the associated group is infinite. If it returns "no" then my group is finite. Hence, I can detect finiteness, a contradiction.
A third example (hyperbolic groups are standard objects in geometric group theory):


*

*being hyperbolic is a Markov property: it is preserved under isomorphism, and take $K_+=\langle a\mid a\rangle$ and $K_-=\langle a, b\mid [a, b]\rangle$. (It is a theorem that $\mathbb{Z}\times\mathbb{Z}$ does not embed into any hyperbolic group.)



Derek Holt points out in the comments to the question that the problem is semi-decidable. I thought it would be a good idea to build on this a litte:

Lemma. If $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ is (infinite) cyclic then it is possible to prove it.

This does not contradict undecidability, as you will never know when to conclude that the input group $G$ is not infinite cyclic. That is, suppose that we input $\langle \mathbf{x}\mid\mathbf{r}\rangle$ into the procedure given by the above lemma, and it doesn't terminate after 1 hour. What can we conclude? Well, we can conclude nothing! It may be the case that the underlying group is infinite cyclic, but we need 100 years of computation to prove that it is so.
Proof of Lemma.
Write $\mathbf{x}=\{x_1, \ldots, x_n\}$. If $G$ is cyclic then there exists a word $w\in F(\mathbf{x})$ and integers $p_0, \ldots, p_n$ such that $x_i=_Gw^{p_i}$. So, enumerate all consequences of the relators and then check each consequence to see if it has the form $x_i^{-1}w^{p_i}$ for some $i, p_i, w$. Terminate the procedure if we have a "complete" set $\{x_i^{-1}w^{p_i}\mid i=1, \ldots, n\}$ with $w$ fixed. If we conclude that $G$ is cyclic then we can easily determine if it is infinite cyclic, as required.
Sticking with the examples above, we also have the following lemma:

Lemma. If $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ is trivial then it is possible to prove it.

Proof.
Write $\mathbf{x}=\{x_1, \ldots, x_n\}$. Enumerate all consequences of the relators and then check each consequence to see if it has the form $x_i$. Terminate the procedure if we have a "complete" set $\{x_i^{-1}\mid i=1, \ldots, n\}$.
A: It depends.  If there's only one generator, the answer is easy.  But if there is more than one generator, then in general no, the problem is provably undecidable!
