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, 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 Σ03 -complete (the former answering an open question of Gao and Gerdes).

Universal computably enumerable equivalence relations

San Mauro Luca.;
2014-01-01

Abstract

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, 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 Σ03 -complete (the former answering an open question of Gao and Gerdes).
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11586/454544
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 44
  • ???jsp.display-item.citation.isi??? ND
social impact