We study computably enumerable equivalence relations (ceers), under the reducibility R ≤ S if there exists a computable function f such that x R y if and only if f(x) S f(y), for every x, y. We show that the degrees of ceers under the equivalence relation generated by ≤ form a bounded poset that is neither a lower semilattice, nor an upper semilattice, and its first-order theory is undecidable.We then study the universal ceers. We show that 1) the uniformly effectively inseparable ceers are universal, but there are effectively inseparable ceers that are not universal; 2) a ceer R is universal if and only if R R' ≤ R, where R' denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes); and 3) both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are Σ^0_3-complete (the former answering an open question of Gao and Gerdes).
|Titolo:||Universal computably enumerable equivalence relations|
|Citazione:||Andrews, U., Lempp, S., Miller, J.S., Ng, K.M., San Mauro, L., & Sorbi, A. (2014). Universal computably enumerable equivalence relations. THE JOURNAL OF SYMBOLIC LOGIC, 79(1), 60-88.|
|Appare nelle tipologie:||1.1 Articolo in rivista|