On the residual finiteness of free semigroups and composition of Boolean matrices
Ki Hang Kim, F.W. Roush, W. Schönfeld · Proceedings of the American Mathematical Society · 1977
By Boolean matrices are meant matrices over the semiring (0, 1) under the operations sup{a, b} and ab. Such matrices can be regarded as relations on a finite set of individuals. In this way relation algebras or equivalently, certain types of programming languages can be treated by means of operations on matrices. In this note we consider expressions involving only matrix multiplication. The following proposition yields a new (as far as we know) proof of the residual finiteness of free semigroups. The corollary, when applied to the Boolean algebra (0, 1) shows that no semigroup identities hold for all square matrix semigroups over this Boolean algebra.