Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T02:57:35.029Z Has data issue: false hasContentIssue false

UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS

Published online by Cambridge University Press:  17 April 2014

URI ANDREWS
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON, WI 53706-1388, USA E-mail: andrews@math.wisc.edu
STEFFEN LEMPP
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON, WI 53706-1388, USA E-mail: lempp@math.wisc.edu
JOSEPH S. MILLER
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON, WI 53706-1388, USA E-mail: jmiller@math.wisc.edu
KENG MENG NG
Affiliation:
DIVISION OF MATHEMATICAL SCIENCES SCHOOL OF PHYSICAL & MATHEMATICAL SCIENCES COLLEGE OF SCIENCE NANYANG TECHNOLOGICAL UNIVERSITY SINGAPORE E-mail: kmng@ntu.edu.sg
LUCA SAN MAURO
Affiliation:
SCUOLA NORMALE SUPERIORE PERFEZIONAMENTO IN DISCIPLINE FILOSOFICHE I-56126 PISA, ITALY E-mail: luca.sanmauro@sns.it
ANDREA SORBI
Affiliation:
DIPARTIMENTO DI INGEGNERIA DELL’INFORMAZIONE E SCIENZE MATEMATICHE UNIVERSITÀ DEGLI STUDI DI SIENA, VIA ROMA, 56 I-53100 SIENA, ITALY E-mail: sorbi@unisi.it
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study computably enumerable equivalence relations (ceers), under thereducibility $R \le S$ if there exists a computable function f suchthat $x\,R\,y$ if and only if $f\left( x \right)\,\,S\,f\left( y \right)$, for every $x,y$. We show that the degrees of ceers under the equivalencerelation generated by $\le$ form a bounded poset that is neither a lower semilattice, noran upper semilattice, and its first-order theory is undecidable. We then studythe universal ceers. We show that 1) the uniformly effectively inseparable ceersare universal, but there are effectively inseparable ceers that are notuniversal; 2) a ceer R is universal if and only if $R\prime \le R$, where $R\prime$ 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 theuniversal ceers and the index set of the uniformly effectively inseparable ceersare ${\rm{\Sigma }}_3^0$-complete (the former answering an open question of Gao andGerdes).

Information

Type
Articles
Copyright
Copyright © Association for Symbolic Logic 2014