Hispanopedia Wiki
Articulo de referencia

Semigroup action

In algebra and theoretical computer science , an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in...

Hispanopedia WikiContenido en espanolLectura gratuita

In algebra and theoretical computer science, an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in such a way that the product of two elements of the semigroup (using the semigroup operation) is associated with the composite of the two corresponding transformations. The terminology conveys the idea that the elements of the semigroup are acting as transformations of the set. From an algebraic perspective, a semigroup action is a generalization of the notion of a group action in group theory. From the computer science point of view, semigroup actions are closely related to automata: the set models the state of the automaton and the action models transformations of that state in response to inputs.

An important special case is a monoid action or act, in which the semigroup is a monoid and the identity element of the monoid acts as the identity transformation of a set. From a category theoretic point of view, a monoid is a category with one object, and an act is a functor from that category to the category of sets. This immediately provides a generalization to monoid acts on objects in categories other than the category of sets.

Another important special case is a transformation semigroup. This is a semigroup of transformations of a set, and hence it has a tautological action on that set. This concept is linked to the more general notion of a semigroup by an analogue of Cayley's theorem.

(A note on terminology: the terminology used in this area varies, sometimes significantly, from one author to another. See the article for details.)

Formal definitions

Let S be a semigroup. Then a (left) semigroup action (or act) of S is a set X together with an operation • : S × X → X which is compatible with the semigroup operation ∗ as follows:

  • 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