# Free monoid

In mathematics, a **free monoid** on a set \( X \) is the monoid \( X^{*} \) whose elements are all finite sequences (words) with entries from \( X \), whose operation is concatenation, and whose identity element is the empty word of length zero. It is called free because it imposes no relations among the generators: two words are equal only when they are the same sequence of letters, and any assignment of the letters to elements of an arbitrary monoid extends uniquely to a monoid homomorphism.<sup>[1](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)</sup>

| Key fact | Detail |
|---|---|
| Carrier | \( X^{*} = \{(x_1, x_2, \ldots, x_u) : u \geq 0,\ x_i \in X\} \), all finite tuples over \( X \), written as words \( x_1 x_2 \cdots x_u \)<sup>[1](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)</sup> |
| Operation and identity | Concatenation of words; the empty word of length 0 is the identity<sup>[1](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)</sup> |
| Universal property | For any monoid \( M \) and any map \( f : X \to M \), there is a unique monoid homomorphism \( \varphi : X^{*} \to M \) with \( \varphi \) extending \( f \) along the inclusion \( X \hookrightarrow X^{*} \)<sup>[1](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)</sup> |
| Freeness criterion | A monoid \( M \) is free when it has a subset \( B \) with \( M = B^{*} \) and every element has a unique representation as a product of elements of \( B \); \( B \) is a base, and the identity is never in the base<sup>[2](https://www.math.utu.fi/en/home/karhumak/pdf/combwo.pdf)</sup> |
| Companion structures | \( X^{+} \), the non-empty words, is the free semigroup on \( X \); adjoining the empty word gives \( X^{*} \)<sup>[3](https://www.sciencedirect.com/topics/mathematics/free-semigroup)</sup> |
| Uniqueness | For each \( n \geq 0 \) there is exactly one free monoid, up to isomorphism, with a basis of \( n \) elements<sup>[4](https://d-nb.info/1190725940/34)</sup> |
| Role in language theory | A formal language over an alphabet \( A \) is a subset of \( A^{*} \)<sup>[5](https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/13%3A_Monoids_and_Automata/13.02%3A_Free_Monoids_and_Languages)</sup> |

## Definition and construction

Let \( X \) be a set, viewed as an alphabet. The free monoid with basis \( X \) is the set \( X^{*} \) of all finite sequences of elements of \( X \), of every possible length, including the empty sequence. The binary operation is concatenation: the product of \( x_1 x_2 \cdots x_u \) and \( y_1 y_2 \cdots y_v \) is \( x_1 \cdots x_u y_1 \cdots y_v \). Concatenation is associative, and the empty word acts as the identity, so \( X^{*} \) is a monoid.<sup>[1](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)</sup>

The notation \( x_1 x_2 \cdots x_u \) can be read two ways, as a single \( u \)-letter word or as a product of \( u \) one-letter words; because concatenation is associative, all readings give the same element. Each letter of \( X \) is identified with the corresponding one-letter word, so \( X \) sits inside \( X^{*} \).<sup>[1](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)</sup>

The same construction with the empty word removed gives \( X^{+} \), the set of non-empty words, which is a semigroup under concatenation, the free semigroup on \( X \). Joining the empty word to \( X^{+} \) produces the free monoid \( X^{*} \).<sup>[3](https://www.sciencedirect.com/topics/mathematics/free-semigroup)</sup> The star notation is the [Kleene star](https://www.edgepedia.org/kleene-star) of formal language theory.

## Universal property

The defining characteristic of \( X^{*} \) is its universal property: for any monoid \( M \) and any map \( f : X \to M \), there exists a unique monoid homomorphism \( \varphi : X^{*} \to M \) such that the diagram commuting with the canonical inclusion \( X \hookrightarrow X^{*} \) is satisfied.<sup>[1](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)</sup> There is no choice in the definition: \( \varphi \) must send the empty word to the identity of \( M \) and must send \( x_1 x_2 \cdots x_u \) to \( f(x_1) f(x_2) \cdots f(x_u) \), and this prescription is indeed a homomorphism.<sup>[1](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)</sup>

This property determines \( X^{*} \) up to isomorphism.<sup>[6](https://www.math.ru.nl/~mueger/PDF/BCHD.pdf)</sup> It also explains the word free: \( X^{*} \) carries exactly the monoid axioms and nothing more, so a word records the ordered history of generator multiplications without imposing any relations. Applying the property to a second alphabet \( B \) shows that any function \( f : A \to B \) induces a unique monoid homomorphism \( f^{*} : A^{*} \to B^{*} \) preserving the empty word and acting letter by letter.<sup>[6](https://www.math.ru.nl/~mueger/PDF/BCHD.pdf)</sup> In particular, alphabets of the same cardinality give isomorphic free monoids: if \( \lvert A_1 \rvert = \lvert A_2 \rvert \), any bijection \( A_1 \to A_2 \) extends to an isomorphism \( A_1^{*} \to A_2^{*} \).<sup>[5](https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/13%3A_Monoids_and_Automata/13.02%3A_Free_Monoids_and_Languages)</sup>

## Bases and free submonoids

An abstract characterization runs in the opposite direction. A monoid \( M \) is free if it contains a subset \( B \) such that \( M = B^{*} \), meaning \( B \) generates \( M \), and such that every equality \( x_1 \cdots x_n = y_1 \cdots y_m \) of products of base elements forces \( n = m \) and \( x_i = y_i \) for each \( i \). Condition (ii) says each element of \( M \) has a unique representation as a product of elements of \( B \), and \( B \) is called a base. The identity of \( M \) is never in the base.<sup>[2](https://www.math.utu.fi/en/home/karhumak/pdf/combwo.pdf)</sup>

For any alphabet \( A \), finite or infinite, the word monoid \( A^{*} \) is free with base \( A \), and \( A^{+} \) is free as a semigroup with the same base.<sup>[2](https://www.math.utu.fi/en/home/karhumak/pdf/combwo.pdf)</sup> Every free monoid with a finite or countable base is isomorphic to a word monoid \( A^{*} \), since any bijection from an alphabet to the base extends to an isomorphism.<sup>[2](https://www.math.utu.fi/en/home/karhumak/pdf/combwo.pdf)</sup>

Free submonoids of \( A^{*} \) are a central object of combinatorics on words, and freeness is not automatic. With \( X = \{a, ab, ba\} \), the submonoid \( X^{*} \) is not free, because the word \( aba \) has two factorizations, \( a \cdot ba \) and \( ab \cdot a \), and any generating subset of \( X^{*} \) must contain \( X \). With \( Y = \{a, ab, bb\} \), the submonoid \( Y^{*} \) is free, since no word in \( Y^{+} \) has two different \( Y \)-factorizations, which can be seen by reading any word from right to left. With \( Z = \{a, ab, b\} \), the monoid \( Z^{*} \) equals \( \{a, b\}^{*} \) and so is free, but it is not freely generated by \( Z \) itself.<sup>[2](https://www.math.utu.fi/en/home/karhumak/pdf/combwo.pdf)</sup> Freeness of a two-generator submonoid \( \{x, y\}^{*} \) is guaranteed whenever the primitive roots of \( x \) and \( y \) differ, because such words cannot satisfy a nontrivial relation.<sup>[2](https://www.math.utu.fi/en/home/karhumak/pdf/combwo.pdf)</sup>

## Relation to other free constructions

The free monoid sits in a family of free objects, and the differences among them are instructive.

**Free semigroup.** \( X^{+} \) is free as a semigroup, but no monoid can be a free semigroup, because the identity \( 1_M \) satisfies \( 1_M = 1_M \cdot 1_M \), violating unique factorization.<sup>[7](https://users.utu.fi/harju/semigroups/Semigroups.pdf)</sup> Correspondingly, the trivial monoid is the free monoid on the empty set, while there is no free semigroup on the empty set.<sup>[8](https://math.stackexchange.com/questions/58553/why-is-the-free-monoid-free)</sup>

**Free commutative monoid.** If commutativity is imposed, words are no longer the right model. The free commutative monoid on \( A \) is the additive monoid \( \mathbb{N}^{A} \) of finitely supported functions \( A \to \mathbb{N} \), with componentwise addition; an element records only how many times each generator occurs, not their order.<sup>[3](https://www.sciencedirect.com/topics/mathematics/free-semigroup)</sup> Its non-zero elements form the free commutative semigroup on \( X \).<sup>[9](https://jdhsmith.math.iastate.edu/class/505Free.pdf)</sup>

**Free group.** The free group on \( X \) is obtained from the free monoid by adjoining formal inverses \( a^{-1} \) for each letter and quotienting by the cancellations \( a a^{-1} = \varepsilon \).<sup>[8](https://math.stackexchange.com/questions/58553/why-is-the-free-monoid-free)</sup>

**Algebras.** For a field \( \mathbb{F} \), the monoid algebra \( \mathbb{F} A^{*} \) is the free noncommutative \( \mathbb{F} \)-algebra generated by \( A \), denoted \( \mathbb{F}\langle A \rangle \). It is distinct from the free commutative \( \mathbb{F} \)-algebra over \( A \), which is the [polynomial ring](https://www.edgepedia.org/polynomial-ring) \( \mathbb{F}[A] \).<sup>[6](https://www.math.ru.nl/~mueger/PDF/BCHD.pdf)</sup>

## Role in formal language theory

A formal language over an alphabet \( A \) is by definition a subset of \( A^{*} \); the free monoid is therefore the ambient space of the entire subject.<sup>[5](https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/13%3A_Monoids_and_Automata/13.02%3A_Free_Monoids_and_Languages)</sup> The length grading \( A^{*} = A^{0} \cup A^{1} \cup A^{2} \cup \cdots \) is a partition into disjoint sets, with \( A^{0} = \{\lambda\} \) the singleton containing the null string, and if \( A \) is countable then \( A^{*} \) is countable.<sup>[5](https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/13%3A_Monoids_and_Automata/13.02%3A_Free_Monoids_and_Languages)</sup> [Concatenation](https://www.edgepedia.org/concatenation) is noncommutative whenever the alphabet has more than one letter.<sup>[5](https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/13%3A_Monoids_and_Automata/13.02%3A_Free_Monoids_and_Languages)</sup>

The universal property makes \( A^{*} \) the starting point for presentations. A finitely presented monoid is a quotient of a free monoid on finitely many generators by a finitely generated congruence, that is, by a set of pairs of words \( (u_i, v_i) \) declaring \( u_i = v_i \).<sup>[10](https://math.ou.edu/~dmccullough/teaching/f06-6833/gap/htm/ref/CHAP051.htm)</sup> For example, the presentation \( \langle a, b \mid aaa = a,\ bbb = b,\ ab = ba \rangle \) yields a nine-element monoid in which every word reduces to one of \( \varepsilon, a, b, aa, ab, bb, aab, abb, aabb \).<sup>[4](https://d-nb.info/1190725940/34)</sup> Word problems, syntactic monoids, and the connections between automata and algebra all take the free monoid as their input: a language \( L \subseteq A^{*} \) is recognized by a homomorphism from \( A^{*} \) to a finite monoid, and the syntactic monoid of \( L \) is a quotient of \( A^{*} \) by the syntactic congruence.<sup>[11](https://arxiv.org/abs/1504.02694)</sup>

Work as recent as 2024 keeps drawing on the freeness structure itself: that year, a paper constructed a free monoid that includes every prefix code, studying it in relation to the families of i-th powers of primitive words with i at least 2, thereby generalizing two 1998 findings of Shyr and Tsai.<sup>[12](https://doi.org/10.1007/s11766-024-4279-1)</sup>

## In software

[Computer algebra](https://www.edgepedia.org/computer-algebra) systems construct free monoids directly. In GAP, the function `FreeMonoid` returns a free monoid on a specified nonnegative number of generators, on explicitly named generators, or, with the rank given as `infinity`, on infinitely many generators; generator labels are an aid for printing and do not necessarily distinguish generators.<sup>[13](https://gap-system.github.io/gap/doc/ref/chap51.html)</sup>

## References

1. [Bux, K.-U. Algebra I and II, Example 1.1.1.9 and Theorem 1.1.1.10, Universität Bielefeld lecture notes](https://www.math.uni-bielefeld.de/~bux/texts/algebra_notes.pdf)
2. [Karhumäki, J. Combinatorics of Words, Section 5: Free monoids and semigroups, University of Turku](https://www.math.utu.fi/en/home/karhumak/pdf/combwo.pdf)
3. [Free Semigroup, ScienceDirect Topics overview](https://www.sciencedirect.com/topics/mathematics/free-semigroup)
4. [Semigroups and Monoids (appendix), d-nb.info full text](https://d-nb.info/1190725940/34)
5. [Doerr, A. and Levasseur, K. Applied Discrete Structures, Section 13.2: Free Monoids and Languages, Mathematics LibreTexts](https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/13%3A_Monoids_and_Automata/13.02%3A_Free_Monoids_and_Languages)
6. [Mueger, M. Basic Category Theory notes (BCHD), Radboud University Nijmegen](https://www.math.ru.nl/~mueger/PDF/BCHD.pdf)
7. [Harju, T. Semigroups, chapter on free monoids, University of Turku](https://users.utu.fi/harju/semigroups/Semigroups.pdf)
8. [Why is the free monoid free?, Mathematics Stack Exchange](https://math.stackexchange.com/questions/58553/why-is-the-free-monoid-free)
9. [Smith, J.D.H. Free Groups and Monoids, Iowa State University class notes](https://jdhsmith.math.iastate.edu/class/505Free.pdf)
10. [GAP reference manual, Chapter 51: Finitely Presented Semigroups and Monoids](https://math.ou.edu/~dmccullough/teaching/f06-6833/gap/htm/ref/CHAP051.htm)
11. [Adámek, J., Milius, S., and Urbat, H. Syntactic Monoids in a Category, arXiv:1504.02694](https://arxiv.org/abs/1504.02694)
12. [Cao, C.-h., Liu, Q., and Yang, D. A free monoid containing all prefix codes, Applied Mathematics-A Journal of Chinese Universities 39, 596–603 (2024)](https://doi.org/10.1007/s11766-024-4279-1)
13. [GAP reference manual, Chapter 51: Semigroups and Monoids, section FreeMonoid](https://gap-system.github.io/gap/doc/ref/chap51.html)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Computational and symbolic algebra › Algebraic combinatorics and graph theory › Combinatorics on words and free structures*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license