Acción de semigrupo

Una acción o acto de un semigrupo sobre un conjunto

En álgebra y en 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 manera que el producto de dos elementos del semigrupo (utilizando la operación de semigrupo ) se asocia 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 de acció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 identidad del monoide actúa como la transformación identidad de un conjunto. Desde un punto de vista de la teoría de categorías , 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 a los actos monoides sobre objetos en categorías distintas a la categoría de conjuntos.

Otro caso especial importante es el semigrupo de transformaciones . Se trata de un semigrupo de transformaciones de un conjunto y, por lo tanto, tiene una acción tautológica sobre ese conjunto. Este concepto está vinculado a la noción más general de semigrupo mediante un análogo del teorema de Cayley .

(Nota sobre la 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 (izquierdo) de S es un conjunto X junto con una operación • : S × X → X que es compatible con la operación de semigrupo ∗ como sigue:

• para todos los s , t en S y x en X , s • ( t • x ) = ( s ∗ t ) • x .

Este es el análogo en la teoría de semigrupos de una acción de grupo (izquierda) , y es equivalente a un homomorfismo de semigrupo en el conjunto de funciones en X. Las acciones de semigrupo derechas se definen de manera similar utilizando 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 (izquierdo) de M es una acción de semigrupo (izquierdo) 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 como resultado un homomorfismo de monoide. Las acciones de monoide derecho se definen de manera similar. Un monoide M con una acción sobre un conjunto también se denomina monoide operador .

Una acción de semigrupo de S sobre X se puede convertir en un acto monoide adjuntando una identidad al semigrupo y requiriendo que actúe como la transformación identidad en X.

Terminología y notación

Si S es un semigrupo o un monoide, entonces un conjunto X sobre el cual S actúa como se indica arriba (a la izquierda, por ejemplo) también se conoce como S -acto (izquierdo) , S -conjunto , S -acción , S -operando o acto izquierdo sobre S. Algunos autores no distinguen entre acciones de semigrupo y de monoide, considerando el axioma de identidad ( e • x = x ) como vacío cuando no hay ningún elemento identidad, o usando el término S -acto unitario para un S -acto con una 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 informática, 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 letras 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 derechos en lugar de actos izquierdos. ^[2] Sin embargo, cada S-acto derecho puede interpretarse 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 las dos nociones son esencialmente equivalentes. Aquí adoptamos principalmente el punto de vista de los actos izquierdos.

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. ${\displaystyle T}$

${\displaystyle T\colon S\times X\to X}$

definiendo la -acción y por lo tanto escribimos en lugar de . Entonces, para cualquier en , denotamos por ${\displaystyle S}$ ${\displaystyle T(s,x)}$ ${\displaystyle s\cdot x}$ ${\displaystyle s}$ ${\displaystyle S}$

${\displaystyle T_{s}\colon X\to X}$

La transformación de definida por ${\displaystyle X}$

${\displaystyle T_{s}(x)=T(s,x).}$

Por la propiedad definitoria de un -acto, se satisface ${\displaystyle S}$ ${\displaystyle T}$

${\displaystyle T_{s*t}=T_{s}\circ T_{t}.}$

Además, considere una función . Es lo mismo que (ver Currying ). Debido a que es una biyección, las acciones de semigrupo se pueden definir como funciones que satisfacen ${\displaystyle s\mapsto T_{s}}$ ${\displaystyle \operatorname {curry} (T):S\to (X\to X)}$ ${\displaystyle \operatorname {curry} }$ ${\displaystyle S\to (X\to X)}$

${\displaystyle \operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).}$

Es decir, es una acción de semigrupo de sobre si y sólo si es un homomorfismo de semigrupo de al monoide de transformación completa de . ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle \operatorname {curry} (T)}$ ${\displaystyle S}$ ${\displaystyle X}$

S-homomorfismos

Sean X y X ′ S -actos. Entonces un S -homomorfismo de X a X ′ es una función

${\displaystyle F\colon X\to X'}$

de tal manera que

${\displaystyle F(sx)=sF(x)}$para todos y . ${\displaystyle s\in S}$ ${\displaystyle x\in X}$

El conjunto de todos estos S -homomorfismos se escribe comúnmente como . ${\displaystyle \mathrm {Hom} _{S}(X,X')}$

Los M -homomorfismos de M- actos, para M un monoide, se definen exactamente de la misma manera.

S-Actuar yMETRO-Acto

Para un semigrupo fijo S , los S -actos izquierdos son los objetos de una categoría, denotada S -Act, cuyos morfismos son los S -homomorfismos. La categoría correspondiente de los S -actos derechos a veces se denota por Act- 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

• Cualquier semigrupo tiene una acción sobre , donde . La propiedad de acción se cumple debido a la asociatividad de . ${\displaystyle (S,*)}$ ${\displaystyle S}$ ${\displaystyle \cdot =*}$ ${\displaystyle *}$
• De manera más general, para cualquier homomorfismo de semigrupo , el semigrupo tiene una acción sobre dada por . ${\displaystyle F\colon (S,*)\rightarrow (T,\oplus )}$ ${\displaystyle (S,*)}$ ${\displaystyle T}$ ${\displaystyle s\cdot t=F(s)\oplus t}$
• Para cualquier conjunto , sea el conjunto de sucesiones de elementos de . El semigrupo tiene una acción sobre dada por (donde denota tiempos repetidos ). ${\displaystyle X}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle (\mathbb {N} ,\times )}$ ${\displaystyle X^{*}}$ ${\displaystyle n\cdot s=s^{n}}$ ${\displaystyle s^{n}}$ ${\displaystyle s}$ ${\displaystyle n}$
• El semigrupo tiene una acción derecha , dada por . ${\displaystyle (\mathbb {N} ,\times )}$ ${\displaystyle (\mathbb {N} ,\cdot )}$ ${\displaystyle x\cdot y=x^{y}}$

Semigrupos de transformación

A continuación se describe una correspondencia entre semigrupos de transformación y acciones de semigrupos. Si la restringimos a acciones de semigrupos fieles , 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 , defina una acción de semigrupo de en como para . Esta acción es fiel, lo que equivale a ser inyectiva . ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle T(s,x)=s(x)}$ ${\displaystyle s\in S,x\in X}$ ${\displaystyle curry(T)}$

Por el contrario, para cualquier acción de semigrupo de en , definamos un semigrupo de transformación . En esta construcción "olvidamos" el conjunto . es igual a la imagen de . Denotemos como por brevedad. Si es inyectiva , entonces es un isomorfismo de semigrupo de a . En otras palabras, si es fiel, entonces no olvidamos nada importante. Esta afirmación se hace precisa por la siguiente observación: si volvemos a una acción de semigrupo de en , entonces para todos . y son "isomorfos" a través de , es decir, esencialmente recuperamos . Así, algunos autores ^[3] no ven distinción entre acciones de semigrupo fieles y semigrupos de transformación. ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle S'=\{T_{s}\mid s\in S\}}$ ${\displaystyle S}$ ${\displaystyle S'}$ ${\displaystyle curry(T)}$ ${\displaystyle curry(T)}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle S}$ ${\displaystyle S'}$ ${\displaystyle T}$ ${\displaystyle S'}$ ${\displaystyle T'}$ ${\displaystyle S'}$ ${\displaystyle X}$ ${\displaystyle T'(f(s),x)=T(s,x)}$ ${\displaystyle s\in S,x\in X}$ ${\displaystyle T}$ ${\displaystyle T'}$ ${\displaystyle f}$ ${\displaystyle T}$

Aplicaciones a la informática

Semiautomáticos

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 semiautómata es una terna (Σ, 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

${\displaystyle T\colon \Sigma \times X\to X}$

llamada función de transición . Los semiautómatas surgen de autómatas deterministas al ignorar el estado inicial y el conjunto de estados aceptados.

Dado un semiautómata, sea T _a : X → X , para a ∈ Σ, 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 semigrupo característico o sistema de transición de (Σ, X , T ). Este semigrupo es un monoide, por lo que este monoide se llama monoide característico o de transición . También se lo ve a veces como un Σ ^∗ -acto sobre 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

${\displaystyle T_{vw}=T_{w}\circ T_{v}.}$

Teoría de Krohn-Rhodes

La teoría de Krohn-Rhodes, a veces también llamada teoría de autómatas algebraicos , proporciona potentes resultados de descomposición para semigrupos de transformación finitos mediante la conexión en cascada de componentes más simples.

Notas

1. La operación monoide es la concatenación; el elemento identidad es la cadena vacía.

Referencias

1. Kilp, Knauer y Mikhalev, 2000, páginas 43–44.
2. Kilp, Knauer y Mikhalev, 2000.
3. Arbib, Michael A., ed. (1968). Teoría algebraica de máquinas, lenguajes y semigrupos . Nueva York y Londres: Academic Press. pág. 83.

• AH Clifford y GB Preston (1961), La teoría algebraica de semigrupos , volumen 1. American Mathematical Society, ISBN 978-0-8218-0272-4 . 
• AH Clifford y GB Preston (1967), La teoría algebraica de semigrupos , volumen 2. American Mathematical Society, ISBN 978-0-8218-0272-4 . 
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoides, actos y categorías: con aplicaciones a productos de corona y gráficos , Exposiciones en matemáticas 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