En álgebra e informática teórica , una acción o acto de un semigrupo sobre un conjunto es una regla que asocia a cada elemento del semigrupo una transformación del conjunto de tal forma que el producto de dos elementos del semigrupo (utilizando el semigrupo operación ) está asociado con el compuesto de las dos transformaciones correspondientes. La terminología transmite la idea de que los elementos del semigrupo actúan como transformaciones del conjunto. Desde una perspectiva algebraica , una acción de semigrupo es una generalización de la noción deacción de grupo en la teoría de grupos . Desde el punto de vista de la informática, las acciones de semigrupo están estrechamente relacionadas con los autómatas : el conjunto modela el estado del autómata y la acción modela las transformaciones de ese estado en respuesta a las entradas.
Un caso especial importante es una acción o acto monoide , en el que el semigrupo es un monoide y el elemento de identidad del monoide actúa como la transformación de identidad de un conjunto. Desde el punto de vista de la teoría de la categoría , un monoide es una categoría con un objeto, y un acto es un funtor de esa categoría a la categoría de conjuntos . Esto proporciona inmediatamente una generalización de los actos de monoide sobre objetos en categorías distintas de la categoría de conjuntos.
Otro caso especial importante es un semigrupo de transformación . Se trata de un semigrupo de transformaciones de un conjunto y, por tanto, tiene una acción tautológica sobre ese conjunto. Este concepto está vinculado a la noción más general de un semigrupo por un análogo del teorema de Cayley .
(Una nota sobre terminología: la terminología utilizada en esta área varía, a veces significativamente, de un autor a otro. Consulte el artículo para obtener más detalles).
Definiciones formales
Sea S un semigrupo. Entonces, una acción (o acto ) de semigrupo (izquierda) de S es un conjunto X junto con una operación •: S × X → X que es compatible con la operación de semigrupo ∗ de la siguiente manera:
- para todos los s , t en S y x en X , s • ( t • x ) = ( s * t ) • x .
Este es el análogo en teoría semigrupo de un (a la izquierda) la acción de grupo , y es equivalente a un homomorfismo semigrupo en el conjunto de funciones en X . Las acciones de semigrupo derecho se definen de manera similar usando una operación •: X × S → X que satisface ( x • a ) • b = x • ( a ∗ b ) .
Si M es un monoide, entonces una acción (o acto ) monoide (izquierda) de M es una acción de semigrupo (izquierda) de M con la propiedad adicional de que
- para todo x en X : e • x = x
donde e es el elemento identidad de M . Esto da correspondientemente un homomorfismo monoide. Las acciones del monoide derecho se definen de manera similar. Un monoide M con una acción en un conjunto también se denomina operador monoide .
Un semigrupo acción de S en X se puede convertir en acto monoid colindando una identidad a la semigrupo y requiriendo que actúa como la transformación de identidad en X .
Terminología y notación
Si S es un semigrupo o monoid, a continuación, un conjunto X en el que S actúa como arriba (a la izquierda, por ejemplo) también se conoce como un (izquierda) S -act , S -set , S -action , S -operand , o acto izquierda sobre S . Algunos autores no distinguen entre acciones de semigrupo y monoides, al considerar el axioma de identidad ( e • x = x ) como vacío cuando no hay elemento de identidad, o al usar el término acto- S unitario para un acto- S con identidad. [1]
La propiedad definitoria de un acto es análoga a la asociatividad de la operación de semigrupo y significa que se pueden omitir todos los paréntesis. Es una práctica común, especialmente en ciencias de la computación, omitir también las operaciones de modo que tanto la operación de semigrupo como la acción se indiquen por yuxtaposición. De esta manera las cadenas de cartas de S actúan sobre X , como en la expresión STX para s , t en S y X en X .
También es bastante común trabajar con actos de derecha en lugar de actos de izquierda. [2] Sin embargo, cada acto S derecho se puede interpretar como un acto izquierdo sobre el semigrupo opuesto , que tiene los mismos elementos que S, pero donde la multiplicación se define invirtiendo los factores, s • t = t • s , por lo que el dos nociones son esencialmente equivalentes. Aquí adoptamos principalmente el punto de vista de los actos de izquierda.
Actos y transformaciones
A menudo es conveniente (por ejemplo, si hay más de un acto en consideración) utilizar una letra, como , para denotar la función
definiendo el -acción y por lo tanto escribir en lugar de . Entonces para cualquier en , denotamos por
la transformación de definido por
Por la propiedad definitoria de un -actuar, satisface
Además, considere una función . Es lo mismo que(ver Curry ). Porque es una biyección, las acciones de semigrupo se pueden definir como funciones que satisface
Es decir, es una acción de semigrupo de en si y solo si es un homomorfismo de semigrupo de a la transformación completa monoide de .
S- homomorfismos
Sean X y X ′ S -actos. Entonces un S -homomorfismo de X a X ′ es un mapa
tal que
- para todos y .
El conjunto de todos esos S- homomorfismos se escribe comúnmente como.
M- homomorfismos de M -actos, para M un monoide, se definen exactamente de la misma manera.
S -Act y M -Act
Para un semigrupo fijo S , los S -actos de la izquierda son los objetos de una categoría, denominada S -Acto, cuyos morfismos son los S -homorfismos. La categoría correspondiente de la derecha S Hechos a veces se denota por Ley: S . (Esto es análogo a las categorías R -Mod y Mod- R de los módulos izquierdo y derecho sobre un anillo ).
Para un monoide M , las categorías M -Act y Act- M se definen de la misma manera.
Ejemplos de
- Cualquier semigrupo tiene una acción en , dónde . La propiedad de acción se mantiene debido a la asociatividad de.
- De manera más general, para cualquier homomorfismo de semigrupo , el semigrupo tiene una acción en dada por .
- Para cualquier conjunto , dejar ser el conjunto de secuencias de elementos de . El semigrupo tiene una acción en dada por (dónde denota repetido veces).
- El semigrupo tiene una acción correcta , dada por .
Semigrupos de transformación
A continuación se describe una correspondencia entre los semigrupos de transformación y las acciones de semigrupo. Si lo restringimos a acciones fieles de semigrupo, tiene buenas propiedades.
Cualquier semigrupo de transformación se puede convertir en una acción de semigrupo mediante la siguiente construcción. Para cualquier semigrupo de transformación de , define una acción de semigrupo de en como por . Esta acción es fiel, lo que equivale aser inyectable .
Por el contrario, para cualquier acción de semigrupo de en , define un semigrupo de transformación . En esta construcción "olvidamos" el conjunto. es igual a la imagen de. Denotemos como para ser breve. Sies inyectivo , entonces es un isomorfismo de semigrupo de a . En otras palabras, sies fiel, entonces no olvidamos nada importante. Esta afirmación se hace precisa mediante la siguiente observación: si nos volvemos volver a una acción de semigrupo de en , luego para todos . y son "isomorfos" a través de , es decir, básicamente recuperamos . Así, algunos autores [3] no ven distinción entre acciones de semigrupo fieles y semigrupos de transformación.
Aplicaciones a la informática
Semiautomas
Los semigrupos de transformación son de importancia esencial para la teoría de la estructura de las máquinas de estados finitos en la teoría de autómatas . En particular, un semiautomatón es un triple ( Σ , X , T ), donde Σ es un conjunto no vacío llamado alfabeto de entrada , X es un conjunto no vacío llamado conjunto de estados y T es una función
llamada función de transición . Los semiautomas surgen de los autómatas deterministas al ignorar el estado inicial y el conjunto de estados aceptados.
Dado un semiautomatón, sea T a : X → X , para a ∈ Σ , denote la transformación de X definida por T a ( x ) = T ( a , x ). Entonces, el semigrupo de transformaciones de X generado por { T a : a ∈ Σ } se llama el semigrupo característico o sistema de transición de ( Σ , X , T ). Este semigrupo es un monoide, por lo que este monoide se denomina monoide característico o de transición . También se ve a veces como un Σ ∗ -acto en X , donde Σ ∗ es el monoide libre de cadenas generado por el alfabeto Σ , [nota 1] y la acción de las cadenas extiende la acción de Σ a través de la propiedad
Teoría de Krohn-Rhodes
La teoría de Krohn-Rhodes, a veces también llamada teoría de los autómatas algebraicos , proporciona resultados de descomposición poderosos para semigrupos de transformación finita mediante la cascada de componentes más simples.
Notas
- ^ La operación monoide es la concatenación; el elemento de identidad es la cadena vacía.
Referencias
- AH Clifford y GB Preston (1961), The Algebraic Theory of Semigroups , volumen 1. American Mathematical Society, ISBN 978-0-8218-0272-4 .
- AH Clifford y GB Preston (1967), The Algebraic Theory of Semigroups , volumen 2. American Mathematical Society, ISBN 978-0-8218-0272-4 .
- Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs , Expositions in Mathematics 29 , Walter de Gruyter, Berlín, ISBN 978-3-11-015248-7 .
- Rudolf Lidl y Günter Pilz, Álgebra abstracta aplicada (1998), Springer, ISBN 978-0-387-98290-8