rational set
Given an alphabet $\mathrm{\Sigma}$, recall that a regular language $R$ is a certain subset of the free monoid $M$ generated by $\mathrm{\Sigma}$, which can be obtained by taking singleton subsets of $\mathrm{\Sigma}$, and perform, in a finite number of steps, any of the three basic operations^{}: taking union, string concatenation, and the Kleene star.
The construction of a set like $R$ is still possible without $M$ being finitely generated^{} free.
Let $M$ be a monoid, and ${\mathcal{S}}_{M}$ the set of all singleton subsets of $M$. Consider the closure^{} ${\mathcal{R}}_{M}$ of $S$ under the operations of union, product^{}, and the formation of a submonoid of $M$. In other words, ${\mathcal{R}}_{M}$ is the smallest subset of $M$ such that

•
$\mathrm{\varnothing}\in {\mathcal{R}}_{M}$,

•
$A,B\in {\mathcal{R}}_{M}$ imply $A\cup B\in {\mathcal{R}}_{M}$,

•
$A,B\in {\mathcal{R}}_{M}$ imply $AB\in {\mathcal{R}}_{M}$, where $AB=\{ab\mid a\in A,b\in B\}$,

•
$A\in {\mathcal{R}}_{M}$ implies ${A}^{*}\in {\mathcal{R}}_{M}$, where ${A}^{*}$ is the submonoid generated by $A$.
Definition. A rational set of $M$ is an element of ${\mathcal{R}}_{M}$.
If $M$ is a finite generated free monoid, then a rational set of $M$ is also called a rational language, more commonly known as a regular language.
Like regular languages, rational sets can also be represented by regular expressions^{}. A regular expression over a monoid $M$ and the set it represents are defined inductively as follows:

•
$\mathrm{\varnothing}$ and $a$ are regular expressions, for any $a\in M$, representing sets $\mathrm{\varnothing}$ and $\{a\}$ respectively.

•
if $a,b$ are regular expressions, so are $a\cup b$, $ab$, and ${a}^{*}$. Furthermore, if $a,b$ represent sets $A,B$, then $a\cup b$, $ab$, and ${a}^{*}$ represent sets $A\cup B$, $AB$, and ${A}^{*}$ respectively.
Parentheses are used, as usual, to avoid ambiguity.
From the definition above, it is easy to see that a set $A\subseteq M$ is rational iff it can be represented by a regular expression over $M$.
Below are some basic properties of rational sets:

1.
Any rational set $M$ is a subset of a finitely generated submonoid of $M$. As a result, every rational set over $M$ is finite iff $M$ is locally finite^{} (meaning every finitely generated submonoid of $M$ is actually finite).

2.
Rationality is preserved under homomorphism^{}: if $A$ is rational over $M$ and $f:M\to N$ is a homomorphism, then $f(A)$ is rational over $N$.

3.
Conversely, if $B\in f(M)$ is rational over $N$, then there is a rational set $A$ over $M$ such that $f(A)=B$. Thus if $f$ is onto, every rational set over $N$ is mapped by a rational set over $M$. If $f$ fails to be onto, the statement becomes false. In fact, inverse^{} homomorphisms generally do not preserve rationality.
References
Title  rational set 

Canonical name  RationalSet 
Date of creation  20130322 19:01:16 
Last modified on  20130322 19:01:16 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  8 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 20M35 
Classification  msc 68Q70 
Defines  rational language 