Meta tags:

Headings (most frequently used words):

monoid, monoids, and, commutative, contents, definition, structures, examples, properties, acts, operator, homomorphisms, equational, presentation, relation, to, category, theory, in, computer, science, mapreduce, complete, see, also, notes, citations, references, external, links, submonoids, generators, partially, products, powers, invertible, elements, grothendieck, group, types, of,

Text of the page (most frequently used words):
the (216), #monoid (170), and (109), with (56), for (54), identity (54), element (46), set (40), group (39), operation (37), that (35), monoids (34), commutative (30), required (29), edit (28), elements (26), this (25), unneeded (25), are (23), category (22), then (21), can (21), theory (20), given (20), not (19), all (18), semigroup (17), under (16), any (15), one (15), such (15), from (14), its (14), homomorphism (14), every (14), isbn (13), may (12), finite (12), computer (12), algebra (12), has (12), which (12), also (12), sum (12), displaystyle (12), example (12), called (12), binary (12), structures (11), science (11), order (11), object (11), text (10), algebraic (10), vol (10), have (10), between (10), ring (10), 2009 (9), two (9), associative (9), function (9), zbl (8), some (8), inverse (8), submonoid (8), numbers (8), there (8), multiplication (8), grothendieck (8), wikipedia (7), categories (7), kuich (7), each (7), case (7), left (7), addition (7), defined (7), like (7), morphisms (7), composition (7), mathematics (6), 978 (6), jacobson (6), cancellation (6), see (6), sup (6), subset (6), map (6), just (6), structure (6), other (6), form (6), integers (6), presentation (6), main (6), let (6), over (6), unique (6), cancellative (6), property (6), lattice (6), page (5), springer (5), automata (5), since (5), where (5), definition (5), both (5), quad (5), associativity (5), end (5), ell (5), endowed (5), whose (5), homomorphisms (5), small (5), more (5), same (5), magma (5), relation (5), free (5), article (5), into (5), denoted (5), exists (5), closed (5), invertible (5), forms (5), subsets (5), toggle (4), contents (4), search (4), press (4), links (4), products (4), semigroups (4), notes (4), programming (4), acts (4), abstract (4), series (4), operations (4), examples (4), only (4), relations (4), define (4), together (4), complete (4), these (4), implies (4), equipped (4), being (4), data (4), consists (4), mapreduce (4), way (4), sequence (4), mathrm (4), cases (4), groups (4), special (4), class (4), axioms (4), multiplicative (4), written (4), does (4), act (4), operator (4), opposite (4), zero (4), nonnegative (4), powers (4), product (4), properties (4), functions (4), itself (4), idempotent (4), abelian (4), history (4), hide (4), move (4), sidebar (4), languages (3), view (3), about (3), non (3), index (3), encyclopedia (3), 1996 (3), doi (3), rhodes (3), monographs (3), 387 (3), new (3), university (3), werner (3), systems (3), 642 (3), verlag (3), 1990 (3), continuous (3), semirings (3), oxford (3), power (3), when (3), domain (3), fix (3), but (3), distinct (3), ordered (3), least (3), their (3), need (3), reduce (3), mapping (3), folding (3), those (3), similar (3), instance (3), fold (3), begin (3), many (3), total (3), types (3), quotient (3), single (3), construction (3), gives (3), full (3), target (3), quasigroup (3), equational (3), simply (3), strings (3), generators (3), said (3), always (3), even (3), particular (3), however (3), respectively (3), sometimes (3), right (3), adjoining (3), transformation (3), additive (3), trivial (3), natural (3), equality (3), true (3), integer (3), cyclic (3), unit (3), positive (3), general (3), boolean (3), trace (3), partially (3), lie (3), tools (3), table (2), contact (2), privacy (2), policy (2), terms (2), wikimedia (2), foundation (2), commons (2), was (2), last (2), cs1 (2), date (2), german (2), language (2), short (2), description (2), wikidata (2), external (2), wehrung (2), 176 (2), 267 (2), john (2), steinberg (2), applications (2), 2nd (2), words (2), 2011 (2), pushdown (2), lecture (2), berlin (2), gruyter (2), graphs (2), handbook (2), nathan (2), help (2), hebisch (2), 1992 (2), gondran (2), michel (2), minoux (2), 2008 (2), models (2), algorithms (2), droste (2), formal (2), theoretical (2), 2006 (2), awodey (2), references (2), citations (2), therefore (2), above (2), equations (2), star (2), height (2), problem (2), semiring (2), monad (2), cartesian (2), infinitary (2), upper (2), compatible (2), directed (2), partial (2), emptyset (2), neq (2), keys (2), number (2), due (2), latter (2), multiset (2), computing (2), produce (2), folded (2), differ (2), depending (2), tree (2), follows (2), pattern (2), value (2), what (2), objects (2), mon (2), thought (2), definitions (2), than (2), subcategory (2), cat (2), precisely (2), viewed (2), loop (2), plactic (2), langle (2), vert (2), rangle (2), thus (2), symmetric (2), closure (2), extended (2), defining (2), means (2), isomorphic (2), isomorphism (2), because (2), though (2), image (2), consider (2), first (2), cannot (2), omitted (2), classes (2), injective (2), known (2), include (2), transition (2), additively (2), equivalently (2), embedded (2), possible (2), exist (2), holds (2), get (2), say (2), equation (2), hold (2), inverses (2), bmatrix (2), cdots (2), denotes (2), generalizing (2), previous (2), constant (2), empty (2), string (2), matrix (2), formed (2), find (2), singleton (2), bounded (2), top (2), lattices (2), algebras (2), heyting (2), semilattice (2), four (2), while (2), xor (2), xnor (2), false (2), operators (2), commonly (2), occur (2), concurrent (2), often (2), generated (2), used (2), inherited (2), submonoids (2), module (2), appearance (2), upload (2), file (2), changes (2), read (2), english (2), bahasa (2), subsection (2), log (2), create (2), account (2), donate (2), menu (2), add, topic, mobile, cookie, statement, statistics, developers, code, conduct, legal, safety, contacts, disclaimers, available, additional, apply, using, site, you, agree, registered, trademark, profit, organization, inc, use, creative, attribution, sharealike, license, rendered, parsoid, edited, august, 2026, utc, hidden, errors, sources, matches, articles, retrieved, https, org, php, title, oldid, 1368940468, planetmath, mathworld, weisstein, eric, ems, 2001, 1994, friedrich, 285, 0865, 06010, 56410568, s2cid, 2140, pjm, pacific, journal, tensor, interpolation, benjamin, 09781, approach, 1997, 0874, 20040, 1475463, 521, 59924, 1017, cbo9780511566097, cambridge, combinatorics, lothaire, 7020, 256, 1251, 68135, 24896, 228, foundations, essays, dedicated, symeon, bozapalidis, occasion, his, retirement, paterson, michael, 443, 110, 540, 52826, 103, 17th, international, colloquium, warwick, england, july, proceedings, kilp, mati, knauer, ulrich, mikhalev, alexander, 2000, expositions, walter, 0945, 20036, 015248, wreath, students, researchers, dover, 486, 47189, basic, incompatibility, citation, 1951, van, nostrand, company, 90122, lectures, 1995, london, mathematical, society, clarendon, 0835, 20077, 851194, fundamentals, howie, udo, eine, algebraische, theorie, unendlicher, summen, mit, anwendungen, auf, halbgruppen, und, halbringe, 152, 0747, 08005, bayreuther, mathematische, schriften, research, interfaces, dordrecht, 1201, 16038, 75450, dioids, eatcs, 01491, 1007, 01492, 5_1, weighted, logic, guides, 1100, 18001, 856861, steve, proof, authors, omit, requirement, must, contain, requiring, satisfy, frobenioid, kleene, functional, green, collection, bounds, bound, ordering, bigcup, cap, sigma, program, represented, too, big, sharded, finalize, reduction, properly, shuffling, stage, regroups, among, nodes, step, whole, reducing, parallelizable, former, wise, nature, application, model, three, dataset, arbitrary, specific, encoding, serialization, result, might, pre, post, traversal, values, type, rightarrow, mapsto, varepsilon, nil, bullet, cons, common, accumulated, final, iterative, update, kind, running, iteration, elegantly, expressed, alternatively, ensures, employing, algorithm, utilize, multiple, cores, processors, efficiently, prefix, parallelized, notion, own, sense, extension, concept, theorems, generalised, likewise, similarly, equivalent, another, equivalence, functors, construct, essentially, thing, indeed, exactly, restricted, source, morphism, unital, groupoid, semigroupoid, divisible, degree, infinite, show, commutes, aba, baa, bba, bab, bicyclic, typical, situation, defines, finally, takes, reflexive, transitive, congruence, svt, sut, much, specified, specifying, extending, congruences, constructing, them, bijective, contrast, necessarily, preserves, modulo, maps, second, condition, residue, identities, surjective, analogue, important, made, semiautomata, action, direction, zerosumfree, necessary, perform, commutativity, sufficient, absorbing, turn, obviously, fact, via, how, constructed, embeddable, sits, inside, perfectly, take, multiplying, sides, would, negative, setting, makes, they, recursively, textstyle, prod, were, permutation, leq, moreover, considered, points, ordinary, sphere, furthermore, projective, plane, expression, torus, connected, compact, surfaces, homeomorphism, relationship, below, endomorphisms, consisting, turns, pointwise, sets, corresponding, coordinates, direct, carrier, fixed, alphabet, serves, concatenation, underlying, matrices, complex, real, rational, turned, conversion, done, adjoin, resulting, orders, representing, lexicographical, functor, bottom, join, meet, union, intersection, numerical, out, sided, make, standard, computation, less, cone, preordering, smallest, containing, generates, finitely, generate, hand, contains, symbolically, whenever, context, symbol, notation, imply, multiplied, juxtaposition, reason, regarded, ary, nullary, characterized, specification, triple, equalities, will, denote, satisfies, following, subject, study, fundamental, krohn, built, describing, provide, process, calculi, state, machines, syntactic, characters, respect, generally, conversely, several, branches, magmas, hopf, bialgebra, graded, linear, vector, space, complemented, division, field, integral, near, rng, rack, quandle, confused, item, projects, printable, version, download, pdf, print, export, switch, legacy, parser, shortened, url, cite, information, permanent, link, related, here, actions, talk, ייִדיש, tiếng, việt, українська, türkçe, ไทย, தமிழ், svenska, српски, srpski, slovenščina, simple, srpskohrvatski, српскохрватски, русский, română, português, piemontèis, polski, occitan, nederlands, မြန်မာဘာသာ, melayu, македонски, lietuvių, lëtzebuergesch, 한국어, 日本語, italiano, íslenska, indonesia, interlingua, magyar, hrvatski, עברית, galego, français, suomi, فارسی, eesti, español, esperanto, ελληνικά, deutsch, čeština, català, azərbaycanca, العربية, personal, pages, recent, community, portal, learn, contribute, random, current, events, navigation, jump, content,

Text of the page (random words):
1 this makes the equation x m n x m x n hold for all m n z the set of all invertible elements in a monoid together with the operation forms a group grothendieck group edit main article grothendieck group not every monoid sits inside a group for instance it is perfectly possible to have a monoid in which two elements a and b exist such that a b a holds even though b is not the identity element for example take a 0 and b 5 in the multiplicative monoid of nonnegative integers such a monoid cannot be embedded in a group because in the group multiplying both sides with the inverse of a would get that b e which is not true a monoid m has the cancellation property or is cancellative if for all a b and c in m the equality a b a c implies b c and the equality b a c a implies b c a commutative monoid with the cancellation property can always be embedded in a group via the grothendieck group construction that is how the additive group of the integers a group with operation is constructed from the additive monoid of natural numbers a commutative monoid with operation and cancellation property however a non commutative cancellative monoid need not be embeddable in a group if a monoid has the cancellation property and is finite then it is in fact a group c the right and left cancellative elements of a monoid each in turn form a submonoid i e are closed under the operation and obviously include the identity this means that the cancellative elements of any commutative monoid can be extended to a group the cancellative property in a monoid is not necessary to perform the grothendieck construction commutativity is sufficient however if a commutative monoid does not have the cancellation property the homomorphism of the monoid into its grothendieck group is not injective more precisely if a b a c then b and c have the same image in the grothendieck group even if b c in particular if the monoid has an absorbing element then its grothendieck group is the trivial group types of monoids edit an inverse monoid is a monoid where for every a in m there exists a unique a 1 in m such that a a a 1 a and a 1 a 1 a a 1 if an inverse monoid is cancellative then it is a group in the opposite direction a zerosumfree monoid is an additively written monoid in which a b 0 implies that a 0 and b 0 7 equivalently that no element other than zero has an additive inverse acts and operator monoids edit main article monoid act let m be a monoid with the binary operation denoted by and the identity element denoted by e then a left m act or left act over m is a set x together with an operation m x x which is compatible with the monoid structure as follows for all x in x e x x for all a b in m and x in x a b x a b x this is the analogue in monoid theory of a left group action right m acts are defined in a similar way a monoid with an act is also known as an operator monoid important examples include transition systems of semiautomata a transformation semigroup can be made into an operator monoid by adjoining the identity transformation monoid homomorphisms edit example monoid homomorphism x 2 x from n 0 to n 1 it is injective but not surjective a homomorphism between two monoids m and n is a function f m n such that f x y f x f y for all x y in m f e m e n where e m and e n are the identities on m and n respectively monoid homomorphisms are sometimes simply called monoid morphisms not every semigroup homomorphism between monoids is a monoid homomorphism since it may not map the identity to the identity of the target monoid even though the identity is the identity of the image of the homomorphism d for example consider z n the set of residue classes modulo n equipped with multiplication in particular 1 n is the identity element function f z 3 z 6 given by k 3 3 k 6 is a semigroup homomorphism since 3 k 3 l 6 9 kl 6 3 kl 6 however f 1 3 3 6 1 6 so a monoid homomorphism is a semigroup homomorphism between monoids that maps the identity of the first monoid to the identity of the second monoid and the latter condition cannot be omitted in contrast a semigroup homomorphism between groups is always a group homomorphism as it necessarily preserves the identity because in the target group of the homomorphism the identity element is the only element x such that x x x a bijective monoid homomorphism is called a monoid isomorphism two monoids are said to be isomorphic if there is a monoid isomorphism between them equational presentation edit main article presentation of a monoid monoids may be given a presentation much in the same way that groups can be specified by means of a group presentation one does this by specifying a set of generators σ and a set of relations on the free monoid σ one does this by extending finite binary relations on σ to monoid congruences and then constructing the quotient monoid as above given a binary relation r σ σ one defines its symmetric closure as r r 1 this can be extended to a symmetric relation e σ σ by defining x e y if and only if x sut and y svt for some strings u v s t σ with u v r r 1 finally one takes the reflexive and transitive closure of e which is then a monoid congruence in the typical situation the relation r is simply given as a set of equations so that r u 1 v 1 u n v n thus for example p q p q 1 displaystyle langle p q vert pq 1 rangle is the equational presentation for the bicyclic monoid and a b a b a b a a b b a b a b displaystyle langle a b vert aba baa bba bab rangle is the plactic monoid of degree 2 it has infinite order elements of this plactic monoid may be written as a i b j b a k displaystyle a i b j ba k for integers i j k as the relations show that ba commutes with both a and b relation to category theory edit group like structures total associative identity divisible partial magma unneeded unneeded unneeded unneeded multiplicative unneeded unneeded required unneeded semigroupoid unneeded required unneeded unneeded small category unneeded required required unneeded groupoid unneeded required required required magma required unneeded unneeded unneeded quasigroup required unneeded unneeded required unital magma required unneeded required unneeded loop required unneeded required required semigroup required required unneeded unneeded associative quasigroup required required unneeded required monoid required required required unneeded group required required required required monoids can be viewed as a special class of categories indeed the axioms required of a monoid operation are exactly those required of morphism composition when restricted to the set of all morphisms whose source and target is a given object 8 that is 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 8 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 8 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 monoids in computer science edit in computer science many abstract data types can be endowed with a monoid structure in a common pattern a sequence of elements of a monoid is folded or accumulated to produce a final value for instance many iterative algorithms need to update some kind of running total at each iteration this pattern may be elegantly expressed by a monoid operation alternatively the associativity of monoid operations ensures that the operation can be parallelized by employing a prefix sum or similar algorithm in order to utilize multiple cores or processors efficiently given a sequence of values of type m with identity element ε and associative operation the fold operation is defined as follows f o l d m m ℓ ε if ℓ n i l m f o l d ℓ if ℓ c o n s m ℓ displaystyle mathrm fold m rightarrow m ell mapsto begin cases varepsilon text if ell mathrm nil m bullet mathrm fold ell text if ell mathrm cons m ell end cases in addition any data structure can be folded in a similar way given a serialization of its elements for instance the result of folding a binary tree might differ depending on pre order vs post order tree traversal mapreduce edit an application of monoids in computer science is the so called mapreduce programming model see encoding map reduce as a monoid with left folding mapreduce in computing consists of two or three operations given a dataset map consists of mapping arbitrary data to elements of a specific monoid reduce consists of folding those elements so that in the end we produce just one element for example if we have a multiset in a program it is represented as a map from elements to their numbers elements are called keys in this case the number of distinct keys may be too big and in this case the multiset is being sharded to finalize reduction properly the shuffling stage regroups the data among the nodes if we do not need this step the whole map reduce consists of mapping and reducing both operations are parallelizable the former due to its element wise nature the latter due to associativity of the monoid complete monoids edit a complete monoid is a commutative monoid equipped with an infinitary sum operation σ i displaystyle sigma _ i for any index set i such that 9 10 11 12 i m i 0 i j m i m j i j k m i m j m k for j k displaystyle sum _ i in emptyset m_ i 0 quad sum _ i in j m_ i m_ j quad sum _ i in j k m_ i m_ j m_ k quad text for j neq k and j j i i j m i i i m i if j j i j i and i j i j for j j displaystyle sum _ j in j sum _ i in i_ j m_ i sum _ i in i m_ i quad text if bigcup _ j in j i_ j i text and i_ j cap i_ j emptyset quad text for j neq j an ordered commutative monoid is a commutative monoid m together with a partial ordering such that a 0 for every a m and a b implies a c b c for all a b c m a continuous monoid is an ordered commutative monoid m in which every directed subset has a least upper bound and these least upper bounds are compatible with the monoid operation a sup s sup a s displaystyle a sup s sup a s for every a m and directed subset s of m if m is a continuous monoid then for any index set i and collection of elements a i i i one can define i a i sup finite e i e a i displaystyle sum _ i a_ i sup _ text finite e subset i sum _ e a_ i and m together with this infinitary sum operation is a complete monoid 12 see also edit cartesian monoid green s relations monad functional programming semiring and kleene algebra star height problem frobenioid notes edit if both e 1 and e 2 satisfy the above equations then e 1 e 1 e 2 e 2 some authors omit the requirement that a submonoid must contain the identity element from its definition requiring only that it have an identity element which can be distinct from that of m proof fix an element x in the monoid since the monoid is finite x n x m for some m n 0 but then by cancellation we have that x m n e where e is the identity therefore x x m n 1 e so x has an inverse f x f e m f x e m f x for each x in m when f is a semigroup homomorphism and e m is the identity of its domain monoid m citations edit jacobson 2009 gondran minoux 2008 p 13 rhodes steinberg 2009 p 22 jacobson 2009 p 29 examples 1 2 4 5 jacobson 2009 p 35 jacobson 2009 p 31 1 2 wehrung 1996 1 2 3 awodey 2006 p 10 droste kuich 2009 pp 7 10 hebisch 1992 kuich 1990 1 2 kuich 2011 references edit awodey steve 2006 category theory oxford logic guides vol 49 oxford university press isbn 0 19 856861 4 zbl 1100 18001 droste m kuich w 2009 semirings and formal power series handbook of weighted automata monographs in theoretical computer science an eatcs series pp 3 28 doi 10 1007 978 3 642 01492 5_1 isbn 978 3 642 01491 8 gondran michel minoux michel 2008 graphs dioids and semirings new models and algorithms operations research computer science interfaces series vol 41 dordrecht springer verlag isbn 978 0 387 75450 5 zbl 1201 16038 hebisch udo 1992 eine algebraische theorie unendlicher summen mit anwendungen auf halbgruppen und halbringe bayreuther mathematische schriften in german 40 21 152 zbl 0747 08005 howie john m 1995 fundamentals of semigroup theory london mathematical society monographs new series vol 12 oxford clarendon press isbn 0 19 851194 9 zbl 0835 20077 jacobson nathan 1951 lectures in abstract algebra vol i d van nostrand company isbn 0 387 90122 1 citation isbn date incompatibility help jacobson nathan 2009 basic algebra vol 1 2nd ed dover isbn 978 0 486 47189 1 kilp mati knauer ulrich mikhalev alexander v 2000 monoids acts and categories with applications to wreath products and graphs a handbook for students and researchers de gruyter expositions in mathematics vol 29 berlin walter de gruyter isbn 3 11 015248 7 zbl 0945 20036 kuich werner 1990 ω continuous semirings algebraic systems and pushdown automata in paterson michael s ed automata languages and programming 17th international colloquium warwick university england july 16 20 1990 proceedings lecture notes in computer science vol 443 springer verlag pp 103 110 isbn 3 540 52826 1 kuich werner 2011 algebraic systems and pushdown automata in kuich werner ed algebraic foundations in computer science essays dedicated to symeon bozapalidis on the occasion of his retirement lecture notes in computer science vol 7020 berlin springer verlag pp 228 256 isbn 978 3 642 24896 2 zbl 1251 68135 lothaire m ed 1997 combinatorics on words encyclopedia of mathematics and its applications vol 17 2nd ed cambridge university press doi 10 1017 cbo9780511566097 isbn 0 521 59924 5 mr 1475463 zbl 0874 20040 rhodes john steinberg benjamin 2009 the q theory of finite semigroups a new approach springer monographs in mathematics vol 71 springer isbn 978 0 387 09781 7 wehrung friedrich 1996 tensor products of structures with interpolation pacific journal of mathematics 176 1 267 285 doi 10 2140 pjm 1996 176 267 s2cid 56410568 zbl 0865 06010 external links edit monoid encyclopedia of mathematics ems press 2001 1994 weisstein eric w monoid mathworld monoid at planetmath retrieved from https en wikipedia org w index php title monoid oldid 1368940468 categories algebraic structures category theory semigroup theory hidden categories articles with short description short descriptio...