Elementary theories of completely simple semigroups (Q701375)

The author investigates the relationship between the elementary theory \(T(C)\) of an arbitrary completely simple semigroup, expressed as a Rees matrix semigroup \(C=M(H,I,J,P)\), and the theory of the structure group \(H\). It is easily seen that if \(T(H)\) is undecidable, then so is \(T(C)\), each in the signature of multiplication. It is shown that in the case that \(I\) and \(J\) are finite, then as long as \(P\) is normalized, \(T(C)\) is decidable if and only if the theory of \(H\) is decidable under the signature obtained by adding the distinct matrix entries of \(P\) as constants. Without normalization, this need not hold. In the general case, decidability of \(T(C)\) is equivalent to the decidability of the elementary theory of every two-sorted system \(D(i_0,j_0)\), for \(i_0\in I\), \(j_0\in J\). Such systems are defined in terms of \(H\), \(I\times J\) and normalization with respect to the designated row and column of \(P\). As an application, it is shown that there is a Rees matrix semigroup over a three-element group whose elementary theory is undecidable. Various other applications are also given.