Classes of semigroups and classes of sets

摘要

Let A be a subset of &Sgr;+, the free semigroup generated by a finite set &Sgr;. In &Sgr;+ we consider congruences satisfying the condition xny & xεA@@@@yε A

Among all such congruences there is a largest one, and the quotient monoid by this congruence is denoted by SA and is called the syntactic semigroup of A. This semigroup is finite if and only if the set A is recognizable (by a finite automaton). The semigroup SA can then easily be described using the minimal automaton of A.

It is reasonable to expect that reasonable properties of the recognizable set A will be reflected by reasonable properties of the finite semigroups SA and vice-versa. In trying to establish such a dialog, one is handicapped by the fact that there are finite semigroups which are not syntactic monoids of any set.

The objective of this note is to state a theorem showing that the above inconvenience disappears if one considers classes of sets (rather than individual sets) and classes of semigroups.