Bicyklická poloskupina - Bicyclic semigroup

v matematika, bicyklická poloskupina je algebraický objekt důležitý pro teorii struktury poloskupiny. Ačkoli se ve skutečnosti jedná o monoidní, obvykle se označuje jako jednoduše poloskupina. To je snad nejsnadněji chápáno jako syntaktický monoid popisující Dyck jazyk vyvážených párů závorek. Proto najde běžné aplikace v systému Windows kombinatorika, jako je popis binární stromy a asociativní algebry.

Dějiny

První publikovaný popis tohoto objektu poskytl Evgenii Lyapin v roce 1953. Alfred H. Clifford a Gordon Preston tvrdí, že jeden z nich pracuje s David Rees, objevil ji nezávisle (bez publikace) někdy před rokem 1943.

Konstrukce

Existují nejméně tři standardní způsoby konstrukce bicyklické semigroup a různé notace pro odkazování na ni. Lyapin to nazval P; Použili Clifford a Preston ${ displaystyle { mathcal {C}}}$; a nejnovější články mají tendenci používat B. Tento článek bude v celém textu používat moderní styl.

Z volné poloskupiny

Bicyklická poloskupina je bezplatná poloskupina na dvou generátorech p a q, podle vztahu p q = 1. To znamená, že každý prvek semigroup je řetězec těchto dvou písmen s podmínkou, že podsekvence "p q"se nezobrazí. Operace semigroup je zřetězení řetězců, což je jasně asociativní. Potom lze ukázat, že všechny prvky B ve skutečnosti mají formu q^A p^b, pro některé přirozená čísla A a b. Složení operace se zjednodušuje na

(q^A p^b) (q^C p^d) = q^{A + C - min {b, C}} p^{d + b - min {b, C}}.

Z objednaných párů

Způsob, jakým jsou tyto exponenty omezeny, naznačuje, že „p a q strukturu „lze zahodit a ponechat pouze operace na“A a b"část. Takže." B je poloskupina párů přirozených čísel (včetně nuly) s operací^[1]

(A, b) (C, d) = (A + C - min {b, C}, d + b - min {b, C}).

To je dostatečné k definování B aby to byl stejný objekt jako v původní konstrukci. Stejně jako p a q generováno B původně s prázdným řetězcem jako monoidní identitou, tato nová konstrukce B má generátory (1, 0) a (0, 1) s identitou (0, 0).

Z funkcí

To lze ukázat žádný poloskupina S generované prvky E, A, a b splnění níže uvedených tvrzení je izomorfní do bicyklické poloskupiny.

• A E = E A = A
• b E = E b = b
• A b = E
• b A ≠ E

Není zcela zřejmé, že by tomu tak mělo být - asi nejtěžším úkolem je pochopit to S musí být nekonečný. Chcete-li to vidět, předpokládejme to A (řekněme) nemá nekonečný řád, takže A^{k + h} = A^h pro některé h a k. Pak A^k = E, a

b = E b = A^k b = A^{k - 1} E = A^{k - 1},

tak

b A = A^k = E,

což není povoleno - takže existuje nekonečně mnoho různých sil A. Úplný důkaz je uveden v knize Clifforda a Prestona.

Všimněte si, že obě výše uvedené definice splňují tyto vlastnosti. Třetí způsob odvozování B používá dvě vhodně zvolené funkce k získání bicyklické poloskupiny jako monoidu transformací přirozených čísel. Nechť α, β a ι jsou prvky transformační poloskupina na přirozených číslech, kde

• ι (n) = n
• α (n) = n + 1
• β (n) = 0 pokud n = 0 a n - 1 jinak.

Tyto tři funkce mají požadované vlastnosti, takže semigroup, kterou generují, je B.^[2]

Vlastnosti

Bicyklická poloskupina má tu vlastnost, že je obrazem jakékoli homomorfismus φ z B do jiné poloskupiny S je buď cyklický, nebo se jedná o izomorfní kopii B. Prvky φ (A), φ (b) a φ (E) z S vždy splní výše uvedené podmínky (protože φ je homomorfismus) s možnou výjimkou, že φ (b) φ (A) se může ukázat jako φ (E). Pokud to není pravda, pak φ (B) je izomorfní s B; jinak se jedná o cyklickou poloskupinu generovanou φ (A). V praxi to znamená, že bicyklickou poloskupinu lze nalézt v mnoha různých kontextech.

The idempotents z B jsou všechny páry (X, X), kde X je jakékoli přirozené číslo (pomocí charakterizace seřazeného páru z B). Protože tyto dojíždějí, a B je pravidelný (pro každého X tady je y takhle X y X = X), bicyklická poloskupina je inverzní poloskupina. (To znamená, že každý prvek X z B má jedinečnou inverzi y, ve smyslu „slabé“ poloskupiny X y X = X a y X y = y.)

Každý ideál z B is principal: the left and right principal ideals of (m, n) jsou

• (m, n) B = {(s, t) : s ≥ m} a
• B (m, n) = {(s, t) : t ≥ n}.

Každý z nich obsahuje nekonečně mnoho dalších, takže B nemá minimální levý ani pravý ideál.

Ve smyslu Greenovy vztahy, B má jen jednu D-třída (to je dvojitý), a proto má pouze jednu J-třída (to je jednoduchý). The L a R vztahy jsou dány

• (A, b) R (C, d) kdyby a jen kdyby A = C; a
• (A, b) L (C, d) právě tehdy b = d.^[3]

To znamená, že dva prvky jsou H- související, pokud a pouze pokud jsou identické. V důsledku toho jediné podskupiny B je nekonečně mnoho kopií triviální skupiny, každá odpovídá jednomu z idempotentů.

The diagram krabice na vejce pro B je nekonečně velký; levý horní roh začíná:

Každá položka představuje singleton H-třída; řádky jsou R-třídy a sloupce jsou L-třídy. Idempotents of B se objeví dolů po úhlopříčce, v souladu se skutečností, že v pravidelné semigroup s dojíždějícími idempotenty každý L-třídy a každý R-class musí obsahovat přesně jeden idempotent.

Bicyklická poloskupina je „nejjednodušším“ příkladem dvojité inverzní poloskupiny s identitou; existuje mnoho dalších. Kde je definice B z uspořádaných párů použila třídu přirozených čísel (což je nejen aditivní poloskupina, ale také komutativní mříž pod min. a max. operací) by se místo toho mohla objevit další sada s příslušnými vlastnostmi a operace „+“, „-“ a „max“ byly odpovídajícím způsobem upraveny.

Viz také

• Čtyři spirálová poloskupina
• Speciální třídy poloskupin

Poznámky

Reference

• Algebraická teorie poloskupin, A. H. Clifford a G. B. Preston. American Mathematical Society, 1961 (svazek 1), 1967 (svazek 2).
• Poloskupiny: úvod do teorie struktury, Pierre Antoine Grillet. Marcel Dekker, Inc., 1995.
• Kanonická forma prvků asociativního systému daná definováním vztahůEvgenii Sergejevič Lyapin, Leningrad Gos. Ped. Inst. Uch. Zap. 89 (1953), strany 45–54 [rusky].
• Hollings, C.D. (2007). "Některé první dráždivé kroky k teorii semigroup". Matematický časopis. Mathematical Association of America. 80: 331–344. JSTOR  27643058.