Decidability and hyperdecidability of joins of pseudovarieties
Benjamin Steinberg, John Rhodes · 1998
This thesis explores various reasonable assumptions that one can place on pseudovarieties V and W of semigroups in order to be able to compute their join, V $\vee$ W. We begin with a useful adjunction which allows us to state a criterion for membership in V $\vee$ W in terms of pointlike sets with respect to V. We use this criterion to show that joins with locally finite pseudovarieties are well-behaved. We give similar results for the notion of hyperdecidability of pseudovarieties. We then proceed to generalize these results to increasing!y more difficult situations, the apex being the decidability, even hyperdecidability of J $\vee$ G, a previously intractable problem. For 10 years this membership problem has been open. It resisted previous attempts at solution because it is not finitely based, i.e. has no finite basis of pseudoidentities. These results then naturally lead one to look at hyperdecidability, decidability of pointlikes, and how these extend over to semidirect products. Towards this end, we obtain a simple proof that taking the semidirect product with a locally finite pseudovariety preserves hyperdecidability, in fact this was the original proof of this fact for pointlike sets. Also several examples are done for pseudovarieties of semigroups with only a single idempotent.