¿Cuando un grupo es isomorfo al Grupo cíclico infinito?

Question

Estoy aprendiendo álgebra y estoy un poco confundido.

¿Vamos a decir tengo un finito presentado grupo $G$, alguien puede decirme si es posible averiguar si $G\cong \mathbb{Z}$?

Gracias

Answer 1

No. Más sorprendente aún: es indecidible si un finitely presentado el grupo es el trivial grupo! Estos hechos fueron probados (de forma independiente) por Adyan y Rabin en los años 50. La idea clave es la de "propiedades de Markov":

Una propiedad $\mathcal{P}$ de finitely presentable grupos es una propiedad de Markov si:

1. la propiedad $\mathcal{P}$ se conserva en el grupo isomorfismo.
2. existe una finitely presentable grupo (testigo) $K_+$ propiedad $\mathcal{P}$.
3. existe una finitely presentable grupo $K_{-}$ que no puede ser incorporado como un subgrupo en cualquier finitely presentable grupo con propiedad $\mathcal{P}$.

El teorema es la siguiente:

Teorema (Adyan-Rabin). Si $\mathcal{P}$ es una propiedad de Markov, entonces no existe un algoritmo con el aporte de un número finito de presentación de $G = \langle \mathbf{x} \mid \mathbf{r}\rangle$ y la que decide si o no en el grupo $G$ definido por esta presentación tiene la propiedad $\mathcal{P}$.

Para una referencia, consulte Lydon y Schupp, Combinatoria, teoría de grupos, en la Sección IV.4, p192. Traté de establecer este teorema, y algunos resultados relacionados, en el "big picture" de la teoría de grupos en esta respuesta anterior.

Así, en los ejemplos que he mencionado anteriormente:

• siendo infinito cíclica es una propiedad de Markov: se conserva bajo un isomorfismo, y tome $K_+=\langle a\mid-\rangle$$K_-=\langle a\mid a^2\rangle$.
• de ser trivial es una propiedad de Markov: se conserva bajo un isomorfismo, y tome $K_+=\langle a\mid a\rangle$$K_-=\langle a\mid a^2\rangle$.

Otro ejemplo:

• un ser finito es una propiedad de Markov: se conserva bajo un isomorfismo, y tome $K_+=\langle a\mid a\rangle$$K_-=\langle a\mid -\rangle$.

Ahora, el ser infinito es no una propiedad de Markov (como todo grupo finito incrusta en una infinita grupo). Sin embargo, esto todavía es indecidible como es el complemento de una propiedad de Markov: Supongamos que tengo un algoritmo con la entrada de $\langle \mathbf{x}\mid\mathbf{r}\rangle$ y que me diga si el grupo asociado es infinito. Si devuelve "no", entonces mi grupo es finito. Por lo tanto, no puedo detectar la finitud, una contradicción.

Un tercer ejemplo (hiperbólica grupos son objetos estándar geométrica teoría del grupo):

• siendo hiperbólica es una propiedad de Markov: se conserva bajo un isomorfismo, y tome $K_+=\langle a\mid a\rangle$$K_-=\langle a, b\mid [a, b]\rangle$. (Es un teorema que $\mathbb{Z}\times\mathbb{Z}$ no incrustar en cualquier hiperbólico grupo).

---

Derek Holt señala en los comentarios a la pregunta que el problema es semi-decidable. Pensé que sería una buena idea construir sobre esto un poco:

Lema. Si $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ (infinito) cíclico , a continuación, es posible demostrarlo.

Esto no contradice undecidability, ya que nunca se sabe cuando a la conclusión de que el grupo de entrada $G$ es no cíclico infinito. Es decir, supongamos que la entrada de $\langle \mathbf{x}\mid\mathbf{r}\rangle$ en el procedimiento dado por el lema anterior, y no terminar después de 1 hora. ¿Qué podemos concluir? Así, podemos concluir nada! Puede darse el caso de que el grupo subyacente es infinito cíclico, pero necesitamos 100 años de la computación para demostrar que no es así.

La prueba del Lema. Escribir $\mathbf{x}=\{x_1, \ldots, x_n\}$. Si $G$ es cíclico, a continuación, existe una palabra $w\in F(\mathbf{x})$ y enteros $p_0, \ldots, p_n$ tal que $x_i=_Gw^{p_i}$. Así, enumerar todas las consecuencias de los relatores y, a continuación, compruebe cada uno de consecuencia para ver si tiene la forma $x_i^{-1}w^{p_i}$ algunos $i, p_i, w$. Terminar el procedimiento, si tenemos un juego completo $\{x_i^{-1}w^{p_i}\mid i=1, \ldots, n\}$ $w$ fijo. Si llegamos a la conclusión de que $G$ es cíclico, entonces podemos fácilmente determinar si es infinito cíclico, como se requiere.

Siguiendo con los ejemplos anteriores, también tenemos el siguiente lema:

Lema. Si $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ es trivial , entonces es posible demostrarlo.

Prueba. Escribir $\mathbf{x}=\{x_1, \ldots, x_n\}$. Enumerar todas las consecuencias de los relatores y, a continuación, compruebe cada uno de consecuencia para ver si tiene la forma $x_i$. Terminar el procedimiento, si tenemos un juego completo $\{x_i^{-1}\mid i=1, \ldots, n\}$.

Answer 2

Depende. Si hay sólo un generador, la respuesta es fácil. Pero si hay más de un generador, entonces en general no, el problema es indecidible provablemente!