Deciding embeddability of partial groupoids into semigroups (Q1293382): Difference between revisions

It is known that the embeddability problem for the class of finite partial groupoids is unsolvable, i.e. there is no algorithm for deciding whether or not a finite partial groupoid can be embedded into a semigroup. A partial groupoid is called a partial semigroup if it is embeddable into a semigroup. The class of all partial semigroups is a quasivariety (in the sense of models). It is proved (Theorem 1) that the class of all partial semigroups is not first-order finitely axiomatizable. Similar results are proved for other classes of partial groupoids (associative partial groupoids, \(R\)-presemigroups, \(S\)-presemigroups). Finally, the Knuth-Bendix completion procedure is used for deciding embeddability of finite partial groupoids into semigroups.