Difference between revisions of "Free monoid generated by"
From Maths
m (Added warning note) |
m (Saving work, again) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 10: | Line 10: | ||
** {{M|1=e=()}} - the "empty" tuple. | ** {{M|1=e=()}} - the "empty" tuple. | ||
The proof that this is indeed a monoid is below | The proof that this is indeed a monoid is below | ||
| + | ===Notation=== | ||
| + | * We often identify {{M|x\in X}} with {{M|(x)\in F}}, and singletons of {{M|F}} (ie: {{M|(y)\in F}} with {{M|y\in X}}. | ||
| + | * This notation extends further, and (especially in the case of the [[free semigroup generated by]] {{M|X}}<ref group="Note">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 {{M|X}}), 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.</ref>) we write {{M|(x_1,x_2,\ldots,x_{n-1},x_n)}} as a product or ''word'', {{M|x_1x_2\ldots x_{n-1}x_n}} | ||
| + | |||
| + | ==Terminology== | ||
| + | * The finite [[tuple|tuples]] of {{M|F}} 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 {{M|F}} written in the "product" notation, {{M|x_1\ldots x_n}}. The reference<ref name="AAPAG"/> implies this.}} | ||
| + | {{Requires references|grade=D|msg=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== | ==Examples== | ||
* This page can be considered an element of the monoid generated by the alphabet ([[union]] all the symbols too) | * This page can be considered an element of the monoid generated by the alphabet ([[union]] all the symbols too) | ||
| Line 16: | Line 25: | ||
# Identity element being an identity element is trivial | # Identity element being an identity element is trivial | ||
(These might be good "low hanging fruit" for any newcomers) | (These might be good "low hanging fruit" for any newcomers) | ||
| + | ==Notes== | ||
| + | <references group="Note"/> | ||
==References== | ==References== | ||
<references/> | <references/> | ||
{{Monoid navbox|plain}} | {{Monoid navbox|plain}} | ||
{{Definition|Monoid Theory|Abstract Algebra}} | {{Definition|Monoid Theory|Abstract Algebra}} | ||
Latest revision as of 16:20, 20 July 2016
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
Contents
Definition
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
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[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:
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
- Associativity is trivial
- Identity element being an identity element is trivial
(These might be good "low hanging fruit" for any newcomers)
Notes
- ↑ 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.
