Bicyklisk halvgrupp
Inom matematiken är den bicykliska semigruppen ett algebraiskt objekt som är viktigt för strukturteorin för semigrupper . Även om det i själva verket är en monoid , kallas det vanligtvis för en halvgrupp. Det är kanske lättast att förstå som den syntaktiska monoiden som beskriver Dyckspråket med balanserade par av parenteser. Således hittar den vanliga tillämpningar inom kombinatorik , som att beskriva binära träd och associativa algebror .
Historia
Den första publicerade beskrivningen av detta föremål gavs av Evgenii Lyapin 1953. Alfred H. Clifford och Gordon Preston hävdar att en av dem, som arbetade med David Rees , upptäckte det självständigt (utan publicering) någon gång före 1943.
Konstruktion
Det finns åtminstone tre standardsätt att konstruera den bicykliska halvgruppen och olika notationer för att referera till den. Lyapin kallade det P ; Clifford och Preston använde ; och de senaste tidningarna har tenderat att använda B . Den här artikeln kommer att använda den moderna stilen genomgående.
Från en gratis semigrupp
Den bicykliska halvgruppen är kvoten av den fria monoiden på två generatorer p och q av kongruensen som genereras av relationen p q = 1. Varje halvgruppselement är således en sträng av dessa två bokstäver, med förbehållet att underföljden " p q " dyker inte upp. Semigruppoperationen är sammanlänkning av strängar, vilket är tydligt associativt . Det kan då visas att alla element i B faktiskt har formen q a p b , för vissa naturliga tal a och b . Sammansättningsoperationen förenklar till
- ( q a p b ) ( q c p d ) = q a + c − min{ b , c } p d + b − min{ b , c } .
Från beställda par
Det sätt på vilket dessa exponenter är begränsade antyder att " p- och q -strukturen" kan förkastas, vilket bara lämnar operationer på " a- och b "-delen. Så B är halvgruppen av par av naturliga tal (inklusive noll), med operation
- ( a , b ) ( c , d ) = ( a + c − min{ b , c }, d + b − min{ b , c }).
Detta är tillräckligt för att definiera B så att det är samma objekt som i den ursprungliga konstruktionen. Precis som p och q genererade B ursprungligen, med den tomma strängen som monoid identitet , har denna nya konstruktion av B generatorer (1, 0) och (0, 1), med identitet (0, 0).
Från funktioner
Det kan visas att vilken semigrupp S som helst som genereras av elementen e , a och b som uppfyller påståendena nedan är isomorf till den bicykliska semigruppen.
- a e = e a = a
- b e = e b = b
- a b = e
- b a ≠ e
Det är inte helt självklart att så ska vara fallet — den svåraste uppgiften är kanske att förstå att S måste vara oändlig. För att se detta, anta att a (säg) inte har oändlig ordning, så a k + h = a h för vissa h och k . Då a k = e , och
- b = e b = a k b = a k - 1 e = a k - 1 ,
så
- b a = a k = e ,
vilket inte är tillåtet - så det finns oändligt många distinkta krafter av en . Det fullständiga beviset ges i Clifford och Prestons bok.
Observera att de två definitionerna ovan båda uppfyller dessa egenskaper. Ett tredje sätt att härleda B använder två lämpligt valda funktioner för att ge den bicykliska halvgruppen som en monoid av transformationer av de naturliga talen. Låt α, β och ι vara element i transformationssemigruppen på de naturliga talen, där
- ι( n ) = n
- α( n ) = n + 1
- β( n ) = 0 om n = 0, och n − 1 annars.
Dessa tre funktioner har de egenskaper som krävs, så halvgruppen de genererar är B .
Egenskaper
Den bicykliska semigruppen har egenskapen att bilden av någon homomorfism φ från B till en annan semigrupp S är antingen cyklisk , eller så är den en isomorf kopia av B. Elementen φ( a ), φ( b ) och φ( e ) i S kommer alltid att uppfylla villkoren ovan (eftersom φ är en homomorfism) med det möjliga undantaget att φ( b ) φ( a ) kan visa sig vara φ ( e ). Om detta inte är sant är φ( B ) isomorf till B ; annars är det den cykliska halvgruppen som genereras av φ( a ). I praktiken innebär det att den bicykliska halvgruppen kan återfinnas i många olika sammanhang.
Idempotenterna för B är alla par ( x , x ), där x är vilket naturligt tal som helst (med den ordnade parkarakteriseringen av B ). Eftersom dessa pendlar, och B är regelbunden (för varje x finns det ett y så att x y x = x ), är den bicykliska halvgruppen en invers halvgrupp . (Detta betyder att varje element x i B har ett unikt inverst y , i den "svaga" halvgruppsbemärkelsen att x y x = x och y x y = y .)
Varje ideal av B är principiellt: vänster och höger huvudideal för ( m , n ) är
- ( m , n ) B = {( s , t ) : s ≥ m } och
- B ( m , n ) = {( s , t ): t ≥n }.
Var och en av dessa innehåller oändligt många andra, så B har inte minimala vänster- eller högerideal.
När det gäller Greens relationer har B bara en D -klass (den är bisimple ) , och har därför bara en J -klass (den är enkel ). L- och R - relationerna ges av
- ( a , b ) R ( c , d ) om och endast om a = c ; och
- ( a , b ) L ( c , d ) om och endast om b = d .
Detta innebär att två element är H -relaterade om och endast om de är identiska. Följaktligen är de enda undergrupperna av B oändligt många kopior av den triviala gruppen, som var och en motsvarar en av de idempotenta.
Äggboxdiagrammet för B är oändligt stort ; det övre vänstra hörnet börjar:
| (0, 0) | (1, 0) | (2, 0) | ... |
| (0, 1) | (1, 1) | (2, 1) | ... |
| (0, 2) | (1, 2) | (2, 2) | ... |
| ... | ... | ... | ... |
Varje post representerar en singleton H -klass; raderna är R -klasserna och kolumnerna är L -klasser. Idempotenterna för B dyker upp längs diagonalen, i enlighet med att i en vanlig semigrupp med pendlande idempotenter måste varje L -klass och varje R -klass innehålla exakt en idempotent.
Den bicykliska halvgruppen är det "enklaste" exemplet på en bisimple invers halvgrupp med identitet; det finns många andra. Där definitionen av B från ordnade par använde klassen av naturliga tal (som inte bara är en additiv halvgrupp, utan också ett kommutativt gitter under min- och max-operationer), kan en annan uppsättning med lämpliga egenskaper visas istället, och "+", "−" och "max" operationer modifierade i enlighet med detta.
Se även
Anteckningar
- ^ Hollings (2007), sid. 332
- ^ Lothaire, M. (2011). Algebraisk kombinatorik på ord . Encyclopedia of Mathematics och dess tillämpningar. Vol. 90. Med förord av Jean Berstel och Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. sid. 459. ISBN 978-0-521-18071-9 . Zbl 1221.68183 .
- ^ Howie s.60
- Den algebraiska teorin om semigrupper , AH Clifford och GB Preston. American Mathematical Society, 1961 (volym 1), 1967 (volym 2).
- Semigrupper: en introduktion till strukturteorin , Pierre Antoine Grillet. Marcel Dekker, Inc., 1995.
- Kanonisk form av element i ett associativt system som ges genom att definiera relationer , Evgenii Sergeevich Lyapin, Leningrad Gos. Ped. Inst. Usch. Zap. 89 (1953), sidorna 45–54 [ryska].
- Hollings, CD (2007). "Några första lockande steg i semigruppsteori". Matematiktidningen . Mathematical Association of America. 80 : 331-344. JSTOR 27643058 .