Reducibilities among equivalence relations induced by recursively enumerable structures
In this paper we investigate the dependence of recursively enumerable structures on the equality relation which is fixed to a specific r.e. equivalence relation. We compare r.e. equivalence relations on the natural numbers with respect to the amount of structures they permit to represent from a given class of structures such as algebras, permutations and linear orders. In particular, we show that for various types of structures represented, there are minimal and maximal elements.
reducibilities recursively enumerable equivalence classes algebraic structures degrees realisability