grupo sobrejuntivo
En matemáticas, un grupo sobrejuntivo es un grupo tal que todo autómata celular inyectivo con los elementos del grupo como sus células también es sobreyectivo . Los grupos superjuntivos fueron introducidos por Gottschalk (1973) . Se desconoce si todos los grupos son sobrejuntivos.
Un autómata celular consta de un sistema regular de celdas, cada una de las cuales contiene un símbolo de un alfabeto finito , junto con una regla uniforme llamada función de transición para actualizar todas las celdas simultáneamente en función de los valores de las celdas vecinas. Lo más común es que las celdas estén dispuestas en forma de una línea o una cuadrícula de enteros de mayor dimensión , pero también son posibles otras disposiciones de celdas. Lo que se requiere de las celdas es que formen una estructura en la que cada celda "se vea igual que" cualquier otra celda: hay una simetría tanto en la disposición de las celdas como en el conjunto de reglas que lleva a cualquier celda a cualquier otra celda. Matemáticamente, esto se puede formalizar mediante la noción de un grupo, un conjunto de elementos junto con una operación binaria asociativa e invertible. Los elementos del grupo se pueden utilizar como las células de un autómata, con simetrías generadas por la operación del grupo. Por ejemplo, una línea de celdas unidimensional se puede describir de esta manera como el grupo aditivo de los enteros , y las cuadrículas de enteros de dimensiones superiores se pueden describir como los grupos abelianos libres .
La colección de todos los estados posibles de un autómata celular sobre un grupo puede describirse como las funciones que asignan cada elemento del grupo a uno de los símbolos del alfabeto. Como conjunto finito, el alfabeto tiene una topología discreta , y al conjunto de estados se le puede dar la topología del producto (llamada topología prodiscreta porque es el producto de topologías discretas). Para ser la función de transición de un autómata celular, una función de estado a estado debe ser una función continua para esta topología, y también debe ser equivariantecon la acción de grupo, lo que significa que desplazar las celdas antes de aplicar la función de transición produce el mismo resultado que aplicar la función y luego desplazar las celdas. Para tales funciones, el teorema de Curtis-Hedlund-Lyndon asegura que el valor de la función de transición en cada elemento del grupo depende del estado anterior de solo un conjunto finito de elementos vecinos.
Una función de transición de estado es una función sobreyectiva cuando cada estado tiene un predecesor (no puede haber Jardín del Edén ). Es una función inyectiva cuando no hay dos estados que tengan el mismo sucesor. Un grupo sobrejuntivo es un grupo que tiene la propiedad de que, cuando sus elementos se utilizan como células de autómatas celulares, toda función de transición inyectiva de un autómata celular es también sobreyectiva. De manera equivalente, resumiendo las definiciones anteriores, un grupo es sobreyectivo si, para cada conjunto finito , cada función inyectiva equivariante continua también es sobreyectiva. [1] La implicación de la inyectividad a la sobreyectividad es una forma del teorema del Jardín del Edén., y los autómatas celulares definidos a partir de funciones de transición inyectivas y sobreyectivas son reversibles .
Los ejemplos de grupos sobrejuntivos incluyen todos los grupos localmente residuales finitos , [2] todos los grupos libres , [2] todos los subgrupos de grupos sobrejuntivos, [3] todos los grupos abelianos, [2] todos los grupos sóficos , [4] y cada grupo local sobrejuntivo. [3]
Cuando introdujo los grupos sobrejuntivos en 1973, Gottschalk observó que no había ejemplos conocidos de grupos no sobrejuntivos. A partir de 2014, aún se desconoce si todos los grupos son sobrejuntivos. [5]