Mängd ändliga semigrupper

I matematik , och mer exakt inom semigruppteorin , är en mängd ändliga semigrupper en klass av semigrupper som har några fina algebraiska egenskaper. Dessa klasser kan definieras på två distinkta sätt, med antingen algebraiska eller topologiska föreställningar. Varieteter av finita monoider , varianter av finita ordnade semigrupper och varianter av finita ordnade monoider definieras på liknande sätt.

Denna uppfattning är mycket lik den allmänna uppfattningen om variation i universell algebra.

Definition

Två likvärdiga definitioner ges nu.

Algebraisk definition

En variation V av ändliga (ordnade) semigrupper är en klass av ändliga (ordnade) semigrupper som:

är stängd under division .
är stängt för att ta ändliga kartesiska produkter.

Det första villkoret är likvärdigt med att ange att V är stängt för att ta delsemigrupper och ta kvoter. Den andra egenskapen innebär att den tomma produkten - det vill säga den triviala halvgruppen av ett element - tillhör varje sort. Därför är en sort nödvändigtvis icke-tom.

En mängd ändliga (ordnade) monoider är en mängd finita (ordnade) semigrupper vars element är monoider. Det vill säga, det är en klass av (ordnade) monoider som uppfyller de två ovan angivna villkoren.

Topologisk definition

För att ge den topologiska definitionen av en mängd finita semigrupper behövs några andra definitioner relaterade till profinita ord .

Låt A vara ett godtyckligt ändligt alfabet . Låt A ⁺ vara dess fria halvgrupp . Låt sedan ${\hat {A}}$ vara uppsättningen av profinita ord över A . Givet en semigruppmorfism ϕ $\displaystyle \phi :A^{+}\to S}$ , låt ${\hat {\phi }}:{\hat { A}}\to S$ vara den unika kontinuerliga förlängningen av $\phi$ till ${\hat {A}}$ .

En profinit identitet är ett par u och v av profinita ord. En halvgrupp S sägs uppfylla den profinita identiteten u = v om, för varje semigruppmorfism $\phi :A^{+}\to S$ , likheten ${\hat {\phi }}(u)={\hat {\phi }}(v)$ gäller.

En mängd finita semigrupper är klassen av finita semigrupper som uppfyller en uppsättning profinita identiteter P .

En variation av ändliga monoider definieras som en mängd ändliga semigrupper, med skillnaden att man bör betrakta monoida morfismer $\phi :A^{*}\to M$ istället för semigruppmorfismer $\phi :A^{+}\to M$ .

En mängd ändligt ordnade semigrupper/monoider ges också med en liknande definition, med skillnaden att man bör överväga morfismer av ordnade semigrupper/monoider.

Exempel

Några exempel på klasser av semigrupper ges. De första exemplen använder finita identiteter – det vill säga profinita identiteter vars två ord är finita ord. Nästa exempel använder profinita identiteter. Den sista är ett exempel på en klass som inte är en sort.

Fler exempel ges i artikeln Special classes of semigroups .

Använda ändliga identiteter

Det mest triviala exemplet är sorten S av alla finita semigrupper. Denna variation definieras av den tomma uppsättningen av profinita jämlikheter. Det är trivialt att se att denna klass av ändliga halvgrupper är stängda under underhalvgrupper, ändliga produkter och kvoter.
Det näst mest triviala exemplet är sort 1 som endast innehåller den triviala halvgruppen. Denna variation definieras av uppsättningen av profinita likheter { x = y }. Intuitivt säger denna jämlikhet att alla element i halvgruppen är lika. Denna klass är trivialt stängd under underhalvgrupper, ändliga produkter och kvoter.
Variationen Com av kommutativa finita semigrupper definieras av den profinita likheten xy = yx . Intuitivt säger denna jämlikhet att varje par av element i semigruppen pendlar.
Variationen av idempotenta finita semigrupper definieras av den profinita likheten xx = x .

Mer generellt, givet ett profinit ord u och en bokstav x , anger den profinita likheten ux = xu att uppsättningen av möjliga bilder av u endast innehåller element av centraliseraren. På liknande sätt ux = x att uppsättningen möjliga bilder av u endast innehåller vänsteridentiteter. Slutligen ux = u att mängden möjliga bilder av u är sammansatt av vänsternollor.

Använda profisionella identiteter

Exempel på profinita ord som inte är finita ges nu.

Givet ett profinit ord, x , låt $x^{\omega }$ beteckna $\lim _{n\to \infty }x^{n!}$ . Därför, givet en semigruppmorfism $\phi :A^{+}\to S$ , ${\hat {\phi }}(x^{\ omega })$ är den enda idempotenta styrkan av $\phi (x)$ . Således, i profinita likheter, $x^{\omega }$ en godtycklig idempotent.

Klassen G av ändliga grupper är en mängd ändliga semigrupper. Observera att en ändlig grupp kan definieras som en ändlig halvgrupp, med en unik idempotent, som dessutom är en vänster- och högeridentitet. När de två egenskaperna väl har översatts i termer av profinit likhet kan man se att sorten G definieras av uppsättningen av profinita likheter $\{x^{\omega }=y^{\omega }{\text{ och }}x^{\omega }y=yx^{\omega }=y\}.$

Klasser som inte är sorter

Observera att klassen av ändliga monoider inte är en mängd ändliga semigrupper. Den här klassen är faktiskt inte stängd under undersemigrupper. För att se detta, ta valfri ändlig halvgrupp S som inte är en monoid. Det är en underhalvgrupp av monoiden Si ^bildad genom att angränsa ett identitetselement.

Reitermans teorem

Reitermans teorem säger att de två definitionerna ovan är likvärdiga. Ett schema över beviset ges nu.

Givet en mängd V av semigrupper som i den algebraiska definitionen, kan man välja uppsättningen P av profinita identiteter för att vara den uppsättning av profinita identiteter som tillfredsställs av varje semigrupp av V .

Återigen, givet en profinit identitet u = v , kan man anmärka att klassen av semigrupper som uppfyller denna profinita identitet är stängd under subsemigrupper, kvoter och finita produkter. Således är denna klass en mängd ändliga semigrupper. under godtycklig skärningspunkt, och givet en godtycklig uppsättning P av profinita identiteter ui ⁼ v ⁱ , är klassen av semigrupper som uppfyller P skärningspunkten för klassen av semigrupper som uppfyller alla dessa profinita identiteter. Det vill säga, det är en skärningspunkt av varianter av ändliga semigrupper, och detta är en mängd ändliga semigrupper.

Jämförelse med begreppet variation av universell algebra

Definitionen av en mängd ändliga semigrupper är inspirerad av föreställningen om en mängd olika universella algebror . Vi minns definitionen av en sort i universell algebra. En sådan sort är på motsvarande sätt:

en klass av strukturer, stängda under homomorfa bilder, subalgebror och (direkta) produkter .
en klass av strukturer som tillfredsställer en uppsättning identiteter .

De huvudsakliga skillnaderna mellan de två begreppen variation ges nu. I det här avsnittet betyder "variation av (godtyckliga) semigrupper" "klassen av semigrupper som en variation av universell algebra över vokabulären för en binär operator". Det följer av definitionerna av dessa två sorters varianter att, för varje sort V av (godtyckliga) semigrupper, är klassen av ändliga semigrupper av V en variation av ändliga semigrupper.

Vi ger först ett exempel på en variation av ändliga semigrupper som inte liknar någon undervarietet av variationen av (godtyckliga) semigrupper. Vi ger sedan skillnaden mellan de två definitionerna med hjälp av identiteter. Slutligen ger vi skillnaden mellan de algebraiska definitionerna.

Som visas ovan är klassen av ändliga grupper en mängd ändliga semigrupper. Klassen av grupper är dock inte en undervarietet av variationen av (godtyckliga) semigrupper. Faktum är att $\langle \mathbb {Z} ,+\rangle$ är en monoid som är en oändlig grupp. Däremot är dess submonoid $\langle \mathbb {N} ,+\rangle$ inte en grupp. Eftersom klassen av (godtyckliga) grupper innehåller en halvgrupp och inte innehåller en av dess undersemigrupper, är den inte en varietet. Huvudskillnaden mellan det finita fallet och det oändliga fallet, när grupper beaktas, är att en submonoid i en finit grupp är en finit grupp. Medan oändliga grupper inte är stängda under tar submonoider.

Klassen av ändliga grupper är en variation av ändliga semigrupper, medan den inte är en undervarietet av variationen av (godtyckliga) semigrupper. Således visar Reitermans teorem att denna klass kan definieras med hjälp av profinita identiteter. Och Birkhoffs HSP-sats visar att denna klass inte kan definieras med identiteter (av ändliga ord). Detta illustrerar varför definitionen av en mängd ändliga semigrupper använder begreppet profinita ord och inte begreppet identiteter.

Vi överväger nu de algebraiska definitionerna av sorter. Att kräva att sorter är stängda under godtyckliga direkta produkter innebär att en sort antingen är trivial eller innehåller oändliga strukturer. För att begränsa varieteter till att endast innehålla finita strukturer använder definitionen av variation av finita semigrupper begreppet ändlig produkt istället för begreppet godtycklig direkt produkt.

Pin, Jean-Éric (2016-11-30). Matematiska grunder för automatteorin (PDF) . s. 141–160.
Pin, Jean-Éric (1986). Variationer av formellt språk . New York: Plenum Publishing Corp.
Eilenberg, S (1976). Automater, språk och maskiner . New york: Harcourt Brace Jovanovich Publishers. s. kapitlen "Depth Decomposition theorem" och "Komplexitet av semigrupper och morfismer".
Almeida, J (1994). Finita semigrupper och universell algebra . Rivere Edge, NJ: World Scientific Publishing Co. Inc.