# Free semi-group

(Redirected from Free monoid)
over an alphabet $A$
The semi-group whose elements are all possible finite sequences of elements of $A$ (letters), and the operation consists of placing one sequence after another. The elements of a free semi-group are usually called words (cf. Word), and the operation is often called concatenation. For the sake of convenience, the empty word 1 is often adjoined (its length is, by definition, zero) by setting $w1 = w = w1$ for any word $w$; the semi-group with an identity that arises in this way is called the free monoid over $A$. The free semi-group (respectively, free monoid) over $A$ is often denoted by $A^+$ (respectively, $A^*$). The alphabet $A$ for the free semi-group $A^+$ is the unique irreducible generating set that consists of just those elements that cannot be decomposed into products. The letters of $A$ are called free generators. A free semi-group is defined uniquely up to an isomorphism by the cardinality of its alphabet, called the rank of the free semi-group. The free semi-group of rank 2 has sub-semi-groups that are free of countable rank.
Free semi-groups are the free objects (cf. Free algebra) in the category of all semi-groups. For a semi-group $F$ the following conditions are equivalent: 1) $F$ is free; 2) $F$ has a generating set $A$ such that any element of $F$ can be uniquely represented as a product of elements of $A$; and 3) $F$ satisfies the cancellation law, does not contain idempotents, every element of $F$ has a finite number of divisors, and for any $u,v,u',v' \in F$ the equality $uv = u'v'$ implies that $u = u'$, or that one of $u,u'$ is a left divisor of the other.
Every sub-semi-group $H$ of a free semi-group has a unique irreducible generating set, which consists of elements that cannot be decomposed into a product in $H$; however, not every sub-semi-group of a free semi-group is free. The following conditions on a sub-semi-group $H$ of a free semi-group $F$ are equivalent: 1) $H$ is a free semi-group; 2) for any $w \in F$, $H \cap wH \neq \emptyset$ and $H \cap Hw \neq \emptyset$ imply that $w \in H$; and 3) for any $w \in F$, $H \cap wH \cap Hw \neq \emptyset$ implies that $w \in H$. For arbitrary different words $u,v$ in a free semi-group $F$, either $u$ and $v$ are free generators of the sub-semi-group generated by them, or there is a $w \in F$ such that $w = u^k$, $w = v^l$ for some natural numbers $k$ and $l$; the second alternative holds if and only if $uv = vu$. Every sub-semi-group with three generators in a free semi-group is finitely presented, but there are sub-semi-groups with four generators that are not.