Skip to main content
added 344 characters in body; deleted 9 characters in body
Source Link
Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k

This answer is to point out that the particular way in which you have posed the second question is not actually the question you meant to ask, for it admits a trivial answer, requiring almost no knowledge about amenable groups. Namely, you ask,

Does there exist a family of amenable groups (indexed by natural numbers) for which one cannot algorithmically decide if two elements of the family are isomorphic?

The answer is yes. Fix any non-computable set $A\subset\mathbb{N}$, and then enumerate the groups you are interested in $G_0,G_1,G_2,\ldots$ (assuming there are at least two non-isomorphic such groups) in such a way so that the indices $n$ of one of the isomorphism classes is exactly $A$, and use the rest of the indices for the rest of the groups (or just some of them) in an arbitrary manner. That is, we make all $G_n$ for $n\in A$ isomorphic, and not isomorphic to any other $G_m$ for $m\notin A$. With such an enumeration, the isomorphism problem is not decidable, simply because for a fixed $k\in A$, we cannot tell if $G_n\cong G_k$, because this would provide a decision procedure for $n\in A$, which is undecidable.

For example, a similar argument shows that there is an enumeration $G_0,G_1,G_2,\ldots$ of copies of the two groups $\mathbb{Z}$ and $\mathbb{Z}/2\mathbb{Z}$, such that the isomorphism problem is not decidable. Simply make $G_n\cong\mathbb{Z}$ if $n\in A$ and otherwise $G_n\cong \mathbb{Z}/2\mathbb{Z}$, for a fixed undecidable set $A$.

Of course this isn't the answer you or anyone is interested in, even though it does actually answer the question you actually asked. So the point is that you shouldn't consider such arbitrary enumerations when asking decidability questions about finitely presented groups, but rather you want to ask about decidability questions for the more natural enumerations of the presentations that arise from a natural indexing of the presentations, by means of a coding of the syntax of the presentation.

This answer is to point out that the particular way in which you have posed the second question is not actually the question you meant to ask, for it admits a trivial answer, requiring almost no knowledge about amenable groups. Namely, you ask,

Does there exist a family of amenable groups (indexed by natural numbers) for which one cannot algorithmically decide if two elements of the family are isomorphic?

The answer is yes. Fix any non-computable set $A\subset\mathbb{N}$, and then enumerate the groups you are interested in $G_0,G_1,G_2,\ldots$ (assuming there are at least two non-isomorphic such groups) in such a way so that the indices $n$ of one of the isomorphism classes is exactly $A$, and use the rest of the indices for the rest of the groups (or just some of them) in an arbitrary manner. That is, we make all $G_n$ for $n\in A$ isomorphic, and not isomorphic to any other $G_m$ for $m\notin A$. With such an enumeration, the isomorphism problem is not decidable, simply because for a fixed $k\in A$, we cannot tell if $G_n\cong G_k$, because this would provide a decision procedure for $n\in A$, which is undecidable.

Of course this isn't the answer you or anyone is interested in, even though it does actually answer the question you actually asked. So the point is that you shouldn't consider such arbitrary enumerations when asking decidability questions about finitely presented groups, but rather you want to ask about decidability questions for the more natural enumerations of the presentations that arise from a natural indexing of the presentations, by means of a coding of the syntax of the presentation.

This answer is to point out that the particular way in which you have posed the second question is not actually the question you meant to ask, for it admits a trivial answer, requiring almost no knowledge about amenable groups. Namely, you ask,

Does there exist a family of amenable groups (indexed by natural numbers) for which one cannot algorithmically decide if two elements of the family are isomorphic?

The answer is yes. Fix any non-computable set $A\subset\mathbb{N}$, and then enumerate the groups you are interested in $G_0,G_1,G_2,\ldots$ (assuming there are at least two non-isomorphic such groups) in such a way so that the indices $n$ of one of the isomorphism classes is exactly $A$, and use the rest of the indices for the rest of the groups (or just some of them) in an arbitrary manner. That is, we make all $G_n$ for $n\in A$ isomorphic, and not isomorphic to any other $G_m$ for $m\notin A$. With such an enumeration, the isomorphism problem is not decidable, simply because for a fixed $k\in A$, we cannot tell if $G_n\cong G_k$, because this would provide a decision procedure for $n\in A$, which is undecidable.

For example, a similar argument shows that there is an enumeration $G_0,G_1,G_2,\ldots$ of copies of the two groups $\mathbb{Z}$ and $\mathbb{Z}/2\mathbb{Z}$, such that the isomorphism problem is not decidable. Simply make $G_n\cong\mathbb{Z}$ if $n\in A$ and otherwise $G_n\cong \mathbb{Z}/2\mathbb{Z}$, for a fixed undecidable set $A$.

Of course this isn't the answer you or anyone is interested in, even though it does answer the question you actually asked. So the point is that you shouldn't consider such arbitrary enumerations when asking decidability questions about finitely presented groups, but rather you want to ask about decidability questions for the more natural enumerations of the presentations that arise from a natural indexing of the presentations, by means of a coding of the syntax of the presentation.

Source Link
Joel David Hamkins
  • 236.2k
  • 44
  • 777
  • 1.4k

This answer is to point out that the particular way in which you have posed the second question is not actually the question you meant to ask, for it admits a trivial answer, requiring almost no knowledge about amenable groups. Namely, you ask,

Does there exist a family of amenable groups (indexed by natural numbers) for which one cannot algorithmically decide if two elements of the family are isomorphic?

The answer is yes. Fix any non-computable set $A\subset\mathbb{N}$, and then enumerate the groups you are interested in $G_0,G_1,G_2,\ldots$ (assuming there are at least two non-isomorphic such groups) in such a way so that the indices $n$ of one of the isomorphism classes is exactly $A$, and use the rest of the indices for the rest of the groups (or just some of them) in an arbitrary manner. That is, we make all $G_n$ for $n\in A$ isomorphic, and not isomorphic to any other $G_m$ for $m\notin A$. With such an enumeration, the isomorphism problem is not decidable, simply because for a fixed $k\in A$, we cannot tell if $G_n\cong G_k$, because this would provide a decision procedure for $n\in A$, which is undecidable.

Of course this isn't the answer you or anyone is interested in, even though it does actually answer the question you actually asked. So the point is that you shouldn't consider such arbitrary enumerations when asking decidability questions about finitely presented groups, but rather you want to ask about decidability questions for the more natural enumerations of the presentations that arise from a natural indexing of the presentations, by means of a coding of the syntax of the presentation.