Rational set

Let ${\displaystyle (N,\cdot )}$ be a monoid with identity element ${\displaystyle e}$. The set ${\displaystyle \mathrm {RAT} (N)}$ of rational subsets of ${\displaystyle N}$ is the smallest set that contains every finite set and is closed under

• union: if ${\displaystyle A,B\in \mathrm {RAT} (N)}$ then ${\displaystyle A\cup B\in \mathrm {RAT} (N)}$
• product: if ${\displaystyle A,B\in \mathrm {RAT} (N)}$ then ${\displaystyle A\cdot B=\{a\cdot b\mid a\in A,b\in B\}\in \mathrm {RAT} (N)}$
• Kleene star: if ${\displaystyle A\in \mathrm {RAT} (N)}$ then ${\displaystyle A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {RAT} (N)}$ where ${\displaystyle A^{0}=\{e\}}$ is the singleton containing the identity element, and where ${\displaystyle A^{n+1}=A^{n}\cdot A}$.

This means that any rational subset of ${\displaystyle N}$ can be obtained by taking a finite number of finite subsets of ${\displaystyle N}$ and applying the union, product and Kleene star operations a finite number of times.

In general a rational subset of a monoid is not a submonoid.

Let ${\displaystyle A}$ be an alphabet, the set ${\displaystyle A^{*}}$ of words over ${\displaystyle A}$ is a monoid. The rational subset of ${\displaystyle A^{*}}$ are precisely the regular languages. Indeed, the regular languages may be defined by a finite regular expression.

The rational subsets of ${\displaystyle \mathbb {N} }$ are the ultimately periodic sets of integers. More generally, the rational subsets of ${\displaystyle \mathbb {N} ^{k}}$ are the semilinear sets.[1]

McKnight's theorem states that if ${\displaystyle N}$ is finitely generated then its recognizable subset are rational sets. This is not true in general, since the whole ${\displaystyle N}$ is always recognizable but it is not rational if ${\displaystyle N}$ is infinitely generated.

Rational sets are closed under morphism: given ${\displaystyle N}$ and ${\displaystyle M}$ two monoids and ${\displaystyle \phi :N\rightarrow M}$ a morphism, if ${\displaystyle S\in \mathrm {RAT} (N)}$ then ${\displaystyle \phi (S)=\{\phi (x)\mid x\in S\}\in \mathrm {RAT} (M)}$.

${\displaystyle \mathrm {RAT} (N)}$ is not closed under complement as the following example shows.[2] Let ${\displaystyle N=\{a\}^{*}\times \{b,c\}^{*}}$, the sets ${\displaystyle R=(a,b)^{*}(1,c)^{*}=\{(a^{n},b^{n}c^{m})\mid n,m\in \mathbb {N} \}}$ and ${\displaystyle S=(1,b)^{*}(a,c)^{*}=\{(a^{n},b^{m}c^{n})\mid n,m\in \mathbb {N} \}}$ are rational but ${\displaystyle R\cap S=\{(a^{n},b^{n}c^{n})\mid n\in \mathbb {N} \}}$ is not because its projection to the second element ${\displaystyle \{b^{n}c^{n}\mid n\in \mathbb {N} \}}$ is not rational.

The intersection of a rational subset and of a recognizable subset is rational.

For finite groups the following result of A. Anissimov and A. W. Seifert is well known: a subgroup H of a finitely generated group G is recognizable if and only if H has finite index in G. In contrast, H is rational if and only if H is finitely generated.[3]

A binary relation between monoids M and N is a rational relation if the graph of the relation, regarded as a subset of M×N is a rational set in the product monoid. A function from M to N is a rational function if the graph of the function is a rational set.[4]

• Rational series
• Recognizable set
• Rational monoid

• Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Chapter 7: Automata". Discrete Algebraic Methods. Berlin/Boston: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8.
• Jean-Éric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets
• Samuel Eilenberg and M. P. Schützenberger, Rational Sets in Commutative Monoids, Journal of Algebra, 1969.

• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. Part II: The power of algebra. ISBN 978-0-521-84425-3. Zbl 1188.68177.