Let $\mathcal Rat(A)$ denote the class of rational (or regular) languages over the alphabet $A$, a subset $\mathcal V(A) \subseteq \mathcal Rat(A)$ is called a variety of (rational) languages iff

  1. closed under boolean operations
  2. closed under quotients, i.e. if $L \in \mathcal V(A)$, then so is

    $u^{-1}L = \{ w \in A^* : uw \in L \}$ and $Lu^{-1} = \{ w \in A^* : wu \in L \}$.

  3. closed under inverse images of morphisms, i.e. if $\varphi : A^* \to B^*$ is a morphism and $L \in \mathcal V(B)$ for some variety of languages $\mathcal V(B)$, then $\varphi^{-1}(L) \in \mathcal V(A)$.

On the other side, a (pseudo-)variety of finite monoids $\mathbf V$ is a class of finite monoids such that

  1. it is closed under quotient, i.e. if $\varphi : M \to N$ is a surjective morphism and $M \in \mathbf V$, so $N \in \mathbf V$.
  2. closed under subalgebras, i.e. if $N$ is a subalgebra of $M$ and $M \in \mathbf V$ so $N \in \mathbf V$
  3. closed under finite products, i.e. for $M,N \in \mathbf V$ also $M \times N \in \mathbf V$.

Now according to Eilenberg, there is a bijective correspondence between the class of (pseudo-)varieties of finite monoids and the class of all varieties of rational languages, given by $$ \mathbf V \to \{ L \subseteq A : L\mbox{ is recognized by some monoid of }\mathbf V \}. $$ where a language $L$ is recognized by some monoid $M$ iff there exists a morphism $\varphi : A^* \to M$ and a subset $F \subseteq M$ such that $L = \varphi^{-1}(F)$.

Now my question is where comes condition 3. in the definition of variety of languages from? I tried to prove it for the class given above, if $\varphi : A^* \to B^*$ is a morphism, and $L \in \mathcal V(B)$ for some variety, then $L$ is recognized by some $\psi : B^* \to M$ and $F \subseteq M$. So $\varphi^{-1}(L) = \varphi^{-1}(\psi^{-1}(F))$, then $\psi \circ \phi : A^* \to M$ recognizes $\phi^{-1}(L)$, but I cannot conclude that $M \in \mathbf V$, which is necessary for $\mathcal V(A)$. Had I overlooked something in the definition of condition 3, maybe that $\mathcal V(B)$ has to be a variety over the same pseudovariety but different alphabets? But I nowhere find in the literature such a condition, it is just stated in this general form "for some variety $\mathcal V(B)$"?


I think the confusion comes from the fact that a variety of languages is not $\mathcal V(A)$ for some fixed $A$, it is a mapping $\mathcal V: \mathit{Alphabets}\to \mathit{Sets~of~Languages}$, mapping each alphabet $A$ to a set of languages $\mathcal V(A)$.

Now it makes sense to say that $\mathcal V$ is closed under inverse morphisms.

The bijection of Eilenberg is actually between $\mathbf{V}$ and $\mathcal V$ (so no alphabet is fixed on either side), which solves the problem in your proof.

| cite | improve this answer | |
  • 1
    $\begingroup$ Said differently $\mathcal V$ is a contravariant functor from the category of fg free monoids to the category of Boolean algebras. $\endgroup$ – Benjamin Steinberg Oct 7 '13 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.