Reducibilities among equivalence relations induced by recursively enumerable structures (Q896924)

Recursively enumerable (r.e.) structures are structures over quotients \(\omega/E\), where \(E\) is an r.e. equivalence relation (an r.e.e.r.) on \(\omega\). Such a structure is called an \(E\)-structure, \((\omega/E, f_1,\dots f_m,P_1,\dots P_n)\), where \(m\) or \(n\) may be \(0\). (If \(n=0\), the \(E\)-structure is an algebra.) The functions must be recursive, the predicates r.e., with finitely many of each. Most important, they must all respect the equivalence relation \(E\). This paper assembles motley previous results and adds many of its own. They deal with such varied structures as permutation algebras, groups, rings, and orderings. There is a focus on ordering relations for the r.e.e.r. and there is extensive interplay with recursion theory. The topics are unusually varied. We select from them here. For r.e.e.r. \(E\), we write \(\mathcal K(E)\) for the class of \(E\)-structures, sometimes relativized by subscript to structures of a specific kind. We say that \(E\) realizes the structures in \(\mathcal K(E)\). For \(S \subseteq \omega\), we let \(E(S) = \{(x,y): x=y \text{ or } x,y \in S\}\). Two straightforward observations: (i) The identity relation is the only r.e.e.r. that realizes a structure containing an injective function; (ii) If \(S\) is a simple set then any function \(f(x)\) in a structure realized by \(E(S)\) must have a constant value for all but finitely many values of \(x\). Let \(C\) be the class of countably infinite algebras. We can define a partial order on the r.e.e.r. by \(E_1\leq _{\mathrm{alg}} E_2 \,\, \text{iff}\,\, \mathcal K_C(E_1) \subseteq \mathcal K_C(E_2)\). Call a set \(E\)-closed if it is a union of equivalence classes of \(E\). Then, with a maximal set from recursion theory playing a role in the argument, there is an r.e.e.r. \(E\) such that every nonempty \(E\)-closed r.e. set other than \(\omega\) is the union of finitely many \(E\)-equivalence classes. This \(E\) is a least element in the \(\leq _{\mathrm{alg}}\) ordering. Further, we can construct an r.e.e.r. \(E'\) not Turing equivalent to \(E\) with \(\mathcal K_C(E') = \mathcal K_C(E)\). On the other hand, there are infinitely many equivalence classes whose members are maximal in the \(\leq _{\mathrm{alg}}\) ordering, including the class of recursive equivalence relations which themselves have infinitely many equivalence classes. Now take \(C\) to be the class of linearly ordred sets. Defining \('E_1 \leq _{\mathrm{ord}} E_2'\) as above, the partial ordering has both a least element and a maximal element, the identity on \(\omega\). Among many results: If \(X \subseteq \omega\) is hyperhypersimple or creative or simple but not hypersimple then \(E(X)\) realizes no linear order; for every \(k\) there is a r.e.e.r that realizes exactly \(k\) orders; the partial order \(\leq _{\mathrm{ord}}\) contains an infinite descending chain.