Supongamos que tenemos un grupo finitamente presentado$G$ con un problema verbal decidible. ¿Es decidible verificar si un elemento dado$x\in G$ tiene orden finito o infinito?
Respuestas
¿Demasiados anuncios?
Un grupo finitamente presentado con un problema verbal decidible y un problema de orden indecidible está en McCool, James Problemas insolubles en grupos con un problema verbal solucionable. Canad. J. Math. 22 1970 836–838 .
dmnc
Puntos
119
El decidability de la palabra problema en sí no implica la decidability de la orden de problema, y de hecho la siguiente más general, el resultado se mantiene.
Teorema. Deje $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ tres recursivamente enumerable grados de unsolvability (es decir, Turing grados) con $\mathbf{a} \leq \mathbf{b}$ e $\mathbf{a} \leq \mathbf{c}$. Entonces existe un finitely presentó el grupo de $L$ tal que
- la palabra problema para $L$ es de grado $\mathbf{a};$
- el problema de la energía para $L$ es de grado $\mathbf{b};$
- el orden de problema para $L$ es de grado $\mathbf{c}.$
Ver
D. J. Collins: La palabra, el poder y el fin de los problemas en finitely presentan grupos, en "Palabra de Problemas, la Toma de Problemas y el Problema de Burnside en Teoría de grupos", Estudios de Lógica y Fundations de Matemáticas 71 (1973).
Vnuk
Puntos
121
Inspirado por McCool del texto de la ponencia presentada en Benjamin la respuesta, he aquí un ejemplo claro de que es finitely generados pero no finitely presentan:
deje $\phi$ ser un inyectiva función recursiva de enteros positivos a sí mismos, cuya imagen no es recursiva. Considerar el grupo con presentación recursiva $$G=\langle t,x\mid r_{\phi(n)}^{n!}:n\ge 1\rangle,\quad \text{where}\;r_m=[t^mxt^{-m},x].$$ No es difícil comprobar que $r_{\phi(n)}$ tiene orden de $n!$ e $r_m$ tiene una infinidad de orden si $m$ no está en el rango de $\phi$ (añadido: ver más abajo para una variante donde puedo justificar esta afirmación) . En particular, el infinito orden de problema (la comprobación de si un elemento tiene orden infinito) no es solucionable.
Sin embargo, este grupo tiene un problema solucionable. La idea es que, dada una palabra de longitud $n$, es trivial en $G$ si y sólo si es trivial en la presentación parcial con sólo relatores $r_{\phi(k)}^{k!}$ para $k\le n$, y la palabra problema en estos grupos son (creo) al mismo tiempo solucionable, aunque no he revisado los detalles.
En realidad McCool dice que es suficiente para integrar un grupo en un grupo con solucionable palabra problema, no hay necesidad de atención que la imagen es recursiva. Y de hecho eso es suficiente (claramente solvencia de la sucesión infinita problema pasa a finitely generado subgrupos).
Agregó: he aquí una pequeña variante en la que me puede dar un breve argumento de la instrucción en el orden de: definir el salomónicas grupo de Coxeter
$$H=\langle t,x\mid x^2,s_{\phi(n)}^{n!}:n\ge 1\rangle,\quad \text{where}\;s_m=x_0x_m,\;x_m=t^mxt^{-m}.$$
De hecho, vemos enseguida que $H$ es un semidirect producto $\mathbf{Z}\ltimes W$ donde $W$ es el grupo de Coxeter con generadores $x_m$, $m\in\mathbf{Z}$, y Coxeter relaciones $(x_{m+\phi(n)}x_m))^{n!}=1$, donde el grupo cíclico de los actos por el desplazamiento de la $x_m$. Y es bien sabido que en un grupo de Coxeter, las prescritas pedidos son los genuinos de los pedidos [sólo tenemos que comprobar que nos injectively prescribir el fin de que las cantidades de la inyectividad de $(m,n)\mapsto (m+\phi(n),m)$, lo que sigue a partir de inyectabilidad de $\phi$].
Por cierto, de ello se desprende que el mismo es que si eliminamos el relator $x^2=1$ en la presentación anterior.
