# Varieties of rational languages and (pseudo-)varieties of finite monoids, question regarding closure property

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.
• Said differently $\mathcal V$ is a contravariant functor from the category of fg free monoids to the category of Boolean algebras. – Benjamin Steinberg Oct 7 '13 at 16:31