Elektronikus könyvtár algebra és számelmélet
A benne meghatározott bináris asszociatív műveletet Π egy félcsoportnak nevezzük. Egy egységcsoporttal rendelkező félcsoportot monoidnak (vagy egyszerűen egy egységcsoportnak) neveznek.
1. Legyen X önkényes halmaz, M (X) az X összes leképezésének halmaza önmagáért. Ezután a térképek összetételének működésével kapcsolatban M (X) egy monoid, nem kapcsolt. Ezt M (X, Oex) jelöli.
2. A készlet négyzetes mátrixok n-edrendű tekintetében mátrix szorzás - nem kommutatív monoid egy egyetlen elem - az identitás mátrix, és tekintetében hozzáadásával mátrixok - kommutatív monoid egy egyetlen elem - a nulla mátrix. Jelölje meg őket (Mn (R), •, E), (Mn (R), +, 0).
3. Az egész számkészlet egy kommutatív monoid mind az addíció, mind a szorzás tekintetében. Jelöljük őket (Z. +, 0), (Z, •, 1). Az n (n> 1) részre osztható egész számkészlet egy kommutatív félcsoport, melynek nincs egységessége a szorzáshoz képest. Mi ezt jelöljük (nZ, •).
4. Legyen A = a1. a> egy véges szimbólumkészlet - egy ábécé. A szimbólumok véges szekvenciáját az ábécé A-ban egy szónak nevezik. Az A ábécén található szavak egy Π-ben megadunk egy bináris műveletet, a "hozzárendelést"; ha, akkor. Ezután Π egy félcsoport. Ezt az A készlet által generált szabad félcsoportot nevezzük.
5. Az X1, X2 szett. X3. X4> a Cayley tábla által adott művelet tekintetében (lásd a 8.1. Táblázatot), egy olyan kapcsoló monoid, amelynek egységeleme X1.
Egy részhalmaza P 'félig-csoport nevezzük subsemigroup ha abЄP' minden a, bЄP”. Ebben az esetben azt is mondjuk, hogy a II. Nyilvánvaló subsemigroup P „önmagában egy félcsoportot a művelet P. Ha M - monoid és egy részhalmaza M” nemcsak zárt műveletek tekintetében, hanem tartalmaz egy egyetlen elem, akkor M nevezzük submonoid M.
Például az n számú többszörös számok halmaza az integerek félcsoportjában a szorzás (Z., 1) és a (Z. +, 0) szimbólumban lévő szubszonikához viszonyítva. Az A betűkészletben szereplő szavak II. Félcsoportjában az A # 900 betűs szavak alcsoportja; És egy alcsoportot is.
Egy monoid M egy eleme az e elemegységgel azt mondják, hogy invertálható, ha egy bizonyos elem esetében az ab = ba = e egyenlõség egyenlõ. A b elemet fordított a, és a-1 jelöli. Az inverz elem egyedülálló. Valóban, ha szintén ab '= b'a = e, akkor b' = eb # 900; = (ba) b '= b (ab') = be = b.
A készlet minden invertálható elemei egy monoid formák submonoid, mivel ez tartalmazza az egység elemet és zárt tekintetében a művelet: ha a és b reverzibilis, b-la-1 - az inverz ab.
A féligcsoportokban szereplő szavak identitásának problémáját tekintjük.
Legyen S = s1, .sn> - részhalmaza P elemei a félcsoport olyan, hogy bármely elemét n lehet reprezentálni a termék a halmaz elemeit S. Ezután, az S rendszer az úgynevezett generátorok P. Például, a szabad félcsoport P által generált az ábécé A = a1 ,. a>, maga az A készlet egy generátorrendszer; a félcsoport egész számok az összeadásra (Z. +, 0) van beállítva képző rendszert, és a félcsoport egész számok alatt szorzás (Z. •, 1) generátorok minden prímszám és az egység.
Meg kell jegyezni, hogy az S készlet elemeinek nem minden eleme a II. Félcsoport különálló eleme. Általánosságban az ilyen termékek egyenlőségének kérdése meglehetősen bonyolult.
Úgy véljük, hogy az elemek véges sorozata által generált félcsoportok. Ezeket finom módon generálják.
Lehetőség van arra, hogy meghatározzuk a félcsoportok meghatározásának módját anélkül, hogy a félcsoport-művelet definíciójának azon elemei egyedi tulajdonságait használnánk, nevezetesen a félcsoport létrehozását generátorok segítségével és a kapcsolatok meghatározását.
Mindegyik félcsoportot generátorok adhatják meg
(a félcsoport egy ábécéje) és a kapcsolatok meghatározását
A félcsoport-elem, azaz. az ábécében lévő szót (8.2.1) a P. félcsoport szójának nevezik.
Egy II. Félcsoport elemi átalakulása egy XAi Y formájú szóból az XBi Y szóhoz (vagy fordítva) való átmenet, ahol X, Y. a II. félcsoport önkényes szava, és Ai = Bi; Az egyik meghatározó kapcsolat (8.2.2).
Az alapváltozásokat a rendszerek formájában ábrázoltuk
Az elemi transzformációk sémái az X → X formájú tautológiai átmeneteket is magukban foglalják. Két szó X és Y grafikus egybeesése X # 333; Y.
Kapcsolatok (8.2.2.) Határozza meg a II. Félkörben szereplő szavak egyenlőségét, amely a II. Félcsoport alapvető eloszlásához kapcsolódik a következő módon. A II. Félvázlat két szója X és Y egyenlő Π ha és csak akkor, ha a félcsoport Φ
az X szó befordítása a Y szóba.
Egy ingyenes félcsoport az ábécéval (8.2.1.) A meghatározó kapcsolatok halmaza üres; két szó egyenlő, ha és csak akkor, ha grafikusan egyeznek.
Az egész számok félcsoportja (Z. +, 0) az addíciót tekintve generátorokkal határozható meg, és meghatározhatja (az additív jelölésben) a kapcsolatokat:
A féligcsoportban levő szavak azonossága a következő: egy olyan algoritmust jelez, amely bármely két szóval megállapíthatja, hogy egyenlő-e a II. Félkörben, vagy sem. Bizonyított, hogy ez a probléma algoritmikusan megoldhatatlan. A feloldhatatlan szóazonosságprobléma egy egyszerű példája az a, b, c, d, e generátorokkal rendelkező félcsoport, és a kapcsolatok definiálása ac = ca, ad = da. bc = cb, bd = db. ecc = cé, edb = de. cca = ccae.