Semigroups of binary relations with right units. (Q1416172)

Denote by \(B_X\) the semigroup, under composition, of all binary relations on the set \(X\). Fix an element \(\alpha\in B_X\) and let \(\theta_X^{(R)}(\alpha)=\{\beta\in B_X:\beta\circ\alpha\subseteq\beta\}\). Then \(\theta_X^{(R)}(\alpha)\) is a subsemigroup of \(B_X\) and is the object of investigation in this paper. For \(Y\subseteq X\), let \(Y\alpha=\{x\in X:(y,x)\in\alpha\) for some \(y\in Y\}\) and let \(\alpha Y=Y\alpha^{-1}\). Denote \(\{y\}\alpha\) and \(\alpha\{y\}\) respectively by the less cumbersome notations \(y\alpha\) and \(\alpha y\). Let \(V(\alpha)=\{Y\alpha:Y\subseteq X\}\). Let \(\alpha^*=\{(x,y)\in X\times X:y\alpha\subseteq x\alpha\}\) and \(\alpha_*=\{(x,y)\in X\times X:\alpha x\subseteq\alpha y\}\). Let \(\alpha^r\) and \(\alpha^t\) denote respectively the reflexive closure and the transitive closure of \(\alpha\). That is, \(\alpha^r=\alpha\cup\Delta_X\) and \(\alpha^t=\bigcup_{n=1}^\infty\alpha^n\). Finally, let \(\alpha^{rt}=(\alpha\cup\Delta_X)^t\). The author gives several characterizations of the elements which belong to \(\theta_X^{(R)}(\alpha)\). He goes on to show that if \(\alpha^{rt}\) is an equivalence relation on an \(n\)-element set \(X\) and \(m\) is the number of equivalence classes, then \(|\theta_X^{(R)}(\alpha)|=2^{mn}\). He shows that for any \(\alpha\in B_X\), there is exactly one quasiorder which is a right identity for \(\theta_X^{(R)}(\alpha)\) and that element is \(\alpha^{rt}\). Moreover, if \(\beta\) is any right identity for \(\theta_X^{(R)}(\alpha)\), then \(\beta\subseteq\alpha^{rt}\) and, finally, an arbitrary relation \(\beta\) is a right identity for \(\theta_X^{(R)}(\alpha)\) if and only if \(V(\beta)\subseteq V(\alpha^{rt})\). This paper is an exhaustive investigation of the semigroup \(\theta_X^{(R)}(\alpha)\) and it is not possible to give details of the many results in any review of reasonable length so we content ourselves with a brief description of the areas which are covered. He finds irreducible generating sets for certain of these semigroups. He finds maximal idempotent subsemigroups for certain of these semigroups. In the final section of the paper, he determines Green's relations and the regular elements for \(\theta_X^{(R)}(\alpha)\). For example, let \(\beta,\delta\in\theta_X^{(R)}(\alpha)\) and let \(\mathcal L\), \(\mathcal R\), and \(\mathcal D\) denote Green's relations. He shows that \(\beta{\mathcal L}\delta\) if and only if \(V(\beta)=V(\alpha^{rt}\circ\beta)=V(\alpha^{rt}\circ\delta)=V(\delta)\). He shows that \(\beta{\mathcal R}\delta\) if and only if \(V(\beta^{-1})=V(\delta^{-1})\) and \(\beta{\mathcal D}\delta\) if and only if \(V(\beta)=V(\alpha^{rt}\circ\beta)\), \(V(\delta)=V(\alpha^{rt}\circ\delta)\) and \(V(\beta)\) and \(V(\delta)\) are isomorphic.