Hispanopedia Wiki
Articulo de referencia

Acción de semigrupo

En álgebra y ciencias de la computación teórica , una acción de un semigrupo sobre un conjunto es una regla que asocia a cada elemento del semigrupo una transformación del conju...

Hispanopedia WikiContenido en espanolLectura gratuita

En álgebra y ciencias de la computación teórica , una acción 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 (mediante la operación de semigrupo ) se asocia con la composición 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 teoría de grupos . Desde el punto de vista de las ciencias de la computación, 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 la acción o acto de un 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 el punto de vista de la teoría de categorías , un monoide es una categoría con un solo objeto, y un acto es un functor de esa categoría a la categoría de conjuntos . Esto proporciona inmediatamente una generalización a actos de monoides sobre objetos en categorías distintas de la categoría de conjuntos.

Otro caso especial importante es el semigrupo de transformaciones . Este es un semigrupo de transformaciones de un conjunto y, por lo tanto, tiene una acción tautológica sobre dicho 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 este ámbito varía, a veces de forma significativa, 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 todo 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 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 ) de 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 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 puede convertirse en una acción de monoide adjuntando una identidad al semigrupo y exigiendo que actúe como la transformación identidad sobre 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 indicó anteriormente (por 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, al considerar el axioma de identidad ( e • x = x ) como vacío cuando no hay elemento identidad, o al usar el término S -acto unitario para un S -acto con identidad. [ 1 ]

La propiedad definitoria de una acción es análoga a la asociatividad de la operación de semigrupo, lo que significa que se pueden omitir todos los paréntesis. Es práctica común, especialmente en informática, omitir también las operaciones para que tanto la operación de semigrupo como la acción se indiquen por yuxtaposición. De esta forma, 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, todo acto S 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 ambas nociones son esencialmente equivalentes. Aquí adoptamos principalmente el punto de vista de los actos izquierdos.

Actos y transformaciones

A menudo resulta conveniente (por ejemplo, si hay más de un acto en consideración) utilizar una carta, como por ejemplo:T{\displaystyle T}, para denotar la función

T:S×incógnita→incógnita{\displaystyle T\colon S\times X\to X}

definiendo elS{\displaystyle S}-acción y por lo tanto escribirT(s,incógnita){\displaystyle T(s,x)}en lugar des⋅incógnita{\displaystyle s\cdot x}. Entonces, para cualquiers{\displaystyle s}enS{\displaystyle S}, lo denotamos por

Ts:incógnita→incógnita{\displaystyle T_{s}\colon X\to X}

la transformación deincógnita{\displaystyle X}definido por

Ts(incógnita)=T(s,incógnita).{\displaystyle T_{s}(x)=T(s,x).}

Por la propiedad definitoria de unS{\displaystyle S}-acto,T{\displaystyle T}Satisface

Ts∗t=Ts∘Tt.{\displaystyle T_{s*t}=T_{s}\circ T_{t}.}

Además, consideremos una funcións↦Ts{\displaystyle s\mapsto T_{s}}Es lo mismo quecurry⁡(T):S→(incógnita→incógnita){\displaystyle \operatorname {curry} (T):S\to (X\to X)}(véase Currying ). Porquecurry{\displaystyle \operatorname {curry} }es una biyección, las acciones de semigrupo se pueden definir como funcionesS→(incógnita→incógnita){\displaystyle S\to (X\to X)}que satisfacen

curry⁡(T)(s∗t)=curry⁡(T)(s)∘curry⁡(T)(t).{\displaystyle \operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).}

Eso es,T{\displaystyle T}es una acción de semigrupo deS{\displaystyle S}enincógnita{\displaystyle X}si y solo sicurry⁡(T){\displaystyle \operatorname {curry} (T)}es un homomorfismo de semigrupo deS{\displaystyle S}a la transformación completa monoide deincógnita{\displaystyle X}.

S- homomorfismos

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

F:incógnita→incógnita′{\displaystyle F\colon X\to X'}

de tal manera que

F(sincógnita)=sF(incógnita){\displaystyle F(sx)=sF(x)}a pesar des∈S{\displaystyle s\in S}yincógnita∈incógnita{\displaystyle x\in X}.

El conjunto de todos esos S -homomorfismos se escribe comúnmente comoHometroS(incógnita,incógnita′){\displaystyle \mathrm {Hom} _{S}(X,X')}.

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

Ley S y Ley M

Para un semigrupo fijo S , los actos izquierdos de S son los objetos de una categoría, denotada S -Act, cuyos morfismos son los homomorfismos de S. La categoría correspondiente de actos derechos de S se denota a veces por Act- S . (Esto es análogo a las categorías R -Mod y Mod- R de módulos izquierdos y derechos sobre un anillo ).

Para un monoide M , las categorías M -Acto y Act- M se definen de la misma manera.

Ejemplos

  • Cualquier semigrupo(S,∗){\displaystyle (S,*)}tiene una acción enS{\displaystyle S}, dónde⋅=∗{\displaystyle \cdot =*}La propiedad de acción se cumple debido a la asociatividad de∗{\displaystyle *}.
  • De manera más general, para cualquier homomorfismo de semigrupoF:(S,∗)→(T,⊕){\displaystyle F\colon (S,*)\rightarrow (T,\oplus )}, el semigrupo(S,∗){\displaystyle (S,*)}tiene una acción enT{\displaystyle T}dado pors⋅t=F(s)⊕t{\displaystyle s\cdot t=F(s)\oplus t}.
  • Para cualquier conjuntoincógnita{\displaystyle X}, dejarincógnita∗{\displaystyle X^{*}}sea ​​el conjunto de secuencias de elementos deincógnita{\displaystyle X}. El semigrupo(norte,×){\displaystyle (\mathbb {N} ,\times )}tiene una acción enincógnita∗{\displaystyle X^{*}}dado pornorte⋅s=snorte{\displaystyle n\cdot s=s^{n}}(dóndesnorte{\displaystyle s^{n}}denotas{\displaystyle s}repetidonorte{\displaystyle n}veces).
  • El semigrupo(norte,×){\displaystyle (\mathbb {N} ,\times )}tiene la acción correcta(norte,⋅){\displaystyle (\mathbb {N} ,\cdot )}, dado porincógnita⋅y=incógnitay{\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 semigrupo. Si la restringimos a acciones de semigrupo fieles , presenta propiedades interesantes.

Cualquier semigrupo de transformación puede convertirse en una acción de semigrupo mediante la siguiente construcción. Para cualquier semigrupo de transformaciónS{\displaystyle S}deincógnita{\displaystyle X}, definir una acción de semigrupoT{\displaystyle T}deS{\displaystyle S}enincógnita{\displaystyle X}comoT(s,incógnita)=s(incógnita){\displaystyle T(s,x)=s(x)}paras∈S,incógnita∈incógnita{\displaystyle s\in S,x\in X}Esta acción es fiel, lo cual es equivalente adotúrry(T){\displaystyle curry(T)}ser inyectivo .

Por el contrario, para cualquier acción de semigrupoT{\displaystyle T}deS{\displaystyle S}enincógnita{\displaystyle X}, definir un semigrupo de transformaciónS′={Ts∣s∈S}{\displaystyle S'=\{T_{s}\mid s\in S\}}En esta construcción "olvidamos" el conjuntoS{\displaystyle S}.S′{\displaystyle S'}es igual a la imagen dedotúrry(T){\displaystyle curry(T)}Denotemos .dotúrry(T){\displaystyle curry(T)}comoF{\displaystyle f}para abreviar. SiF{\displaystyle f}es inyectivo , entonces es un isomorfismo de semigrupos deS{\displaystyle S}aS′{\displaystyle S'}. En otras palabras, siT{\displaystyle T}es fiel, entonces no olvidamos nada importante. Esta afirmación se precisa con la siguiente observación: si giramosS′{\displaystyle S'}De vuelta a una acción de semigrupoT′{\displaystyle T'}deS′{\displaystyle S'}enincógnita{\displaystyle X}, entoncesT′(F(s),incógnita)=T(s,incógnita){\displaystyle T'(f(s),x)=T(s,x)}a pesar des∈S,incógnita∈incógnita{\displaystyle s\in S,x\in X}.T{\displaystyle T}yT′{\displaystyle T'}son "isomórficos" a través deF{\displaystyle f}, es decir, esencialmente nos recuperamosT{\displaystyle T}. Por lo tanto, algunos autores [ 3 ] no ven distinción entre acciones de semigrupos fieles y semigrupos de transformación.

Aplicaciones a la informática

Semiautómatas

Los semigrupos de transformación son de vital importancia 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 tripleta (Σ, 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

T:Σ×incógnita→incógnita{\displaystyle T\colon \Sigma \times X\to X}

llamada función de transición . Los semiautómatas surgen de los 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 considera a veces como una Σ ∗ -acción sobre X , donde Σ ∗ es el monoide libre de cadenas generado por el alfabeto Σ, [ nota 1 ] y la acción de cadenas extiende la acción de Σ a través de la propiedad

Tvw=Tw∘Tv.{\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 resultados de descomposición potentes para semigrupos de transformación finitos mediante la cascada de componentes más simples.

Notas

  1. ↑ La operación monoide es la concatenación; el elemento neutro 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), 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), Monoides, actos y categorías: con aplicaciones a productos de coronas y grafos , 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
Obtenido de " https://en.wikipedia.org/w/index.php?title=Semigroup_action&oldid=1332464196 "
Lecturas relacionadas
6 articulos
ÁlgebraÁlgebraEl álgebra es la rama de las matemáticas que estudia ciertos sistemas abstractos , conocidos como estructuras algebraicas , y la manipulación de en...Informática teóricaLa informática teórica es un subcampo de la informática y las matemáticas que se centra en los fundamentos abstractos y matemáticos de la computaci...SemigrupoSemigrupoEn matemáticas, un semigrupo es una estructura algebraica que consiste en un conjunto junto con una operación binaria interna asociativa sobre él.Conjunto (matemáticas)Un conjunto de polígonos en un diagrama de Euler Este conjunto es igual al representado arriba ya que ambos tienen los mismos elementos. En matemát...Transformación geométricaEn matemáticas , una transformación geométrica es cualquier biyección de un conjunto a sí mismo (o a otro conjunto similar) con algún fundamento ge...Operación binariaOperación binariaEn matemáticas , una operación binaria u operación diádica es una regla para combinar dos elementos (llamados operandos ) para producir otro elemen...