# Free monoid generated by

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

## Definition

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

• 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

### Notation

• 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]

## Terminology

• 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 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)

## Examples

• 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)