decidability de grupo homomorphism existencia

Question

Fijar un finitely-presentado el grupo $G$ distinguido con la no-identidad elemento $g$. Para cualquier finitely-presentado el grupo $H$ con el elemento $h$, es decidable si hay un homomorphism $h: G \rightarrow H$ tal que $h(g) = h\ ?$

Si conocemos $G$ es cíclica, es decir, la pregunta es indecidible por la reducción de la Palabra Problema. Pero, ¿y si no sabemos nada acerca de $G$? Lo que si sabemos $g$ ha finito de orden en $G$?

Answer 1

Estoy con Reid. Si G,H son finitely presentado, y g,los elementos de h, y queremos saber si hay un morfismos f:G->H con f(g)=h, ¿no restringir a una de morfismos en el grupo cíclico generado por g, y por lo tanto ser inmediatamente indecidible?

Answer 2

Si G es cíclico infinito y g genera G, entonces la respuesta es: "sí, hay un mapa" (así, en particular, no es indecidible).

Así que no estoy muy seguro de lo que el cartel original significaba diciendo que si G es cíclico, el problema es redicible a la palabra problema. Tal vez, si alguien ve cómo ese argumento iría (y lo que el derecho es la hipótesis), se podría explicar.

Entonces podría ser más claro si este mismo argumento se puede aplicar si G no es cíclico.

Charles es cierto, por supuesto, decir que un mapa de G a H restringe a un mapa desde el grupo cíclico generado por g, H, pero si se pudiera determinar que no era apropiado mapa de G a H, que no necesariamente a decir que no era apropiado mapa de < g> H, por lo que, en la cara de ella, es posible que podría ser decidable que no había mapas apropiados de G a H, pero no decidable de si era o no apropiado mapas de < g> para H. (Aquí, "adecuado" significa "tomar de g a h".)

(Editado para corregir html cuestión.)

Answer 3

El problema es decidable si y sólo si existe un homomorphism de $G$ hasta el infinito cíclico grupo $\mathbb Z$ de los que tomaron $g$ a 1 (el generador de $\mathbb Z$). Claramente, si un homomorphism existe, la respuesta a tu pregunta es "sí" por cada $H,h$. Supongamos que no hay tal homomorphism. Considere la posibilidad de la firma (grupo de operaciones, nullary operación) de los pares de $(H,h)$ donde $H$ es un grupo, $h\in H$. Deje $X$ el conjunto de los generadores y $R$ el conjunto de la definición de las relaciones de $G$, supongamos $g$ está representado por una palabra $w$$X$. Entonces la pregunta es, si una fórmula $\theta=\exists X (\& R \& (w=h))$ es cierto para el par $(H,h)$. Pero la negación $\neg\theta$ es una propiedad de Markov. De hecho, existe un par de, digamos, $({\mathbb Z},1)$ que satisface $\neg\theta$ debido a que no hay homomorphism $G\to \mathbb Z$ que se lleva a $g$$1$, y existe un par de, digamos, $(G,g)$ que no puede ser embebido en cualquier par $(G',g)$ que satisface $\neg\theta$. La prueba de que las propiedades de Markov para los pares de $(H,h)$ son indecidible es la misma que la prueba de la Adian-Rabin teorema para grupos .

Answer 4

Como personas ya han observado, si G es cíclico infinito y g es un generador, entonces la respuesta es siempre "sí". Steven Sam comentario muestra que no puede haber un uniforme algoritmo que funciona para todos los grupos cíclicos Z/n. En realidad, el problema es indecidible para cualquier n. Por ejemplo:-

Para cíclico finito G de orden n con el generador g, la pregunta puede reformularse como "Es decidable si el elemento h es finito el fin de dividir n?". Supongamos que H es de torsiones. Si este problema es decidable para algún n, entonces el problema es solucionable en H.

Pero el problema no es solucionable en la torsión libre de grupos. Por ejemplo, Collins y Miller construyó una secuencia de presentaciones de torsión libre de grupos H_1, H_2,... con la propiedad de que cada H_i es de torsiones y es indecidible que de la H_i son triviales. (Más precisamente, el conjunto de todos los i tal que H_i es trivial es recursivamente enumerable, pero no recursiva.)