Кіріспе
Ассоциативтік операциясы және сәйкестік элементі бар алгебралық құрылым – категория теориясындағы моноидты нысандар. Абстрактілік алгебра математиканың бір саласы ретінде, моноид – ассоциативтік бинарлық операциясы және сәйкестік элементі бар жиынтық. Мысалы, қосу арқылы теріс емес бүтін сандар моноидты құрайды, онда сәйкестік элементі 0 болады. Моноидтар – сәйкестік элементі бар жартылай топтар. Мұндай алгебралық құрылымдар математиканың әртүрлі салаларында кездеседі. Белгілі бір жиыннан өзіне бағытталған функциялар функциялық композиция бойынша моноидты құрайды. Әдетте, категориялар теориясында, объектінің өзіне қатысты морфизмдер моноидты құрайды, ал керісінше, моноидты бір ғана объектісі бар категория ретінде қарастыруға болады. Компьютерлік ғылым және компьютерлік бағдарламалауда, берілген символдар жиынтығынан құралған жолдар жиынтығы бос моноид болып табылады. Көшу моноидтары және синтаксистік моноидтар шекті автоматтарды сипаттауда қолданылады. Із моноидтары және тарих моноидтары процестік есептеулер мен параллель есептеулер үшін негіз құрайды. Теориялық компьютерлік ғылымда моноидтарды зерттеу автоматтар теориясы (Крохн-Родос теориясы) және формальді тілдер теориясы (жұлдыздық биіктік мәселесі) үшін негізгі болып табылады. Тақырыптың тарихы және моноидтардың басқа да жалпы қасиеттері үшін жартылай топтарға қараңыз.
monoid objects in category theory
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids are semigroups with identity. Such algebraic structures occur in several branches of mathematics. The functions from a set into itself form a monoid with respect to function composition. More generally, in category theory, the morphisms of an object to itself form a monoid, and, conversely, a monoid may be viewed as a category with a single object. In computer science and computer programming, the set of strings built from a given set of characters is a free monoid. Transition monoids and syntactic monoids are used in describing finite state machines. Trace monoids and history monoids provide a foundation for process calculi and concurrent computing. In theoretical computer science, the study of monoids is fundamental for automata theory (Krohn–Rhodes theory), and formal language theory (star height problem). See semigroup for the history of the subject, and some other general properties of monoids.
Субмоноидтар
Моноидтың (M, •) субмоноиды — моноид операциясы бойынша жабық және M-нің e сәйкестік элементін қамтитын M-нің N ішкі жиыны. Символдық түрде, N — M-нің субмоноиды, егер e ∈ N ⊆ M және x, y ∈ N болғанда x • y ∈ N орындалса. Бұл жағдайда N — M-ден мұрагерлік екілік операция бойынша моноид болады. Екінші жағынан, егер N — моноид операциясы бойынша жабық моноидтың ішкі жиыны және осы мұрагерлік операция бойынша моноид болса, онда N әрқашан субмоноид бола бермейді, себебі сәйкестік элементтері әртүрлі болуы мүмкін. Мысалы, бір элементтен тұратын жиын көбейту бойынша жабық, бірақ теріс емес бүтін сандардың (көбейту) моноидінің субмоноиды емес.
On the other hand, if N is subset of a monoid that is closed under the monoid operation, and is a monoid for this inherited operation, then N is not always a submonoid, since the identity elements may differ. For example, the singleton set is closed under multiplication, and is not a submonoid of the (multiplicative) monoid of the nonnegative integers.
Генераторлар
M жиынының S ішкі жиыны M-ді туғызады деп есептеледі, егер S-ні қамтитын M-нің ең кіші субмоноиді M-ге тең болса. Егер M-ді туғызатын шекті жиын болса, онда M шекті туындаған моноид деп аталады.
Коммутативтік моноид
Операциясы коммутативті моноид коммутативті моноид (немесе, сирек кездесетін, абельдік моноид) деп аталады. Коммутативті моноидтар көбінесе қосымша түрінде жазылады. Кез келген коммутативті моноид өзінің алгебралық алдын ала реті ≤ арқылы жабдықталады, ол x ≤ y егер 1=x + z = y болатын z элементі болса, деп анықталады. Коммутативті моноидтың рет бірлігі – M моноидінің u элементі, онда M-нің кез келген x элементі үшін u-дың туындаған жиынында x ≤ v болатын v элементі бар. Бұл көбінесе M – G жартылай реттелген абельдік топтың оң конусы болған жағдайда қолданылады, онда u – G-нің рет бірлігі деп айтамыз.
Жарым коммутативті моноид
Кейбір элементтері үшін ғана коммутативті, ал барлық элементтері үшін емес операциясы бар моноид – ізгі моноид болып табылады; ізгі моноидтар параллель есептеулер теориясында кеңінен қолданылады.
Қасиеттері
Моноид аксиомалары сәйкестік элементі e бірегей екенін көрсетеді: егер e және f моноидтың сәйкестік элементтері болса, онда 1 = e = ef = f.
Өнімдер мен қуаттар
Кез келген нөлге тең немесе одан үлкен бүтін сан үшін, моноидтың n элементтерінен (a1, ..., an) кез келген тізбегінің көбейтіндісін рекурсивті түрде анықтауға болады: 1 = p0 = e және 1 = pm = pm−1 • am, 1 ≤ m ≤ n үшін.
Арнайы жағдай ретінде, моноидтың x элементінің нөлге тең немесе одан үлкен бүтін дәрежелерін анықтауға болады: 1 = x^(0) = 1 және 1 = x^(n) = x^(n−1) • x, n ≥ 1 үшін. Сонда 1 = x^(m+n) = x^(m) • x^(n) барлық m, n ≥ 0 үшін.
Керілі элементтер
Егер 1=x • y = e және 1=y • x = e болатын y элементі болса, x элементі кері нүсқалы (инвертируемый) деп аталады. Кері нүсқалар, егер олар болса, бірегей болады: егер y және z элементтері x-тің кері нүсқалары болса, онда ассоциативтілік қағидасы бойынша 1=y = ey = (zx)y = z(xy) = ze = z. Егер x кері нүсқалы болса, мысалы, y кері нүсқасымен, онда x-тің теріс дәрежелерін 1=x^(−n) = y^(n) деп, әр n ≥ 1 үшін анықтауға болады; бұл теңдеу 1=x^(m+n) = x^(m) • x^(n) барлық m, n ∈ 'Z үшін орындалады. Моноидтағы барлық кері нүсқалы элементтердің жиыны, • операциясымен бірге, топты құрайды.
Grothendieck тобы
Әр моноид топтың ішінде орналаспайды. Мысалы, екі элементі a және b болатын моноидта 1=a • b = a теңдігі орындалуы мүмкін, тіпті b сәйкестік элементі болмаса да. Мұндай моноидты топқа ендіру мүмкін емес, себебі топта екі жағын a-ның кері элементіне көбейту арқылы 1=b = e теңдігіне жетеміз, бұл дұрыс емес. Моноид (M, •) жою қасиетіне ие (немесе жоюшы) деп аталады, егер M-дегі кез келген a, b және c үшін 1=a • b = a • c теңдігі 1=b = c теңдігін білдірсе, ал 1=b • a = c • a теңдігі 1=b = c теңдігін білдірсе.
Коммутативті моноид, егер жою қасиетіне ие болса, әрқашан Гротендик құрылысы арқылы топқа ендіріле алады. Бүтін сандардың қосым тобы (қосым операциясы бар топ) осылай, табиғи сандардың қосым моноидінен (қосым операциясы және жою қасиеті бар коммутативті моноид) құрастырылады. Дегенмен, коммутативті емес жоюшы моноидты топқа ендіру міндетті емес. Егер моноид жою қасиетіне ие және шекті болса, онда ол, шын мәнінде, топ болып табылады. Моноидтың оң және сол жақтан жоюшы элементтері әрқайсысы өз кезегінде субмоноидты құрайды (яғни, операция бойынша жабық және сәйкестік элементін қамтиды). Бұл, кез келген коммутативті моноидтың жоюшы элементтерін топқа кеңейтуге болады дегенді білдіреді. Моноидтағы жою қасиеті Гротендик құрылысын жүзеге асыру үшін қажет емес – коммутативтілік жеткілікті. Алайда, егер коммутативті моноид жою қасиетіне ие болмаса, онда моноидтың Гротендик тобына гомоморфизмі инъективті емес. Нақтырақ айтқанда, егер 1=a • b = a • c болса, онда b және c Гротендик тобында бірдей бейнеге ие болады, тіпті b ≠ c болса да. Атап айтқанда, егер моноид сіңіретін элементке ие болса, онда оның Гротендик тобы тривиальды топ болып табылады.
Моноидтардың түрлері
Кері моноид — M жиынындағы әрбір a үшін M жиынында бірегей a^(−1) болатын моноид, яғни 1=a = a • a^(−1) • a және 1=a^(−1) = a^(−1) • a • a^(−1). Егер кері моноид қысқартылатын болса, онда ол топ болады. Керісінше, нөлдік қосындысы жоқ моноид — бұл 1=a + b = 0 болса, 1=a = 0 және 1=b = 0 екенін білдіретін, нөлден басқа ешқандай элементтің қосымша керісі жоқ, қосымша түрінде жазылған моноид.
Категориялар теориясымен байланысы
Моноидтарды ерекше санаттар класы ретінде қарастыруға болады. Шындығында, моноидтық операцияға қажетті аксиомалар, нақты бір объектінің бастапқы және соңғы нүктесі болатын барлық морфизмдер жиынына шектелгенде, морфизмдердің құрамына қажетті аксиомалармен сәйкес келеді. Яғни, моноид – бұл бір ғана объектісі бар санаттың өзі. Нақтырақ айтқанда, (M, •) моноиді берілген жағдайда, тек бір объектісі бар және морфизмдері M элементтерінен тұратын кіші санатты құруға болады. Морфизмдердің құрамы моноидтық операция • арқылы анықталады. Сол сияқты, моноидтық гомоморфизмдер – бұл бір объектілі санаттар арасындағы функторлар. Осылайша, бұл құрылым (кіші) моноидтар санаты Mon мен (кіші) санаттар санаты Cat-тың толық кіші санаты арасындағы эквиваленттілік береді. Сондай-ақ, топтар санаты Cat санатының тағы бір толық кіші санатына эквивалентті. Осы тұрғыдан алғанда, санаттар теориясын моноид ұғымының кеңейтілген түрі деп қарастыруға болады. Моноидтарға қатысты көптеген анықтамалар мен теоремаларды бірнеше объектісі бар кіші санаттарға жалпылауға болады. Мысалы, бір объектілі санаттың бөлігі – бұл үлестік моноид. Моноидтар, басқа алгебралық құрылымдар сияқты, өздерінің санатын – Mon құрайды, ондағы объектілер моноидтар, ал морфизмдер моноидтық гомоморфизмдер болып табылады. Сондай-ақ, санаттағы моноидтың абстрактілі анықтамасы болып табылатын моноидты объект ұғымы бар. Жиын теориясындағы (Set) моноидты объект – жай ғана моноид.
A monoid is, essentially, the same thing as a category with a single object. More precisely, given a monoid (M, •), one can construct a small category with only one object and whose morphisms are the elements of M. The composition of morphisms is given by the monoid operation •. Likewise, monoid homomorphisms are just functors between single object categories. So this construction gives an equivalence between the category of (small) monoids Mon and a full subcategory of the category of (small) categories Cat. Similarly, the category of groups is equivalent to another full subcategory of Cat. In this sense, category theory can be thought of as an extension of the concept of a monoid. Many definitions and theorems about monoids can be generalised to small categories with more than one object. For example, a quotient of a category with one object is just a quotient monoid. Monoids, just like other algebraic structures, also form their own category, Mon, whose objects are monoids and whose morphisms are monoid homomorphisms. There is also a notion of monoid object which is an abstract definition of what is a monoid in a category. A monoid object in Set is just a monoid.
MapReduce (Жалғалау)
Компьютерлік ғылымда моноидтардың қолданылуының бір мысалы – MapReduce бағдарламалау моделі («Картаны сол жаққа бүктеу арқылы MapReduce-ті моноид ретінде кодтау» деген мақалаға қараңыз). MapReduce есептеулерде екі немесе үш операциядан тұрады. Деректер жиынтығы берілген жағдайда, "Карта" операциясы кез келген деректі белгілі бір моноидтың элементтеріне бейнелейді. "Кеміту" операциясы осы элементтерді біріктіреді, нәтижесінде тек бір элемент алынады. Мысалы, егер бізде көп жиынтық болса, бағдарламада ол элементтерді олардың санына сәйкес келетін карта түрінде көрсетіледі. Бұл жағдайда элементтер кілттер деп аталады. Егер түрлі кілттердің саны өте көп болса, онда көп жиынтық бөліктерге бөлінеді. Кемітуді дұрыс аяқтау үшін "Шафлинг" кезеңі деректерді түйіндер арасында қайта топтостырады. Егер бұл қадам қажет болмаса, Map/Reduce операциясы картаға түсіруден және кемітуден тұрады; екі операция да параллельдеуге болады, біріншісі элементтік сипатына байланысты, екіншісі моноидтың ассоциативті қасиетіне байланысты.