Semigruppsåtgärd

Inom algebra och teoretisk datavetenskap är en handling eller handling av en halvgrupp på en mängd en regel som associerar till varje element i halvgruppen en transformation av mängden på ett sådant sätt att produkten av två element i halvgruppen (med hjälp av halvgruppen operation ) är associerad med sammansättningen av de två motsvarande transformationerna. Terminologin förmedlar tanken att halvgruppens element fungerar som transformationer av mängden. Ur ett algebraiskt perspektiv är en semigrupphandling en generalisering av begreppet grupphandling i gruppteorin . Ur datavetenskaplig synvinkel är halvgruppshandlingar nära besläktade med automater : uppsättningen modellerar automatens tillstånd och handlingsmodellerna transformationer av det tillståndet som svar på indata.

Ett viktigt specialfall är en monoid handling eller handling , där semigruppen är en monoid och identitetselementet för monoiden fungerar som identitetstransformationen av en mängd. Ur en kategoriteoretisk synvinkel är en monoid en kategori med ett objekt, och en akt är en funktion från den kategorin till kategorin uppsättningar . Detta ger omedelbart en generalisering till monoida handlingar på objekt i andra kategorier än kategorin av uppsättningar.

Ett annat viktigt specialfall är en transformationssemigrupp . Detta är en halvgrupp av transformationer av en uppsättning, och därför har den en tautologisk verkan på den uppsättningen. Detta koncept är kopplat till den mer allmänna uppfattningen om en halvgrupp genom en analog till Cayleys sats .

(En anmärkning om terminologi: terminologin som används inom detta område varierar, ibland avsevärt, från en författare till en annan. Se artikeln för detaljer.)

Formella definitioner

Låt S vara en halvgrupp. Då är en (vänster) halvgruppsåtgärd (eller handling ) av S en mängd X tillsammans med en operation • : S × X → X som är kompatibel med semigruppoperationen ∗ enligt följande:

för alla s , t i S och x i X , s • ( t • x ) = ( s ∗ t ) • x .

Detta är analogen i semigruppteorin till en (vänster) grupphandling , och är ekvivalent med en semigrupphomomorfism i uppsättningen funktioner på X . Höger halvgruppsåtgärder definieras på liknande sätt med en operation • : X × S → X som uppfyller ( x • a ) • b = x • ( a ∗ b ) .

Om M är en monoid, så är en (vänster) monoid verkan (eller akt ) av M en (vänster) halvgruppsverkan av M med den ytterligare egenskapen

för alla x i X : e • x = x

där e är identitetselementet för M . Detta ger på motsvarande sätt en monoid homomorfism. Rätt monoida handlingar definieras på liknande sätt. En monoid M med en verkan på en uppsättning kallas också en operator monoid .

En semigrupphandling av S på X kan göras till monoid handling genom att angränsa en identitet till semigruppen och kräva att den fungerar som identitetstransformationen på X .

Terminologi och notation

Om S är en halvgrupp eller monoid, så är en mängd X där S fungerar som ovan (till vänster, säg) också känd som en (vänster) S -akt , S -mängd , S -action , S -operand , eller vänster agera över S . Vissa författare skiljer inte mellan halvgrupps- och monoida handlingar, genom att betrakta identitetsaxiomet ( e • x = x ) som tomt när det inte finns något identitetselement, eller genom att använda termen enhetlig S -akt för en S -akt med en identitet.

Den definierande egenskapen för en handling är analog med associativiteten för semigruppoperationen, och innebär att alla parenteser kan utelämnas. Det är vanlig praxis, särskilt inom datavetenskap, att utelämna operationerna också så att både semigruppoperationen och handlingen indikeras genom sida. På så sätt verkar strängar av bokstäver från S på X , som i uttrycket stx för s , t i S och x i X .

Det är också ganska vanligt att man arbetar med högerakter snarare än vänsterakter. Varje höger S-akt kan dock tolkas som en vänsterakt över den motsatta halvgruppen , som har samma element som S, men där multiplikation definieras genom att vända om faktorerna, s • t = t • s , så de två begreppen är väsentligen likvärdig. Här antar vi i första hand vänsteragerandes synvinkel.

Handlingar och förvandlingar

Det är ofta bekvämt (till exempel om det finns mer än en akt under övervägande) att använda en bokstav, som $T$ , för att beteckna funktionen

T\colon S\ gånger X\till X

definiera $S$ -åtgärden och skriv därför $T(s,x)$ istället för $s\cdot x$ . Sedan för alla $s$ i $S$ anger vi med

T_{s}\colon X\to X

transformationen av $X$ definierad av

T_{s}(x)=T(s,x).

Genom den definierande egenskapen för en $S$ -akt, uppfyller $T$

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

Betrakta vidare en funktion $s\mapsto T_{s}$ . Det är samma sak som $\operatorname {curry} (T):S\to (X\to X)$ (se Currying ). Eftersom $\operatorname {curry}$ är en bijektion, kan semigruppåtgärder definieras som funktioner $S\to (X\to X)$ som uppfyller

\operatörsnamn {curry} (T)(s*t)=\operatörsnamn {curry} (T)(s)\circ \operatörsnamn {curry} (T)(t).

Det vill säga, $T$ är en halvgruppsåtgärd av $S$ på $X$ om och endast om $\operatorname {curry} (T)$ är en semigroup homomorphism från $S$ till den fullständiga transformationsmonoiden av $X$ .

S -homomorfismer

Låt X och X ′ vara S -akter. Då är en S -homomorfism från X till X ′ en karta

F\colon X\to X'

Så att

F(sx)=sF(x)

för alla

s\in S

och

x\in X

.

Mängden av alla sådana S -homomorfismer skrivs vanligtvis som $\mathrm {Hom} _{S}(X,X')$ .

M -homomorfismer av M -akter, för M en monoid, definieras på exakt samma sätt.

S -Act och M -Act

För en fast halvgrupp S är de vänstra S -akterna objekten i en kategori, betecknad S -Act, vars morfismer är S -homomorfismerna. Motsvarande kategori av rätt S -akter betecknas ibland med Act- S . (Detta är analogt med kategorierna R -Mod och Mod- R för vänster och höger moduler över en ring .)

För en monoid M definieras kategorierna M -Act och Act- M på samma sätt.

Exempel

Vilken semigrupp som helst $(S,*)$ har en åtgärd på $S$ , där $\cdot =*$ . Action-egenskapen gäller på grund av associativiteten för $*$ .
Mer allmänt, för varje semigrupphomomorfism $F\colon (S,*)\rightarrow (T,\oplus )$ , semigruppen ${\ displaystyle (S,*)}$ har en åtgärd på $T$ som ges av $s\cdot t=F(s)\oplus t$ .
För varje uppsättning $X$ , låt $X^{*}$ vara uppsättningen av sekvenser av element i $X$ . Halvgruppen $(\mathbb {N} ,\times )$ har en åtgärd på $X^{*}$ som ges av $n\cdot s=s^{n}$ (där $s^{n}$ anger $s$ som upprepas $n$ gånger).
Halvgruppen $(\mathbb {N} ,\times )$ har en rätt åtgärd $(\mathbb {N} ,\cdot )$ , given av $x\cdot y=x^{y}$ .

Transformationssemigrupper

En överensstämmelse mellan transformationssemigrupper och semigruppåtgärder beskrivs nedan. Om vi begränsar det till trogna semigrupphandlingar, har det fina egenskaper.

Varje transformationssemigrupp kan omvandlas till en semigruppåtgärd genom följande konstruktion. För $T(s,x)=s(x)$ transformationssemigrupp $S$ av $X$ , definiera en semigruppåtgärd $T$ av $S$ på $X$ som för $s\in S,x\in X$ . Denna åtgärd är trogen, vilket motsvarar att $\displaystyle curry(T)}$ { är .

Omvänt, för varje semigruppåtgärd $T$ av $S$ på $X$ , definiera en transformationssemigrupp $S'=\{ T_{s}\mid s\in S\}$ . I denna konstruktion "glömmer" vi mängden $S$ . $S'$ är lika med bilden av $curry(T)$ . Låt oss beteckna $curry(T)$ som $f$ korthetens skull. Om $f$ är injektiv , så är det en semigruppisomorfism från S $\displaystyle S}$ till $S'$ . Med andra ord, om $T$ är trogen, glömmer vi inget viktigt. Detta påstående preciseras av följande observation: om vi gör $S'$ tillbaka till en halvgruppsåtgärd $T'$ av $S'$ på $X$ , sedan $T'(f(s),x)=T(s,x)$ för alla $s\in S,x\in X$ . $T$ och $T'$ är "isomorfa" via $f$ , dvs vi återställde i huvudsak $T$ . Således ser vissa författare ingen skillnad mellan trogna semigrupphandlingar och transformationssemigrupper.

Ansökningar till datavetenskap

Halvautomater

Transformationssemigrupper är av väsentlig betydelse för strukturteorin för finita tillståndsmaskiner inom automatteorin . I synnerhet är en halvautomat en trippel (Σ, X , T ), där Σ är en icke-tom mängd som kallas ingångsalfabetet , X är en icke-tom mängd som kallas mängden tillstånd och T är en funktion

T\colon \Sigma \times X\to X

kallas övergångsfunktionen . Halvautomater uppstår från deterministiska automater genom att ignorera initialtillståndet och uppsättningen av accepttillstånd.

Givet en halvautomat, låt _T a _: X → X , för en ∈ Σ, beteckna transformationen av X definierad av Ta ( x ) = T ( a , x ). Sedan kallas halvgruppen av transformationer av X som genereras av { T _a : a ∈ Σ} den karakteristiska semigruppen eller övergångssystemet för (Σ, X , T ). Denna halvgrupp är en monoid, så denna monoid kallas den karakteristiska eller övergångsmonoiden . Det ses också ibland som en Σ ^∗ -akt på X , där Σ ^∗ är den fria monoiden av strängar som genereras av alfabetet Σ, och strängarnas verkan förlänger verkan av Σ via egenskapen

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

Krohn–Rhodes teori

Krohn–Rhodes teori, ibland även kallad algebraisk automatteori , ger kraftfulla nedbrytningsresultat för finita transformationssemigrupper genom att kaskadkoppla enklare komponenter.

Anteckningar

AH Clifford och GB Preston (1961), The Algebraic Theory of Semigroups , volym 1. American Mathematical Society, ISBN 978-0-8218-0272-4 .
AH Clifford och GB Preston (1967), The Algebraic Theory of Semigroups , volym 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, Berlin, ISBN 978-3-11-015248-7 .
Rudolf Lidl och Günter Pilz, Applied Abstract Algebra (1998), Springer, ISBN 978-0-387-98290-8