Three Notions of Conjugacy for Abstract Semigroups
Araújo, João; Kinyon, Michael; Konieczny, Janusz ; Malheiro, António


There have been several attempts to extend the notion of conjugacy from groups to semigroups.
One notion, which we will denote by $\cp$, was originally introduced for free semigroups and popularized by Lallement's book.
In a general semigroup, $\cp$ is reflexive and symmetric, but not transitive.
However, one may consider the transitive closure $\cp^*$ of $\cp$, which is an equivalence relation in any semigroup.
Another notion of conjugacy, which we will denote by $\co$, was introduced by Otto for monoids presented by finite Thue systems.
The relation $\co$ is an equivalence relation in any semigroup, but it reduces to the universal relation
if a semigroup has a zero;
{since there is a precise sense in which almost all finite semigroups have a zero, it follows that $\co$ is
not useful for almost all finite semigroups.} Three authors of the present paper introduced another notion of conjugacy, denoted by $\con$,
which is an equivalence relation in any semigroup; in addition, if a semigroup $S$ does not have a zero, then $\con\,\,=\,\,\co$ in $S$, but $\con$
does not reduce to the universal relation when a semigroup has a zero. In order to decide which notion is
{the most satisfactory}, in the sense that it allows the extension of the classic conjugacy results in groups and hence leads to strong and elegant results with interconnections with other parts of mathematics, it is necessary to carry out a deep study comparing and separating these three notions of conjugacy. This is the aim of our paper.

First, we study the decidability and independence of the conjugacy problems for certain classes of finitely presented monoids.
We show that there exists a monoid $M$ defined by a finite complete rewriting system such that
the $c$-conjugacy problem for $M$ is undecidable, and that for finitely presented monoids,
the $c$-conjugacy problem and the word problem are independent, as are the $c$-conjugacy and $p$-conjugacy problems.
As an especially interesting test case, we describe $\con$ and $\cp$ in the class of
polycyclic monoids, and show that in this class, the $p$-conjugacy is ``almost'' transitive
and that $\con$ is strictly included in $\cp$. We also characterize $\con$ in the symmetric inverse monoid $\mi(X)$
for a countable set $X$, and compare $\con$ and $\cp$ in that monoid.
We then generalize an outstanding theorem proved by Kudryavtseva,
showing that $\cp$ is transitive in a variety of semigroups that contains all
completely regular semigroups and their variants.

Although $\co$ and $\con$ coincide for semigroups without zero, they differ in the most extreme way in some semigroups with zero.
We present an infinite family of semigroups with zero divisors in which $\co$ is universal while $\con$ is the identity. We prove that commutative semigroups are precisely those where $\cp$ is the identity, and commutative and cancellative semigroups are those where $\co$ is the identity.
We also show that a semigroup in which $\cp$ is universal is necessarily simple. Moreover, if a semigroup
$S$ has an idempotent, we conclude that $S$ is a rectangular band if and only if $\cp$ is the universal relation.

The paper ends with a fairly large section of open problems on combinatorics, semigroup theory, decidability, transformation semigroups, model theory, matrix theory and universal algebra.

FCT - Fundação para a Ciência e a Tecnologia