We review the literature on universal computably enumerable equivalence relations, i.e. the computably enumerable equivalence relations (ceers) which are $\Sigma^0_1$-complete with respect to computable reducibility on equivalence relations. Special attention will be given to the so-called uniformly effectively inseparable (u.e.i.) ceers, i.e. the nontrivial ceers yielding partitions of the natural numbers in which each pair of distinct equivalence classes is effectively inseparable (uniformly in their representatives). The u.e.i. ceers comprise infinitely many isomorphism types. The relation of provable equivalence in Peano Arithmetic plays an important role in the study and classification of the u.e.i. ceers.

Andrews, U., Badaev, S., Sorbi, A. (2017). A survey on universal computably enumerable equivalence relations. In M.F. A. Day (a cura di), Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (pp. 418-451). Cham : Springer International Publishing [10.1007/978-3-319-50062-1_25].

A survey on universal computably enumerable equivalence relations

SORBI, ANDREA
2017-01-01

Abstract

We review the literature on universal computably enumerable equivalence relations, i.e. the computably enumerable equivalence relations (ceers) which are $\Sigma^0_1$-complete with respect to computable reducibility on equivalence relations. Special attention will be given to the so-called uniformly effectively inseparable (u.e.i.) ceers, i.e. the nontrivial ceers yielding partitions of the natural numbers in which each pair of distinct equivalence classes is effectively inseparable (uniformly in their representatives). The u.e.i. ceers comprise infinitely many isomorphism types. The relation of provable equivalence in Peano Arithmetic plays an important role in the study and classification of the u.e.i. ceers.
2017
978-3-319-50061-4
Andrews, U., Badaev, S., Sorbi, A. (2017). A survey on universal computably enumerable equivalence relations. In M.F. A. Day (a cura di), Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (pp. 418-451). Cham : Springer International Publishing [10.1007/978-3-319-50062-1_25].
File in questo prodotto:
File Dimensione Formato  
surveyceers.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 292.15 kB
Formato Adobe PDF
292.15 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11365/1006917