Esta pregunta continúa la línea de investigación de estos tres preguntas.
Pregunta. Que finitely presentado los grupos pueden ser distinguido por decidable propiedades?
Para ser más precisos, digamos que φ es un decidable propiedad de finitely presentan grupos, si hay una clase de finitely presentan grupos, cerrado en el grupo isomorphisms, de tal manera que { p | ⟨p⟩ ∈ A } es decidable, donde ⟨p⟩ denota el grupo presentado por p. Que es, insistimos en que el procedimiento de la decisión de dar la misma respuesta para las presentaciones que conducen a un mismo grupo de isomorfismo.
Un caso extremo, tal vez es poco probable, sería que cualquiera de los dos no isomorfos finitely presentan grupos pueden ser distinguidos por decidable propiedades, por lo que para cualquiera de los dos finitely presentado no isomorfos grupos ⟨p⟩ y ⟨p⟩, hay un decidable de la propiedad donde φ φ(p) tiene y φ(q) se produce un error. Que sería bastante notable.
Si este no es el caso, entonces habría dos finito grupo presentaciones de p y q, tales que los grupos presentan ⟨p⟩ y ⟨p⟩ no son isomorfos, pero tienen todos el mismo decidable propiedades. Esto también sería notable.
Cual es el caso?
Otra forma de describir la pregunta es en términos de la equivalencia relación ≡, que presenté en mi la pregunta anterior, donde p ≡ q si φ(p) y f(q) tienen la misma respuesta para cualquier decidable propiedad φ de finitely presentan grupos. Este es precisamente la relación de equivalencia de "tener todos los mismo decidable propiedades". Por supuesto, esto incluye la grupo-isomorfismo relación, y la cuestión actual es la pregunta: ¿Qué es esta relación ≡? En particular, es ≡ el mismo que el grupo de isomorfismo relación? Si es así, entonces cualquiera de los dos no isomorfos finitely presentado los grupos se pueden distinguir por decidable propiedades; si no, entonces hay dos finitely presentado no isomorfos grupos ⟨p⟩, ⟨p⟩ tener todos el mismo decidable propiedades.
Henry Wilton ha subrayado varias veces que hay relativamente pocos realmente interesante decidable propiedades de finitely presentan grupos. Esto puede muy bien ser cierto. Sin embargo, las respuestas a las anteriores preguntas sobre MO en este tema se han proporcionado al menos algunosdecidable propiedades, y mi pregunta aquí está pidiendo a la medida para que estas propiedades son capaces de distinguir las dos finitely presentan grupos.
En particular, en estos MO preguntas, Chad Groft preguntó si había cualquier no-trivial decidable propiedades de finitely presentado grupos. John Stillwell del la respuestafue que uno podía decidir muchas preguntas acerca de la abelianization del grupo. En una pregunta posterior, me se preguntó si todos los decidable de las propiedades de la realidad, sobre la el abelianization, y David Speyer la respuestafue que no, que hubo preguntas acerca de otros cocientes, tales como si el grupo tenía un trivial en un homomorphism en particular finito de grupo, tales como5. En una tercera pregunta, David generalizada más allá y le preguntó si todos los decidable propiedades dependía de la profinitization, y nuevamente la respuesta fue no (proporcionada por David y Henry). Así que al menos en estos casos hemos sido cada vez más capaz de separar grupos por decidable propiedades.
Una generalización de la pregunta sería ir más allá de la decidable propiedades. Por ejemplo, si consideramos la computably enumerable (c.e.) propiedades, entonces tenemos bastante mucha más capacidad para distinguir grupos. Una propiedad es c.e. si hay una computable algoritmo para determinar la positivo instancias de φ(p), pero sin necesidad de que el negativo instancias para siempre convergen en una respuesta. Para ejemplo, la palabra problema para cualquier finitely presentado el grupo, o, de hecho, para cualquier computably presentado el grupo, es computably enumerable, ya que si una palabra es de hecho trivial, vamos a descubrir con el tiempo este. Utilizando la misma idea como la de David respuesta a mi pregunta, se sigue que la cuestión de la si un finitely presentada grupo ⟨p⟩ admite una trivial homomorphism en los enteros Z, digamos, o muchos otros grupos, es computably enumerable. Uno simplemente puede probar todos los posibles mapas de los generadores. Una generalización de este establece:
Teorema. La cuestión de si uno finitely presentado el grupo ⟨p⟩ mapas homomorphically sobre (o en) otro ⟨p⟩ es computably enumerable.
La prueba es que dado p y q, se puede observar un mapa de los generadores de p a las palabras de p, tal que todos los las relaciones de p son obedecidas por la imagen en la q, y tales que todos los generadores de q están en el rango de la resultante mapa. Este es un c.e. de la propiedad, ya que uno puede mirar para todos los posibles candidatos el mapa de los generadores de p en palabras de q, y comprobar si las relaciones son obedecidas y los generadores de los q están en el rango del mapa y así sucesivamente. Si lo son, finalmente, este va a ser observados, y en el punto en el que uno puede estar seguro de que ⟨p⟩ mapas en ⟨p⟩. De manera más general, es el isomorfismo relación a sí mismo.c.e.? Sin duda es computable a partir de la detención problema 0', ya que se nos podría preguntar 0' si el núcleo de la propuesta de mapa era trivial o no, y el deseo de saber la respuesta.
- ¿De dónde viene el isomorfismo relación en finitely presentan grupos de ajuste en la jerarquía de Turing grados? Es c.e.? Es Turing equivalente a Detener problema?
Una vez que uno se mueve a la c.e. propiedades, es igualmente natural de ir más allá de la finitely presentado los grupos de la computably presentan grupos (los que tienen una computable la presentación, no necesariamente finitely generado). En este contexto, la prueba de arriba ya no funciona, y el natural la generalización de la pregunta:
- Que computably presentan grupos se distinguen por c.e. propiedades?
El isomorfismo relación en finitely generado computably presentan grupos (ponencias) parece ser computables a partir de la detención problema por la misma razón que en la prueba anterior, pero ahora uno no sabe en un número finito de etapa en la que la propuesta de mapa de los generadores se definitivamente el trabajo, ya que se debe verificar que todos los relaciones-todavía-a-ser enumerados. Pero 0' sabe la respuesta, por lo que hacemos computably en 0'. En lo infinitamente generado caso, sin embargo, las cosas son más complicadas.
