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.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.
https://hdl.handle.net/11365/1006917