Back to Search
Start Over
UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS.
- Source :
- Journal of Symbolic Logic; Mar2014, Vol. 79 Issue 1, p60-88, 29p
- Publication Year :
- 2014
-
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 Σ<subscript>3</subscript><superscript>0</superscript>-complete (the former answering an open question of Gao and Gerdes). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00224812
- Volume :
- 79
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Journal of Symbolic Logic
- Publication Type :
- Academic Journal
- Accession number :
- 96277382
- Full Text :
- https://doi.org/10.1017/jsl.2013.8