Recursively Enumerable Equivalence Relations Modulo Finite Differences
André Nies · Mathematical logic quarterly · 1994
Abstract We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first‐order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many‐one degrees in Eq*, thereby showing that Th(Eq*) has the same computational complexity as the true first‐order arithmetic. Mathematics Subject Classification: 03D25, 03D15, 03D35.