En matemáticas , y más precisamente en teoría de semigrupos , una variedad de semigrupos finitos es una clase de semigrupos que tienen algunas propiedades algebraicas agradables. Esas clases se pueden definir de dos formas distintas, utilizando nociones algebraicas o nociones topológicas. Las variedades de monoides finitos , las variedades de semigrupos ordenados finitos y las variedades de monoides ordenados finitos se definen de manera similar.
Esta noción es muy similar a la noción general de variedad en el álgebra universal.
Definición
Ahora se dan dos definiciones equivalentes.
Definición algebraica
Una variedad V de semigrupos finitos (ordenados) es una clase de semigrupos finitos (ordenados) que:
- está cerrado bajo división .
- se cierra tomando productos cartesianos finitos.
La primera condición equivale a afirmar que V está cerrado de subgrupos de empresas y cocientes de empresas. La segunda propiedad implica que el producto vacío, es decir, el semigrupo trivial de un elemento, pertenece a cada variedad. Por tanto, una variedad es necesariamente no vacía.
Una variedad de monoides finitos (ordenados) es una variedad de semigrupos finitos (ordenados) cuyos elementos son monoides. Es decir, es una clase de monoides (ordenados) que satisfacen las dos condiciones indicadas anteriormente.
Definición topológica
Para dar la definición topológica de una variedad de semigrupos finitos, se necesitan algunas otras definiciones relacionadas con palabras profinitas .
Sea A un alfabeto finito arbitrario . Sea A + su semigrupo libre . Entonces dejael conjunto de palabras profinito más de una . Dado un morfismo de semigrupo , dejar ser la única extensión continua de a .
Una identidad profinito es un par de u y v de las palabras profinito. Se dice que un semigrupo S satisface la identidad profinita u = v si, para cada morfismo de semigrupo, la igualdad sostiene.
Una variedad de semigrupos finitos es la clase de semigrupos finitos que satisfacen un conjunto de identidades profinito P .
Una variedad de monoides finitos se define como una variedad de semigrupos finitos, con la diferencia de que se deben considerar morfismos monoides. en lugar de morfismos de semigrupo .
Una variedad de semigrupos / monoides ordenados finitos también viene dada por una definición similar, con la diferencia de que se deben considerar los morfismos de semigrupos / monoides ordenados.
Ejemplos de
Se dan algunos ejemplos de clases de semigrupos. El primer ejemplo utiliza identidades finitas, es decir, identidades profinitas cuyas dos palabras son palabras finitas. El siguiente ejemplo usa identidades profinitas. El último es un ejemplo de una clase que no es una variedad.
Se dan más ejemplos en el artículo Clases especiales de semigrupos .
Usando identidades finitas
- El ejemplo más trivial es la variedad S de todos los semigrupos finitos. Esta variedad se define por el conjunto vacío de igualdad de ganancias. Es trivial ver que esta clase de semigrupos finitos está cerrada bajo subsemigrupos, productos finitos y cocientes.
- El segundo ejemplo más trivial es la variedad 1 que contiene solo el semigrupo trivial. Esta variedad se define por el conjunto de igualdad de ganancias { x = y }. Intuitivamente, esta igualdad establece que todos los elementos del semigrupo son iguales. Esta clase está trivialmente cerrada bajo subsemigrupos, productos finitos y cocientes.
- La variedad Com de semigrupos finitos conmutativos se define por la igualdad profinita xy = yx . Intuitivamente, esta igualdad establece que cada par de elementos del semigrupo conmuta.
- La variedad de semigrupos finitos idempotentes se define por la igualdad profinita xx = x .
De manera más general, dada una palabra profinita u y una letra x , la igualdad profinita ux = xu establece que el conjunto de imágenes posibles de u contiene solo elementos del centralizador. De manera similar, ux = x establece que el conjunto de posibles imágenes de u contiene solo identidades izquierdas. Finalmente ux = u establece que el conjunto de posibles imágenes de u está compuesto por ceros a la izquierda.
Usar identidades profinitas
Ahora se dan ejemplos que utilizan palabras profinitas que no son finitas.
Dada una palabra profinita, x , sea denotar . Por tanto, dado un morfismo de semigrupo, es el único poder idempotente de . Así, en igualdad de beneficios, representa un idempotente arbitrario.
La clase G de grupos finitos es una variedad de semigrupos finitos. Tenga en cuenta que un grupo finito se puede definir como un semigrupo finito, con un idempotente único, que además es una identidad de izquierda y derecha. Una vez que esas dos propiedades se traducen en términos de igualdad de ganancias, se puede ver que la variedad G está definida por el conjunto de igualdad de ganancias.
Clases que no son variedades
Tenga en cuenta que la clase de monoides finitos no es una variedad de semigrupos finitos. De hecho, esta clase no está cerrada bajo subsemigrupos. Para ver esto, tome cualquier semigrupo S finito que no sea un monoide. Es un subsemigrupo del monoide S 1 formado por un elemento de identidad contiguo.
Teorema de reiterman
El teorema de Reiterman establece que las dos definiciones anteriores son equivalentes. Ahora se da un esquema de la prueba.
Teniendo en cuenta una variedad V de semigroups como en la definición algebraica, se puede elegir el conjunto P de las identidades profinito ser el conjunto de identidades profinito satisfechas por cada semigrupo de V .
Recíprocamente, dada una identidad profinita u = v , se puede observar que la clase de semigrupos que satisfacen esta identidad profinita está cerrada bajo subsemigrupos, cocientes y productos finitos. Por tanto, esta clase es una variedad de semigrupos finitos. Además, las variedades se cierran bajo intersección arbitraria, por lo tanto, dado un conjunto arbitrario P de identidades profinitas u i = v i , la clase de semigrupos que satisfacen P es la intersección de la clase de semigrupos que satisfacen todas esas identidades profinitas. Es decir, es una intersección de variedades de semigrupos finitos, y esta es una variedad de semigrupos finitos.
Comparación con la noción de variedad de álgebra universal
La definición de una variedad de semigrupos finitos se inspira en la noción de una variedad de álgebras universales . Recordamos la definición de una variedad en álgebra universal. Tal variedad es, de manera equivalente:
- una clase de estructuras, cerradas bajo imágenes homomórficas , subálgebras y productos (directos) .
- una clase de estructuras que satisfacen un conjunto de identidades .
Se dan ahora las principales diferencias entre las dos nociones de variedad. En esta sección, "variedad de semigrupos (arbitrarios)" significa "la clase de semigrupos como una variedad de álgebra universal sobre el vocabulario de un operador binario". De las definiciones de esos dos tipos de variedades se deduce que, para cualquier variedad V de semigrupos (arbitrarios), la clase de semigrupos finitos de V es una variedad de semigrupos finitos.
Primero damos un ejemplo de una variedad de semigrupos finitos que no es similar a ninguna subvariedad de la variedad de semigrupos (arbitrarios). Luego damos la diferencia entre las dos definiciones usando identidades. Finalmente, damos la diferencia entre las definiciones algebraicas.
Como se muestra arriba, la clase de grupos finitos es una variedad de semigrupos finitos. Sin embargo, la clase de grupos no es una subvariedad de la variedad de semigrupos (arbitrarios). En efecto,es un monoide que es un grupo infinito. Sin embargo, su submonoideno es un grupo. Dado que la clase de grupos (arbitrarios) contiene un semigrupo y no contiene uno de sus subsemigrupos, no es una variedad. La principal diferencia entre el caso finito y el caso infinito, cuando se consideran grupos, es que un submonoide de un grupo finito es un grupo finito. Mientras que los grupos infinitos no están cerrados al tomar submonoides.
La clase de grupos finitos es una variedad de semigrupos finitos, mientras que no es una subvariedad de la variedad de semigrupos (arbitrarios). Por tanto, el teorema de Reiterman muestra que esta clase se puede definir utilizando identidades profinitas. Y el teorema HSP de Birkhoff muestra que esta clase no se puede definir usando identidades (de palabras finitas). Esto ilustra por qué la definición de una variedad de semigrupos finitos utiliza la noción de palabras profinitas y no la noción de identidades.
Consideremos ahora las definiciones algebraicas de variedades. Exigir que las variedades estén cerradas bajo productos directos arbitrarios implica que una variedad es trivial o contiene estructuras infinitas. Para restringir las variedades para que contengan solo estructuras finitas, la definición de variedad de semigrupos finitos utiliza la noción de producto finito en lugar de la noción de producto directo arbitrario.
Referencias
- Pin, Jean-Éric (30 de noviembre de 2016). Fundamentos matemáticos de la teoría de los autómatas (PDF) . págs. 141–160.
- Pin, Jean-Éric (1986). Variedades de lenguaje formal . Nueva York: Plenum Publishing Corp.
- Eilenberg, S (1976). Autómatas, lenguajes y máquinas . Nueva York: Harcourt Brace Jovanovich Publishers. pp. capítulos "Teorema de descomposición en profundidad" y "Complejidad de semigrupos y morfismos".
- Almeida, J (1994). Semigrupos finitos y álgebra universal . Rivere Edge, Nueva Jersey: World Scientific Publishing Co. Inc.