Recognizable set

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some morphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra.
This notion is different from the notion of recognizable language. Indeed, the term "recognizable" has a different meaning in computability theory.
Definition.
Let formula_1 be a monoid, a subset formula_2 is recognized by a monoid formula_3 if there exists a morphism formula_4 from formula_1 to formula_3 such that formula_7, and recognizable if it is recognized by some finite monoid. This means that there exists a subset formula_8 of formula_3 (not necessarily a submonoid of formula_3) such that the image of formula_11 is in formula_8 and the image of formula_13 is in formula_14.
Example.
Let formula_15 be an alphabet: the set formula_16 of words over formula_15 is a monoid, the free monoid on formula_15. The recognizable subsets of formula_16 are precisely the regular languages. Indeed, such a language is recognized by the transition monoid of any automaton that recognizes the language.
The recognizable subsets of formula_20 are the ultimately periodic sets of integers.
Properties.
A subset of formula_1 is recognizable if and only if its syntactic monoid is finite.
The set formula_22 of recognizable subsets of formula_1 is closed under:
Mezei's theorem states that if formula_3 is the product of the monoids formula_25, then a subset of formula_3 is recognizable if and only if it is a finite union of subsets of the form formula_27, where each formula_28 is a recognizable subset of formula_29. For instance, the subset formula_30 of formula_20 is rational and hence recognizable, since formula_20 is a free monoid. It follows that the subset formula_33 of formula_34 is recognizable.
McKnight's theorem states that if formula_1 is finitely generated then its recognizable subsets are rational subsets. 
This is not true in general, since the whole formula_1 is always recognizable but it is not rational if formula_1 is infinitely generated.
Conversely, a rational subset may not be recognizable, even if formula_1 is finitely generated. 
In fact, even a finite subset of formula_1 is not necessarily recognizable. For instance, the set formula_40 is not a recognizable subset of formula_41. Indeed, if a morphism formula_4 from formula_43 to formula_3 satisfies formula_45, then formula_4 is an injective function, hence formula_3 is infinite.
Also, in general, formula_22 is not closed under Kleene star. For instance, the set formula_33 is a recognizable subset of formula_34, but formula_51 is not recognizable. Indeed, its syntactic monoid is infinite.
The intersection of a rational subset and of a recognizable subset is rational.
Recognizable sets are closed under inverse of morphisms. I.e. if formula_1 and formula_3 are monoids and formula_54 is a morphism then if formula_55 then formula_56.
For finite groups the following result of Anissimov and 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.