Free monoid generated by

From Maths
Jump to: navigation, search
Stub grade: A
This page is a stub
This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:
Demote once fleshed out and minimally complete
Be sure to check Discussion of the free monoid and free semigroup generated by a set, as there are some things to note


Given a set, [ilmath]X[/ilmath], there is a free monoid, [ilmath](F,*)[/ilmath][1].

  • The elements of [ilmath]F[/ilmath] are all the finite tuples, [ilmath](x_1,\ldots,x_n)[/ilmath] (where [ilmath]x_i\in X[/ilmath])
  • The monoid operation ([ilmath]*:F\times F\rightarrow F[/ilmath]) is concatenation:
    • [ilmath]*:((x_1,\ldots,x_n),(y_1,\ldots,y_n))\mapsto(x_1,\ldots,x_n,y_1,\ldots,y_n)[/ilmath]
  • The identity element of the monoid is:
    • [ilmath]e=()[/ilmath] - the "empty" tuple.

The proof that this is indeed a monoid is below


  • We often identify [ilmath]x\in X[/ilmath] with [ilmath](x)\in F[/ilmath], and singletons of [ilmath]F[/ilmath] (ie: [ilmath](y)\in F[/ilmath] with [ilmath]y\in X[/ilmath].
  • This notation extends further, and (especially in the case of the free semigroup generated by [ilmath]X[/ilmath][Note 1]) we write [ilmath](x_1,x_2,\ldots,x_{n-1},x_n)[/ilmath] as a product or word, [ilmath]x_1x_2\ldots x_{n-1}x_n[/ilmath]


  • The finite tuples of [ilmath]F[/ilmath] are sometimes called "words".
    • Warning:The "word" terminology may be specific to the free group, however I wouldn't be surprised if word is used in this context too, so I deem it still worth mentioning
    • Caution:Word may only be used for elements of [ilmath]F[/ilmath] written in the "product" notation, [ilmath]x_1\ldots x_n[/ilmath]. The reference[1] implies this.
Grade: D
This page requires references, it is on a to-do list for being expanded with them.
Please note that this does not mean the content is unreliable, it just means that the author of the page doesn't have a book to hand, or remember the book to find it, which would have been a suitable reference.
The message provided is:
While not explicitly said, the main reference doesn't deal with these objects in great detail, however usually such tuples are called words, at least with free groups (see warning)


  • This page can be considered an element of the monoid generated by the alphabet (union all the symbols too)

Proof that this is indeed a monoid

  1. Associativity is trivial
  2. Identity element being an identity element is trivial

(These might be good "low hanging fruit" for any newcomers)


  1. We do this because the semigroup has no identity (in fact, is considered as the set of all tuples of length greater than or equal to one of elements of [ilmath]X[/ilmath]), it has no "empty tuple", writing an empty tuple as a "word" would be an empty word! You couldn't even tell it was there.


  1. 1.0 1.1 Abstract Algebra - Pierre Antoine Grillet

Template:Monoid navbox