Кіріспе

Абстракт алгебрада, жиынның еркін моноиды — элементтері сол жиынның нөл немесе одан көп элементтерінен құралған барлық шекті тізбектер (немесе жолдар) болатын моноид, мұнда жолдарды біріктіру моноид операциясы болып табылады, ал сәйкестік элементі — нөл элементтерінен тұратын бірегей тізбек, көбінесе бос жол деп аталады және ε немесе λ арқылы белгіленеді. А жиынындағы еркін моноид әдетте A* деп белгіленеді. А жиынындағы еркін жартылай топ — бос жолды қоспағанда, A* жиынының барлық элементтерін қамтитын жартылай топ. Ол әдетте A+ деп белгіленеді. Жалпы алғанда, абстракт моноид (немесе жартылай топ) S, егер ол қандай да бір жиынның еркін моноидына (немесе жартылай тобына) изоморфты болса, еркін деп аталады. Аты айтқандай, еркін моноидтар мен жартылай топтар — моноидтар мен жартылай топтардың тиісті санаттарында еркін объектілерді анықтайтын әмбебап қасиетті қанағаттандыратын объектілер. Осыдан әр моноид (немесе жартылай топ) еркін моноидтың (немесе жартылай топтың) гомоморфтік бейнесі ретінде туындайды. Жартылай топтарды еркін жартылай топтардың бейнелері ретінде зерттеуді комбинаторлық жартылай топ теориясы дейді. Еркін моноидтар (және жалпы моноидтар) анықтама бойынша ассоциативті; яғни, топтастыруды немесе операциялардың орындалу ретін көрсету үшін жақшалар қолданылмайды. Ассоциативті емес эквиваленті — еркін магма.

Бірлескен сөздер

Біз A жиынынан алынған uv және vu формасындағы сөздер жұбын конъюгат деп анықтаймыз: сөздің конъюгаттары – оның айналмалы түрленулері болып табылады. Егер екі сөз А жиынымен туындаған еркін топтың элементтері ретінде топ теориясы мағынасында конъюгат болса, онда олар осы мағынада конъюгат болады.

Тең бөлінетіндігі

Еркін моноид теңбөлінеді: егер mn = pq теңдеуі орындалса, онда m = ps, sn = q (мысалы, суретті қараңыз) немесе ms = p, n = sq болатын s элементі табылады. Бұл нәтиже Леви леммасы деп те аталады. Моноид еркін болу үшін, оның сыныпталған болуы қажет және міндетті (тек толыққанды элемент 0-сыныпты) және теңбөлінетін болуы керек. A* субмоноиді тұрақты болу үшін, оның еркін болуы қажет және міндетті. Мысалы, А ретінде біттер жиынтығын { "0", "1" } пайдалансақ, "1"-дің жұп саны бар барлық биттік тізбектердің N жиынтығы тұрақты субмоноид болып табылады, себебі егер u-да "1"-дің жұп саны болса және ux-та болса, онда x-та да "1"-дің жұп саны болуы керек. N-ді кез келген жеке біттер жиынтығымен еркін құру мүмкін болмаса да, оны біттік тізбектер жиынтығы { "0", "11", "101", "1001", "10001", } – жай ғана "10n1" түріндегі тізбектер жиынтығы ( "0" тізбегімен бірге), n – кез келген теріс емес бүтін сан болғанда еркін құруға болады.

Кодтар

P еркін моноиді үшін еркін генераторлар жиынтығы P-нің негізі деп аталады: егер C* еркін моноид болса және C негіз болса, онда C сөздерінің жиынтығы код болып саналады. A∗ субмоноиді оң жақтық бірлік болып табылады, егер x және xy N-де болса, онда y де N-де болады. Субмоноид префикс бойынша туындайды, егер және тек қана оң жақтық бірлік болса.

Факторлау

Еркін моноидтың факторлануы — сөздердің ішкі жиындарының тізбегі, мұндағы қасиет — еркін моноидтағы әрбір сөзді осы ішкі жиындардан алынған элементтердің тізбегі ретінде жазуға болады. Чен-Фокс-Линдон теоремасы Линдон сөздері осындай факторлануды береді деп мәлімдейді. Көбірек жалпылай келгенде, Холл сөздері де факторлануды қамтамасыз етеді; ал Линдон сөздері — Холл сөздерінің ерекше жағдайы.

Морфизмдер

Бос моноид B∗-тан моноид M-ге дейінгі f моноидтық морфизмі – x, y сөздері үшін f(xy) = f(x)⋅f(y) және f(ε) = ι шартын қанағаттандыратын бейнелеу, мұнда ε және ι сәйкесінше B∗ және M сәйкестік элементтерін білдіреді. Морфизм f, B әріптеріндегі мәндерімен анықталады, ал керісінше, B-ден M-ге дейінгі кез келген бейнелеу морфизмге дейін кеңейтіледі. Егер B әрпінің ешқайсысы ι-ге бейнеленбесе, морфизм өшірмейтін немесе үздіксіз болады, ал егер B әрпінің барлығы ι-ге бейнеленсе, тривиалды болады. Бос моноид B∗-тан бос моноид A∗-ға дейінгі морфизм f толық деп аталады, егер A әрпінің әрқайсысы f бейнесіндегі кейбір сөздерде кездессе; циклдік – егер f бейнесі A-ның w сөзі үшін {w}∗ жиынында жатса. Морфизм f, егер |f(a)| ұзындығы A-дағы барлық a үшін тұрақты және k-ға тең болса, k біркелкі болады. 1 біркелкі морфизм қатаң түрде әліпбилік болып табылады.

Бос моноид B∗-тан бос моноид A∗-ға дейінгі морфизм f қарапайым болады, егер B-дан кішкентай кардиналдығы бар C алфавиті болса, морфизм f, C∗ арқылы факторланады, яғни, ол B∗-тан C∗-ға дейінгі морфизмнің және одан A∗-ға дейінгі морфизмнің композициясы болады; әйтпесе f элементар болады. Егер f астында B әрпінің бейнесі код болса, онда морфизм f код деп аталады. Кез келген элементар морфизм – код.

Сынақ жиынтығы

L үшін B* жиынының ішкі жиыны болғанда, L жиынының шекті ішкі жиыны T, егер B* жиынындағы f және g морфизмдері L жиынында сәйкес келсе, ғана T жиынында сәйкес келсе, L үшін сынақ жиыны болып табылады. Эренфюхт болжамы кез келген L жиынының сынақ жиыны бар екенін айтады: бұл Альберт пен Лоуренс, Макнотон және Губа тәуелсіз түрде дәлелдеген. Дәлелдер Гилберттің негіздер теоремасына сүйенеді.

Эндоморфизмдер

A эндоморфизмі – A*-дан өзіне морфизм. I сәйкестік операторы A* эндоморфизмі болып табылады, және эндоморфизмдер функциялар композициясы бойынша моноид құрайды. Егер f эндоморфизмі үшін, бос емес s жолы үшін f(a) = as тең болатын a әрпі болса, онда f эндоморфизмі ұзартылатын болады.