Quasigroups, congruences and recognizable subsets

Question

My question refers to the draft of Mathematical Foundations of Automata Theory, IV.2.1 (pages 89ff in the pdf). I will repeat everything necessary nevertheless:

Let $M,N$ be monoids and $\varphi: M \rightarrow N $ a monoid morphism. We say that a subset $L$ of $M$ is recognizable by $\varphi$ if there is a subset $P$ of $N$ such that $L = \varphi^{-1}(P)$. As is known, the rational languages are precisely the recognizable subsets of $\Sigma^\ast$.

Furthermore, we define an equivalence relation $R_\varphi$ by $u R_\varphi v :\Leftrightarrow \varphi(u)=\varphi(v)$. This relation is a congruence relation, that is $\forall s,t,u,v \in M:s R_\varphi t \Rightarrow usv~R_\varphi~utv$.

We say that a congruence relation $R$ saturates $L$ if for all $u \in L$, $uRv$ implies $v \in L$. Then in the above document, the following proposition (IV.2.2, page 90) is stated:

Let $\varphi : M \rightarrow N$ be a monoid morphism and let $L$ be a subset of $M$. The following conditions are equivalent:

(1) $L$ is recognised by $\varphi$

(2) $L$ is saturated by $R_\varphi$

(3) $\varphi^{-1}(\varphi(L))=L$

Proof. (1) implies (2). If $L$ is recognised by $\varphi$, then $L=\varphi^{-1}(P)$ for some subset $P$ of $N$. Thus if $x \in L$ and $x R_\varphi y$, one has $\varphi(x) \in P$ and since $\varphi(x)=\varphi(y), y \in \varphi^{-1}(P)=L$.

(2) implies (3). If $x \in \varphi^{-1}(\varphi(L))$, there is $y \in L$ such that $\varphi(x) = \varphi(y)$, that is $x R_\varphi y$. Thus, $x \in L$, and $\varphi^{-1}(\varphi(L)) \subseteq L$ follows. "$\supseteq$" is trivial.

(3) implies (1). Let $P:=\varphi(L)$, then $\varphi^{-1}(P)=L$.

I want to weaken the assumptions made in the proposition. Namely, assume tgat the $N$ in the above definitions is a proper groupoid (in fact, I need to deal with loops), that is, associativity and identity are lost. Further, $\varphi$ need not be a morphism (the relation $R_\varphi$, defined in the same way as above, a priori need not be a congruence anymore) and we restate (1) accordingly (as formally, the notion of a "recognable subset" is not defined for groupoids). Then my questions are

(1) Is $R_\varphi$ still a congruence if we demand $\varphi$ to be a morphism of groupoids (loops)?

(2) Does the proposition still hold? Does it if we assume that $R_\varphi$ is not a congruence?

(3) What other sources (preferably monographs) are there that you recommend as comprehensive introductions to algebraic automata theory, esp. concerned with the role of monoids, semigroups (and maybe more general structures as groupoids) and their connection with automata and languages?

Personally, I think they are both true, as for (2), neither the morphism properties, nor associativity nor congruences seem to be used in the proof. And for (1), I don't see where one would need associativity to prove it. But it may well be that I overlooked something (which is why I ask...).

Answer 1

(1) for any function $\varphi:E\to F$, the relation $R_\varphi$ as you define it is always an equivalence relation on elements of $E$. But the notion of congruence depends of the laws you have on your sets, and $R_\varphi$ will be a congruence for the operations that are preserved by $\varphi$. Notice that your formulation with $usv$ is not anymore well-defined without associativity: you have to state it separately for $us$ and $sv$.

(2) Let us weaken even more the hypotheseses. Let $\varphi:E\to F$ be any function, without any structure assumed on $E$ and $F$. Then if we take the definitions you wrote for "recognised" and "saturated", the 3 propositions are still equivalent, as your proofs still work.

The thing you will lose by considering arbitrary sets (or groupoids or loops) is that you won't carry out the nice monoid structure of $\Sigma^*$, so you lose almost all the tools of regular languages theory, like Myhill-Nerode equivalence, Green relations, and so on...

For (3), I think Jean-Eric Pin's webpage (including the document you mention) contains good surveys of this field.